Changes between Version 3 and Version 6 of Ticket #18242


Ignore:
Timestamp:
04/20/15 10:51:06 (7 years ago)
Author:
pernici
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #18242

    • Property Cc mmezzarobba gagern added
    • Property Branch changed from to u/pernici/ticket/18242
    • Property Keywords qqbar resultant exactify minpoly added
    • Property Commit changed from to 99617e90a98946fb435481c39a9dbbf4afc1996a

  • Ticket #18242 – Description

    v3 v6  
    1   We implemented the algorithm for computing the composed sum and
     1  I implemented the algorithm for computing the composed sum and
    22  the composed product of univariate polynomials, presented in
    33
    … …  
    66    Journal of Symbolic Computation 41 (2006), 1-29
    77
    8   The composed sum algorithm is faster than using resultants;
     8  The composed sum algorithm is faster than using the resultant method;
    99  using it one of the  bottleneck in computing minimal polynomials is removed.
    1010
    11   The composed product is comparable to using resultants; they are usually both fast.
     11  The composed product is comparable to using the resultant method; they are usually both fast.
     12
     13Here is an example in which a fast algorithm for resultants makes a difference in timings:
     14
     15{{{
     16sage: from sage.calculus.calculus import minpoly
     17sage: ex = solve(x^4 + x^3 + sqrt(2)*x + 1 == 0, x)[0].rhs()
     18sage: time minpoly(ex, algorithm='algebraic')
     19Wall time: 6.81 s
     20x^8 + 2*x^7 + x^6 + 2*x^4 + 2*x^3 - 2*x^2 + 1
     21}}}
     22
     23in commit 12a1053f78c9efee9f3e6c88eb2c1c89d2db4312
     24it takes 31s; the difference in timings is in the computation of resultants.