#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: | 885eb5d695818eeeed34362e37e5271960896c8b
u/vdelecroix/18356 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Marco Pernici, Vincent Delecroix', 'oldvalue': ''}):
* status: needs_info => needs_review
* author: => Marco Pernici, Vincent Delecroix
* branch: u/pernici/ticket/18356 => u/vdelecroix/18356
* milestone: sage-6.7 => sage-7.1
* commit: dcb3748ffdc3748b6968cf91c188f8ab266ab626 =>
885eb5d695818eeeed34362e37e5271960896c8b
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 the 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)`
New 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
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=51a383569dd40e300aef748a847ae3ddeb101885
51a3835]||{{{Trac 18356: composed_sum and composed_product for
polynomials}}}||
||[http://git.sagemath.org/sage.git/commit/?id=8c609a8a1c7cfbc34fe08984d2df82c862b006eb
8c609a8]||{{{Added `composed_op` replacing `composed_sum` and
`composed_product`.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=830d9a751b2fb4378ea841abfccfb273bfdffcb4
830d9a7]||{{{Trac 18356: various improvements and bug fixes}}}||
||[http://git.sagemath.org/sage.git/commit/?id=bef78f51e6d029356dcc4187f9e1a010e4bce3fe
bef78f5]||{{{Eliminated call to big_O}}}||
||[http://git.sagemath.org/sage.git/commit/?id=8fcbb1aa00349be3048fdf78c6dac4aba038c07c
8fcbb1a]||{{{Used `operator.add` instead of `+`.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=896f9bdcff469a2bc86847ac38e59fb408bcc9a2
896f9bd]||{{{Added checks on the input polynomials.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=81ec213e52d4b04a6d752d23d66eaa8bcd4941d1
81ec213]||{{{eliminated `newton_sum`}}}||
||[http://git.sagemath.org/sage.git/commit/?id=f720b8bab4b30d9db69f66a13ca5822aa9514d1d
f720b8b]||{{{Trac 18356: Eliminated `QQxy_with_gens`; added some
doctests.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=de9f0473c60325e54f53d112bd587790f646ecff
de9f047]||{{{Trac 18356: fix documentation}}}||
||[http://git.sagemath.org/sage.git/commit/?id=885eb5d695818eeeed34362e37e5271960896c8b
885eb5d]||{{{Trac 18356: do not use power series ring}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/18356#comment:36>
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.
