Use composed_op for QQbar exactification

[pernici]

In #18356, is implemented an algorithm for computing the composed sum, difference, product and division of two polynomials. That can be used to fasten exactification in QQbar.

See also #17886.

---

From the older description

Here is an example in which a fast algorithm for resultants makes a difference in timings:

sage: from sage.calculus.calculus import minpoly
sage: ex = solve(x^4 + x^3 + sqrt(2)*x + 1 == 0, x)[0].rhs()
sage: time minpoly(ex, algorithm='algebraic')
Wall time: 6.81 s
x^8 + 2*x^7 + x^6 + 2*x^4 + 2*x^3 - 2*x^2 + 1

in commit 12a1053f78c9efee9f3e6c88eb2c1c89d2db4312 it takes 31s; the difference in timings is in the computation of resultants.

[mmezzarobba]

New commits:

​db11616	trac #17886: Compute binary operations using resultants.
​8d4b91b	Return a descriptor, not an algebraic number.
​234b2c4	Choose roots field based on approximation field.
​12a1053	Name myself in list of authors
​99617e9	Added algorithm computing special resultants.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5cf75a4	eliminated a call to `roots`
​584f444	Fixed bug in `AlgebraicNumber.__pow__`.

[vdelecroix]

What does the following test from ​584f444 is doing in sage.rings.qqbar!?

sage: from sage.calculus.calculus import minpoly
sage: x = SR.var('x')
sage: ex = solve(x^4 + x + 1 == 0, x)[0].rhs()
sage: minpoly(ex, algorithm='algebraic')
x^4 + x + 1

Why isn't it in sage.calculus.calculus?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f37f86d

Changed test.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e0626dc

Added ``-`` and ``/`` operations using ``BFSS`` algorithm

[vdelecroix]

Hello,

This ticket is still in state "new" but here are some remarks.

I would make this ticket independent of #17886 and ignore completely the potential application to QQbar (considering it in another ticket). It would be more flexible that way.

You implemented functions but I guess some of them would better be methods over polynomials (that is methods of polynomial.polynomial_element.Polynomial). For example, the hadamard_product or even the composed_sum. So move them. For _hadamard_exp it is only well defined in zero characteristic, so I am not sure what is the most appropriate; what do you think?

Did you do some serious benchmark to see which methods is faster depending on p1 and p2? I guess it might aslo depends on the sparseness of the polynomials, the size of the coefficients.

1. newton_sum

• I would rather add the power series ring object R as an argument. Building a ring is always costly.

• In

  p2 = R(QQ(1)/p1)
  

  You would better do

  p2 = ~R(p1)
  

  you would avoid computing 1/p1 in the fraction field.

• It would be faster to return p3.truncate() or res.truncate() instead of adding a truncation argument

• the argument name typ is horrible. Be more explicit about what it is. "a related expression" is not an explanation of the output!

2. In hadamard_product there is no need to build the list of coefficients. You can access the coefficients of a polynomial p through p[i]. So just do

   def hadamard_product(p1, p2):
       R = p1.parent()
       return R([p1[i]*p2[i] for i in range(min(p1.degree(), p2.degree())+1)])
   

   (I recall that this function must move as a method of univariate polynomials)

3. composed_product

• you duplicated the code for BFSS... moreover if the argument algorithm is neither "resultant" nor "BFSS" an error should be raised.

• I guess that the resultant method works in any characteristic?

Sided note: the Bostan-Flajolet-Salvy-Schost deals with any characteristic. So it would be interesting to have a more general implementation.

Vincent

[vdelecroix]

Note: I opened #18333 as a "task ticket" for the global cleaning of QQbar. Any comments, suggestions and reviews of tickets mentioned there are welcome!

[pernici]

Hello Vincent, I opened #18356 implementing composed_sum and composed_product in polynomial_element.pyx, taking into account most of your comments.

"hadamard_exp" appears as a method raising an exception if the polynomial is not on rationals.

I suspect that newton_sum method is not efficient, and it might be somewhere else in Sage. As long as it is called by composed_sum, the time spent in newton_sum is negligible.

There is a small benchmark test, confirming the fact that the "BFSS" algorithm is asymptotically faster.

I do not plan to look at the "BFSS" algorithm in any characteristics.

I do not think I will open another ticket before #18356 is merged, because I do not know how to manage tickets depending on other tickets, or how to add the dependence on both #17886 and #18356.

[vdelecroix]

Hi Mario,

Replying to pernici:

Hello Vincent, I opened #18356 implementing composed_sum and composed_product in polynomial_element.pyx, taking into account most of your comments.

What is the intersection between this ticket and #18356? I think from now it is better to discuss on #18356 right?

I do not plan to look at the "BFSS" algorithm in any characteristics.

This is fine. Just add a NOTE somewhere like

.. NOTE::

    The BFSS algorithm could be implemented in any characteristic but it currently only works in characteristic zero (see paper XYZ).

I do not think I will open another ticket before #18356 is merged, because I do not know how to manage tickets depending on other tickets, or how to add the dependence on both #17886 and #18356.

Tickets depending on other tickets have two flavour:

• from the trac point of view, this is just logical order (you just have to fill the dependency field in the ticket description)
• from the git point of view, if X depends on Y, it means that the branch of Y is based on top of X

You are free to rebase git branch on other git branches. Or change the git branch on some ticket to some other branch.

Vincent

[vdelecroix]

Replying to vdelecroix:

I do not plan to look at the "BFSS" algorithm in any characteristics.

This is fine. Just add a NOTE somewhere like

Ha nice. It is already there!

[vdelecroix]

To me, it would make more sense to use directly composed_op in #17886 and close this ticket as duplicate.