#18356: special resultants ``composed_sum`` and ``composed_product``
-------------------------------------+-------------------------------------
Reporter: pernici | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.1
Component: algebra | Resolution:
Keywords: | Merged in:
Authors: Marco Pernici, | Reviewers:
Vincent Delecroix | Work issues:
Report Upstream: N/A | Commit:
Branch: | bfb6379a8ab8b59d37cb99204f40322b911fab90
u/vdelecroix/18356 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Description changed by vdelecroix:
Old description:
> Add a new operation `composed_op` on polynomials to compute the composed
> sum, difference, product and division. Two implementations are proposed.
> The straightforward one using resultants and the algorithm from [BFSS].
> Currently, only polynomial with coefficient in `QQ` are supported. 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
New description:
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
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18356#comment:41>
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.
