id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
18356 special resultants ``composed_sum`` and ``composed_product`` mario pernici "Add a new operation `composed_op` on polynomials to compute the composed sum, difference, product and division of two polynomias. That is the polynomial whose roots are the sum (resp. difference, product, division) of the roots of the two polynomials.
Two implementations are proposed. The straightforward one using resultants and the algorithm from [BFSS]. For the latter algorithm, only polynomial with coefficient in `ZZ` or `QQ` are supported. However, this algorithm is asymptotically faster than using the `resultant` method.
For instance
{{{
sage: p1 = minpoly(cos(pi/43))
sage: p2 = minpoly(cos(pi/47))
sage: time r1 = p1.composed_op(p2, operator.add)
CPU times: user 108 ms, sys: 4 ms, total: 112 ms
Wall time: 111 ms
sage: time r2 = p1.composed_op(p2, operator.add, algorithm=""resultant"")
CPU times: user 47.1 s, sys: 0 ns, total: 47.1 s
Wall time: 47.1 s
sage: r1 == r2
True
sage: r1.is_irreducible()
True
}}}
In the example above, `r1` is the minimal polynomial of `cos(pi/43) + cos(pi/47)`
Reference:
[BFSS] A. Bostan, P. Flajolet, B. Salvy and E. Schost, ""Fast Computation of special resultants"", Journal of Symbolic Computation 41 (2006), 1-29" enhancement closed major sage-7.3 algebra fixed Mario Pernici, Vincent Delecroix Vincent Delecroix, Marc Mezzarobba N/A c6b1c35de85957fc501d6f34b4de6b8def0a8ea0