Opened 8 years ago
Closed 3 years ago
#15600 closed defect (fixed)
Skip polredbest() for large extensions in exact computations in QQbar
Reported by:  mmezzarobba  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  performance  Keywords:  
Cc:  jdemeyer, gagern, vdelecroix, cheuberg  Merged in:  
Authors:  Marc Mezzarobba  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  beb66eb (Commits, GitHub, GitLab)  Commit:  beb66ebbee4f61a7febfa3a27d6359ac39a62636 
Dependencies:  Stopgaps: 
Description (last modified by )
QQbar
and AA
are very slow, to the point of often being unusable. There are many reasons to that (see #18333), including computations being triggered when they shouldn't, internal operations that construct elements of large degree, and incomplete of caching in some places. Yet the most visible issue by far is that, each time a new extension is constructed internally, we try to optimize its representation using PARI's polredbest()
. This is bad, since polredbest()
can easily take days for moderately large extensions, and only made worse by other issues that lead to lots of large extensions being created.
The reasons I can see to call polredbest()
are:
 to limit the creation of isomorphic number fields (but with no guarantee that we'll avoid it completely),
 to speed up subsequent computations in these number fields,
 and perhaps also, in simple cases, to make the elements more readable.
None of these is worth letting simple computations hang forever.
This ticket restricts the optimization step using polredbest()
to cases where (based on the size of the defining polynomial) it can be expected to finish in reasonable time.
Change History (15)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
I agree that QQbar also needs more caching. (And not only in the marked places. For instance, look how many times nfinit
is called by sage_input(pol.roots(...,ring=QQbar), verify=True)
: it seems to me that lots of expensive purely algebraic computations could be performed only once when we have AlgebraicGenerator
s corresponding to several roots of the same irreducible polynomial.)
But even with caching, is it reasonable to spend tens of seconds optimizing the representation of an extension that may be used only once to check that some expression is zero?
comment:3 followup: ↓ 9 Changed 8 years ago by
I asked Karim Belabas. Here is what I understand of his answer:
 the cost of
polredbest
for a polynomial of degreen
with coefficients of bit sizeB
is roughlyn^5 B^2
;  the best it can do is to reduce the cost of subsequent computations in the extension by a factor of roughly
B^2
;  it is essentially never worth calling it on polynomials of moderately large degree;
 ...except before performing very expensive operations (typically
bnfinit()
) on the extension, when there is reason to expect that it will find a defining polynomial of very small height.
On a related note, I noticed that QQbar
often calls polredbest
on polynomials of the form p(x^k)
where k
can be pretty large. Karim suggested that the Pari function rnfpolredbest
could be useful in this case.
comment:4 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:6 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:7 Changed 7 years ago by
 Cc gagern added
I agree that dropping that function seems a reasonable approach to the problem at hand. In particular, if we follow the idea from #17886 then operations within a single number field would become even rarer, so the benefit of a reduced basis would be less as well.
As a middle ground, it might be possible to do the reduction lazily, once it looks as if there would be a sufficient number of operations performed in the same number field to justify the time spent for this computation. But since implementing this could be a major effort, I'm not really suggesting this approach, just mentioning it as an idea if there is too much objection to dropping the reduction altogether.
Here is one example which doesn't complete in over 6 hours, due to the call to polredbest
. I had this as the motivating example for #17896 which looks like a duplicate of this one here.
sage: x,y = polygens(QQ,"x,y") sage: p1 = x^5 + 6*x^4  42*x^3  142*x^2 + 467*x + 422 sage: p2 = p1(x=(x1)^2) sage: p3 = p2(x=x*y).resultant(p2,x).univariate_polynomial() sage: p4, = [f[0] for f in p3.factor() if f[0].degree() == 80] sage: ival = CIF((0.77, 0.78), (0.08, 0.07)) sage: z, = [r for r in p4.roots(QQbar, False) if r in ival] sage: %time z.exactify()
comment:8 Changed 3 years ago by
 Branch set to u/mmezzarobba/qqbar_polred
 Cc vdelecroix cheuberg added
 Commit set to 653e939c1a8d7ae170ca540ba21c29aef7486066
 Description modified (diff)
 Milestone changed from sage6.4 to sage8.6
 Status changed from new to needs_review
 Summary changed from Exact computations in QQbar spend unreasonable amounts of time in do_polred to Skip polredbest() for large extensions in exact computations in QQbar
I'd like to revive this ticket. It's been five years, and (in spite of a bit of progress on related issues), there is still no other viable solution. While the change suggested here will not make QQbar very fast, it can at least make it usable.
New commits:
653e939  #15600 qqbar: don't run polredbest on large extensions

comment:9 in reply to: ↑ 3 Changed 3 years ago by
Replying to mmezzarobba:
On a related note, I noticed that
QQbar
often callspolredbest
on polynomials of the formp(x^k)
wherek
can be pretty large.
As we realized with Pascal Molin, this is related in particular to #26898. What used to happen is that hashing an algebraic number α would trigger the exact computation, not just of α itself, but of the real and imaginary parts of α + β for some β ∈ ℚ[i]...
comment:10 Changed 3 years ago by
Just a copy of the example in #21095 that never terminates
sage: x = polygen(ZZ) sage: p = 67*x^4  33*x^3 + 94*x^2  30*x + 57 sage: r = p.roots(QQbar, multiplicities=False) sage: r[0].abs().exactify() # < takes forever
comment:11 followup: ↓ 12 Changed 3 years ago by
Do you have some timings that make you decide about this threshold?
comment:12 in reply to: ↑ 11 Changed 3 years ago by
Replying to vdelecroix:
Do you have some timings that make you decide about this threshold?
Nothing rigorous. But for instance, degree 40 with 30bit coefficients seems to take a second or two, degree 60 (still with 30bit coeffs) ~9s, and degree 80 more than 30s.
comment:13 Changed 3 years ago by
 Commit changed from 653e939c1a8d7ae170ca540ba21c29aef7486066 to beb66ebbee4f61a7febfa3a27d6359ac39a62636
Branch pushed to git repo; I updated commit sha1. New commits:
beb66eb  #15600 missing encoding declaration

comment:14 Changed 3 years ago by
 Milestone changed from sage8.6 to sage8.7
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
This is a good move! Thanks.
comment:15 Changed 3 years ago by
 Branch changed from u/mmezzarobba/qqbar_polred to beb66ebbee4f61a7febfa3a27d6359ac39a62636
 Resolution set to fixed
 Status changed from positive_review to closed
I don't think this is the right solution, using caching would be a better idea I think. In fact, in the code there are various places with