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), 1-29 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.