#18242: Use composed_op for QQbar exactification
-------------------------------------+-------------------------------------
Reporter: pernici | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-7.1
Component: number fields | Resolution:
Keywords: qqbar resultant | Merged in:
exactify minpoly | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | e0626dcabde6434cedd0c8736df198065b7a01d6
u/pernici/ticket/18242 | Stopgaps:
Dependencies: #17886 |
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* milestone: sage-6.7 => sage-7.1
Old description:
> I implemented the algorithm for computing the composed sum and
> the composed product of univariate polynomials, presented in
>
> A. Bostan, P. Flajolet, B. Salvy and E. Schost,
> "Fast Computation of special resultants",
> Journal of Symbolic Computation 41 (2006), 1-29
>
> The composed sum algorithm is faster than using the resultant method;
> using it one of the bottleneck in computing minimal polynomials is
> removed.
>
> The composed product is comparable to using the resultant method; they
> are usually both fast.
>
> Here is an example in which a fast algorithm for resultants makes a
> difference in timings:
>
> {{{
> sage: from sage.calculus.calculus import minpoly
> sage: ex = solve(x^4 + x^3 + sqrt(2)*x + 1 == 0, x)[0].rhs()
> sage: time minpoly(ex, algorithm='algebraic')
> Wall time: 6.81 s
> x^8 + 2*x^7 + x^6 + 2*x^4 + 2*x^3 - 2*x^2 + 1
> }}}
>
> in commit 12a1053f78c9efee9f3e6c88eb2c1c89d2db4312
> it takes 31s; the difference in timings is in the computation of
> resultants.
New description:
In #18356, is implemented an algorithm for computing the composed sum,
difference, product and division of two polynomials. That can be used to
fasten exactification in QQbar.
See also #17886.
---------------------------
From the older description
Here is an example in which a fast algorithm for resultants makes a
difference in timings:
{{{
sage: from sage.calculus.calculus import minpoly
sage: ex = solve(x^4 + x^3 + sqrt(2)*x + 1 == 0, x)[0].rhs()
sage: time minpoly(ex, algorithm='algebraic')
Wall time: 6.81 s
x^8 + 2*x^7 + x^6 + 2*x^4 + 2*x^3 - 2*x^2 + 1
}}}
in commit 12a1053f78c9efee9f3e6c88eb2c1c89d2db4312
it takes 31s; the difference in timings is in the computation of
resultants.
--
Comment:
To me, it would make more sense to use directly `composed_op` in #17886
and close this ticket as duplicate.
--
Ticket URL: <http://trac.sagemath.org/ticket/18242#comment:16>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
