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:  sage7.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: 
Description (last modified by )
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
 Dependencies set to 17886
comment:2 Changed 6 years ago by
 Dependencies changed from 17886 to #17886
comment:3 Changed 6 years ago by
 Description modified (diff)
 Summary changed from Added algorithm computing special resolvents to Added algorithm computing special resultants
comment:4 Changed 6 years ago by
 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
 Cc mmezzarobba added
 Commit set to 99617e90a98946fb435481c39a9dbbf4afc1996a
comment:6 Changed 6 years ago by
 Cc gagern added
 Description modified (diff)
 Keywords qqbar resultant exactify minpoly added
comment:7 Changed 6 years ago by
 Commit changed from 99617e90a98946fb435481c39a9dbbf4afc1996a to 584f444a68d2afcd6eb955da5ba7b344df3e630c
comment:8 Changed 6 years ago by
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
 Commit changed from 584f444a68d2afcd6eb955da5ba7b344df3e630c to f37f86d8ac9aebcdd248301454545a7235f7dc1a
Branch pushed to git repo; I updated commit sha1. New commits:
f37f86d  Changed test.

comment:10 Changed 6 years ago by
 Commit changed from f37f86d8ac9aebcdd248301454545a7235f7dc1a to e0626dcabde6434cedd0c8736df198065b7a01d6
Branch pushed to git repo; I updated commit sha1. New commits:
e0626dc  Added ```` and ``/`` operations using ``BFSS`` algorithm

comment:11 Changed 6 years ago by
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.
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 dop2 = ~R(p1)
you would avoid computing1/p1
in the fraction field.
 It would be faster to return
p3.truncate()
orres.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!
 In
hadamard_product
there is no need to build the list of coefficients. You can access the coefficients of a polynomialp
throughp[i]
. So just dodef 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)
composed_product
 you duplicated the code for
BFSS
... moreover if the argumentalgorithm
is neither"resultant"
nor"BFSS"
an error should be raised.
 I guess that the resultant method works in any characteristic?
Sided note: the BostanFlajoletSalvySchost deals with any characteristic. So it would be interesting to have a more general implementation.
Vincent
comment:12 Changed 6 years ago by
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 followup: ↓ 14 Changed 6 years ago by
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 ; followup: ↓ 15 Changed 6 years ago by
Hi Mario,
Replying to pernici:
Hello Vincent, I opened #18356 implementing
composed_sum
andcomposed_product
inpolynomial_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
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
 Description modified (diff)
 Milestone changed from sage6.7 to sage7.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.
New commits:
trac #17886: Compute binary operations using resultants.
Return a descriptor, not an algebraic number.
Choose roots field based on approximation field.
Name myself in list of authors
Added algorithm computing special resultants.