Use composed_op for QQbar exactification

[sagetrac-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.

Depends on #17886

CC: @mezzarobba @gagern

Component: number fields

Keywords: qqbar resultant exactify minpoly

Branch/Commit: u/pernici/ticket/18242 @ e0626dc

Issue created by migration from https://trac.sagemath.org/ticket/18242

[sagetrac-pernici]

Dependencies: 17886

[sagetrac-pernici]

Changed dependencies from 17886 to #17886

[sagetrac-pernici]

Branch: u/pernici/ticket/18242

[mezzarobba]

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.

[mezzarobba]

Commit: 99617e9

[sagetrac-pernici]

Changed keywords from none to qqbar resultant exactify minpoly

[sagetrac-git]

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

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

[sagetrac-git]

Changed commit from 99617e9 to 584f444

[videlec]

comment:8

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?

[sagetrac-git]

Changed commit from 584f444 to f37f86d

[sagetrac-git]

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

f37f86d

Changed test.

[sagetrac-git]

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

e0626dc

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

[sagetrac-git]

Changed commit from f37f86d to e0626dc

[videlec]

comment:11

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

[videlec]

comment:12

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!

[sagetrac-pernici]

comment:13

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.

[videlec]

comment:14

Hi Mario,

Replying to @sagetrac-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

[videlec]

comment:15

Replying to @videlec:

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!

[videlec]

comment:16

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