Opened 6 years ago

Last modified 5 years ago

#18242 new enhancement

Use composed_op for QQbar exactification

Reported by: pernici Owned by:
Priority: major Milestone: sage-7.1
Component: number fields Keywords: qqbar resultant exactify minpoly
Cc: mmezzarobba, gagern Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/pernici/ticket/18242 (Commits, GitHub, GitLab) Commit: e0626dcabde6434cedd0c8736df198065b7a01d6
Dependencies: #17886 Stopgaps:

Status badges

Description (last modified by vdelecroix)

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.

Change History (16)

comment:1 Changed 6 years ago by pernici

  • Dependencies set to 17886

comment:2 Changed 6 years ago by pernici

  • Dependencies changed from 17886 to #17886

comment:3 Changed 6 years ago by pernici

  • Description modified (diff)
  • Summary changed from Added algorithm computing special resolvents to Added algorithm computing special resultants

comment:4 Changed 6 years ago by pernici

  • Branch set to u/pernici/ticket/18242
  • Created changed from 04/17/15 18:32:52 to 04/17/15 18:32:52
  • Modified changed from 04/17/15 19:11:10 to 04/17/15 19:11:10

comment:5 Changed 6 years ago by mmezzarobba

  • Cc mmezzarobba added
  • Commit set to 99617e90a98946fb435481c39a9dbbf4afc1996a

New commits:

db11616trac #17886: Compute binary operations using resultants.
8d4b91bReturn a descriptor, not an algebraic number.
234b2c4Choose roots field based on approximation field.
12a1053Name myself in list of authors
99617e9 Added algorithm computing special resultants.

comment:6 Changed 6 years ago by pernici

  • Cc gagern added
  • Description modified (diff)
  • Keywords qqbar resultant exactify minpoly added

comment:7 Changed 6 years ago by git

  • Commit changed from 99617e90a98946fb435481c39a9dbbf4afc1996a to 584f444a68d2afcd6eb955da5ba7b344df3e630c

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

5cf75a4eliminated a call to `roots`
584f444Fixed bug in `AlgebraicNumber.__pow__`.

comment:8 Changed 6 years ago by 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?

comment:9 Changed 6 years ago by git

  • Commit changed from 584f444a68d2afcd6eb955da5ba7b344df3e630c to f37f86d8ac9aebcdd248301454545a7235f7dc1a

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

f37f86dChanged test.

comment:10 Changed 6 years ago by git

  • Commit changed from f37f86d8ac9aebcdd248301454545a7235f7dc1a to e0626dcabde6434cedd0c8736df198065b7a01d6

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

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

comment:11 Changed 6 years ago by 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!
  1. 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)
  1. 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

comment:12 Changed 6 years ago by 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!

comment:13 follow-up: Changed 6 years ago by 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.

comment:14 in reply to: ↑ 13 ; follow-up: Changed 6 years ago by 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

comment:15 in reply to: ↑ 14 Changed 6 years ago by 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!

comment:16 Changed 5 years ago by vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-6.7 to sage-7.1
  • Summary changed from Added algorithm computing special resultants to Use composed_op for QQbar exactification

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

Note: See TracTickets for help on using tickets.