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: sage-8.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:

Status badges

Description (last modified by mmezzarobba)

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 jdemeyer

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

# XXX need more caching here

comment:2 Changed 8 years ago by mmezzarobba

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 AlgebraicGenerators 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 follow-up: Changed 8 years ago by mmezzarobba

I asked Karim Belabas. Here is what I understand of his answer:

  • the cost of polredbest for a polynomial of degree n with coefficients of bit size B is roughly n^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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 7 years ago by gagern

  • 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=(x-1)^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 mmezzarobba

  • Authors set to Marc Mezzarobba
  • Branch set to u/mmezzarobba/qqbar_polred
  • Cc vdelecroix cheuberg added
  • Commit set to 653e939c1a8d7ae170ca540ba21c29aef7486066
  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-8.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 mmezzarobba

Replying to mmezzarobba:

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.

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 vdelecroix

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 follow-up: Changed 3 years ago by vdelecroix

Do you have some timings that make you decide about this threshold?

comment:12 in reply to: ↑ 11 Changed 3 years ago by mmezzarobba

Replying to vdelecroix:

Do you have some timings that make you decide about this threshold?

Nothing rigorous. But for instance, degree 40 with 30-bit coefficients seems to take a second or two, degree 60 (still with 30-bit coeffs) ~9s, and degree 80 more than 30s.

comment:13 Changed 3 years ago by git

  • 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 vdelecroix

  • Milestone changed from sage-8.6 to sage-8.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 vbraun

  • Branch changed from u/mmezzarobba/qqbar_polred to beb66ebbee4f61a7febfa3a27d6359ac39a62636
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.