#18356: special resultants ``composed_sum`` and ``composed_product``
-------------------------------------+-------------------------------------
Reporter: pernici | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.7
Component: algebra | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/pernici/ticket/18356 | 5f888c83095eab89acbd96ee09e067918a60c258
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by pernici:
Old description:
> Added `composed_op` to compute the composed sum and the composed product,
> implementing
> the algorithm in A. Bostan, P. Flajolet, B. Salvy and E. Schost,
> "Fast Computation of special resultants",
> Journal of Symbolic Computation 41 (2006), 1-29
> in the case of polynomials on integer or rational ring.
> 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, '+')
> Wall time: 105 ms
> sage: time r2 = p1.composed_op(p2, '+', algorithm="resultant")
> Wall time: 53.4 s
> sage: r1 == r2.monic()
> sage: r1.is_irreducible()
> True
> }}}
>
> so `r1` is the minimal polynomial of `cos(pi/43) + cos(pi/47)`
New description:
Added `composed_op` to compute the composed sum and the composed product,
implementing
the algorithm in A. Bostan, P. Flajolet, B. Salvy and E. Schost,
"Fast Computation of special resultants",
Journal of Symbolic Computation 41 (2006), 1-29
in the case of polynomials on integer or rational ring.
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)
Wall time: 105 ms
sage: time r2 = p1.composed_op(p2, operator.add, algorithm="resultant")
Wall time: 53.4 s
sage: r1 == r2
sage: r1.is_irreducible()
True
}}}
so `r1` is the minimal polynomial of `cos(pi/43) + cos(pi/47)`
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18356#comment:16>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
