#17886: Faster qqbar operations using resultants
-------------------------------------+-------------------------------------
Reporter: gagern | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.6
Component: number fields | Resolution:
Keywords: qqbar resultant | Merged in:
exactify minpoly | Reviewers:
Authors: Martin von Gagern | Work issues:
Report Upstream: N/A | Commit:
Branch: | 234b2c4f3435531007c095d278a4c02da8ee2365
u/gagern/ticket/17886 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Old description:
> This is a spin-off from comment:31:ticket:16964.
>
> Many operations on algebraic numbers can become painfully slow. Most of
> these operations can be expressed in terms of resultants, and
> surprisingly the corresponding computations are sometimes ''way'' faster
> than what Sage currently does. So much faster that I'm not sure whether
> to consider this ticket here a request for enhancement, or even a defect.
>
> Take for example the difference between two algebraic numbers `r1` and
> `r2`, which are defined as follows:
>
> {{{
> sage: x = polygen(ZZ)
> sage: p1 = x^5 + 6*x^4 - 42*x^3 - 142*x^2 + 467*x + 422
> sage: p2 = p1((x-1)^2)
> sage: r1 = QQbar.polynomial_root(p2, CIF(1, (2.1, 2.2)))
> sage: r2 = QQbar.polynomial_root(p2, CIF(1, (2.8, 2.9)))
> }}}
>
> Computing their exact difference takes like forever:
>
> {{{
> sage: r4 = r1 - r2
> sage: %time r4.exactify()
> (still running, after more than half an hour)
> }}}
>
> On the other hand, computing a polynomial which has the difference as one
> root can be achieved fairly easily using resultants, and the resulting
> number is obtained in under one second:
>
> {{{
> sage: a,b = polygens(QQ, 'a,b')
> sage: %time p3 = r1.minpoly()(a + b).resultant(r2.minpoly()(b), b)
> CPU times: user 62 ms, sys: 0 ns, total: 62 ms
> Wall time: 68 ms
> sage: rs = [r for f in p3.factor()
> ....: for r in f[0].univariate_polynomial().roots(QQbar, False)
> ....: if r._value.overlaps(r1._value - r2._value)]
> sage: assert len(rs) == 1
> sage: r3, = rs
> sage: %time r3.exactify()
> CPU times: user 599 ms, sys: 0 ns, total: 599 ms
> Wall time: 578 ms
> }}}
>
> One possible root of `p3` is `b=r2` and `a+b=r1` which means `a=r1-r2`.
> So eliminating b we get a (reducible, not minimal) polynomial in a which
> has that difference as one of its roots. I try to identify that by
> looking at the roots `r` of the factors `f`, checking whether they
> overlap the numeric interval.
>
> The way I understand the current code, most exact binary operations are
> implemented by exactifying both operands to number field elements, then
> constructing the union of both number fields, converting both operands to
> that and performing the operation in there. But there is no reason why
> the number field for the result should be able to contain the operands. I
> guess dropping that is the main reason why direct resultant computations
> are faster.
>
> I propose that we try to build all binary operations on algebraic numbers
> on resultants instead of union fields. I furthermore propose that we try
> to build the equality comparison directly on resultants of two univariate
> polynomials, without bivariate intermediate steps.
>
> I can think of two possible problems. One is that we might be dealing
> with a special case in the example above, and that perhaps number field
> unions are in general cheaper than resultants. Another possible problem I
> can imagine is that the resultant could factor into several distinct
> polynomials, some of which might share a root. If that were the case,
> numeric refinement wouldn't be able to help choosing the right factor.
> Should we perhaps not factor the resultant polynomial, but instead
> compute roots for the fully expanded form?
>
> I'll try to come up with a branch which implements this approach.
New description:
This is a spin-off from comment:31:ticket:16964.
Many operations on algebraic numbers can become painfully slow. Most of
these operations can be expressed in terms of resultants, and surprisingly
the corresponding computations are sometimes ''way'' faster than what Sage
currently does. So much faster that I'm not sure whether to consider this
ticket here a request for enhancement, or even a defect.
Take for example the difference between two algebraic numbers `r1` and
`r2`, which are defined as follows:
{{{
sage: x = polygen(ZZ)
sage: p1 = x^5 + 6*x^4 - 42*x^3 - 142*x^2 + 467*x + 422
sage: p2 = p1((x-1)^2)
sage: r1 = QQbar.polynomial_root(p2, CIF(1, (2.1, 2.2)))
sage: r2 = QQbar.polynomial_root(p2, CIF(1, (2.8, 2.9)))
}}}
Computing their exact difference takes like forever:
{{{
sage: r4 = r1 - r2
sage: %time r4.exactify()
CPU times: user 2h 57min 1s, sys: 2.16 s, total: 2h 57min 3s
Wall time: 2h 57min 5s
}}}
On the other hand, computing a polynomial which has the difference as one
root can be achieved fairly easily using resultants, and the resulting
number is obtained in under one second:
{{{
sage: a,b = polygens(QQ, 'a,b')
sage: %time p3 = r1.minpoly()(a + b).resultant(r2.minpoly()(b), b)
CPU times: user 62 ms, sys: 0 ns, total: 62 ms
Wall time: 68 ms
sage: rs = [r for f in p3.factor()
....: for r in f[0].univariate_polynomial().roots(QQbar, False)
....: if r._value.overlaps(r1._value - r2._value)]
sage: assert len(rs) == 1
sage: r3, = rs
sage: %time r3.exactify()
CPU times: user 599 ms, sys: 0 ns, total: 599 ms
Wall time: 578 ms
}}}
One possible root of `p3` is `b=r2` and `a+b=r1` which means `a=r1-r2`. So
eliminating b we get a (reducible, not minimal) polynomial in a which has
that difference as one of its roots. I try to identify that by looking at
the roots `r` of the factors `f`, checking whether they overlap the
numeric interval.
The way I understand the current code, most exact binary operations are
implemented by exactifying both operands to number field elements, then
constructing the union of both number fields, converting both operands to
that and performing the operation in there. But there is no reason why the
number field for the result should be able to contain the operands. I
guess dropping that is the main reason why direct resultant computations
are faster.
I propose that we try to build all binary operations on algebraic numbers
on resultants instead of union fields. I furthermore propose that we try
to build the equality comparison directly on resultants of two univariate
polynomials, without bivariate intermediate steps.
I can think of two possible problems. One is that we might be dealing with
a special case in the example above, and that perhaps number field unions
are in general cheaper than resultants. Another possible problem I can
imagine is that the resultant could factor into several distinct
polynomials, some of which might share a root. If that were the case,
numeric refinement wouldn't be able to help choosing the right factor.
Should we perhaps not factor the resultant polynomial, but instead compute
roots for the fully expanded form?
I'll try to come up with a branch which implements this approach.
--
Comment (by gagern):
Including total CPU time for `r4.exactify()` using existing
implementation.
--
Ticket URL: <http://trac.sagemath.org/ticket/17886#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
