Changes between Version 3 and Version 6 of Ticket #18242
 Timestamp:
 04/20/15 10:51:06 (7 years ago)
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 Weimplemented the algorithm for computing the composed sum and1 I implemented the algorithm for computing the composed sum and 2 2 the composed product of univariate polynomials, presented in 3 3 … … 6 6 Journal of Symbolic Computation 41 (2006), 129 7 7 8 The composed sum algorithm is faster than using resultants;8 The composed sum algorithm is faster than using the resultant method; 9 9 using it one of the bottleneck in computing minimal polynomials is removed. 10 10 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 13 Here is an example in which a fast algorithm for resultants makes a difference in timings: 14 15 {{{ 16 sage: from sage.calculus.calculus import minpoly 17 sage: ex = solve(x^4 + x^3 + sqrt(2)*x + 1 == 0, x)[0].rhs() 18 sage: time minpoly(ex, algorithm='algebraic') 19 Wall time: 6.81 s 20 x^8 + 2*x^7 + x^6 + 2*x^4 + 2*x^3  2*x^2 + 1 21 }}} 22 23 in commit 12a1053f78c9efee9f3e6c88eb2c1c89d2db4312 24 it takes 31s; the difference in timings is in the computation of resultants.