Changes between Initial Version and Version 8 of Ticket #15600


Ignore:
Timestamp:
12/23/18 08:02:36 (4 years ago)
Author:
mmezzarobba
Comment:

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

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #15600

    • Property Status changed from new to needs_review
    • Property Authors changed from to Marc Mezzarobba
    • Property Cc gagern vdelecroix cheuberg added
    • Property 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
    • Property Branch changed from to u/mmezzarobba/qqbar_polred
    • Property Milestone changed from sage-6.1 to sage-8.6
    • Property Commit changed from to 653e939c1a8d7ae170ca540ba21c29aef7486066
  • Ticket #15600 – Description

    initial v8  
    1 Zero-tests in `QQbar` and `AA` are very slow—slower than can be reasonably expected of exact computations with algebraic numbers IMHO.
     1`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.
    22
    3 On some examples, it turns out that 80% or more of the time is spent calling PARI's `polredbest`. The current implementation apparently calls `polredbest` each time exact computations in a new extension are required, which can be pretty expensive. It does so in the hope of finding a "nice" primitive element whose use will speed up subsequent computations (and perhaps also make the descriptions of the elements slightly more readable?), but otherwise my understanding is that this step is completely optional.
     3The reasons I can see to call `polredbest()` are:
     4* to limit the creation of isomorphic number fields (but with no guarantee that we'll avoid it completely),
     5* to speed up subsequent computations in these number fields,
     6* and perhaps also, in simple cases, to make the elements more readable.
     7None of these is worth letting simple computations hang forever.
    48
    5 Let's try to disable it except for small degrees (the value of `max_deg` was chosen to avoid changing the output of the tests in `qqbar.py`):
    6 {{{
    7 #!diff
    8 --- a/src/sage/rings/qqbar.py
    9 +++ b/src/sage/rings/qqbar.py
    10 @@ -1510,7 +1510,7 @@ def clear_denominators(poly):
    11      poly = poly(poly.parent().gen() / change)
    12      return change, poly
    13  
    14 -def do_polred(poly):
    15 +def do_polred(poly, max_deg=8):
    16      r"""
    17      Find a polynomial of reasonably small discriminant that generates
    18      the same number field as ``poly``, using the PARI ``polredbest``
    19 @@ -1554,9 +1554,12 @@ def do_polred(poly):
    20          sage: do_polred(x^4 - 4294967296*x^2 + 54265257667816538374400)
    21          (1/4*x, 4*x, x^4 - 268435456*x^2 + 211973662764908353025)
    22      """
    23 +    parent = poly.parent()
    24 +    if poly.degree() > max_deg:
    25 +        return parent.gen(), parent.gen(), poly
    26 +
    27      new_poly, elt_back = poly._pari_().polredbest(flag=1)
    28  
    29 -    parent = poly.parent()
    30      elt_fwd = elt_back.modreverse()
    31      return parent(elt_fwd.lift()), parent(elt_back.lift()), parent(new_poly)
    32  }}}
    33 Before (`master` as of a few days ago):
    34 {{{
    35     sage -t --long src/sage/rings/qqbar.py
    36         [1355 tests, 34.81 s]
    37     ----------------------------------------------------------------------
    38     All tests passed!
    39     ----------------------------------------------------------------------
    40     Total time for all tests: 35.2 seconds
    41         cpu time: 34.8 seconds
    42         cumulative wall time: 34.8 seconds
    43 }}}
    44 After:
    45 {{{
    46     sage -t --long src/sage/rings/qqbar.py
    47         [1355 tests, 6.09 s]
    48     ----------------------------------------------------------------------
    49     All tests passed!
    50     ----------------------------------------------------------------------
    51     Total time for all tests: 6.4 seconds
    52         cpu time: 6.1 seconds
    53         cumulative wall time: 6.1 seconds
    54 }}}
    55 
    56 Now these examples may not be representative of anything, and the above patch is a very naive solution. But it should certainly be possible to come up with a better strategy than calling `polredbest` every time!
     9This 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.