Changes between Version 7 and Version 13 of Ticket #16964

Jan 26, 2015, 9:36:43 AM (8 years ago)
Martin von Gagern

Changing description to turn focus from pari exception to performance.

Replying to jdemeyer:

I like your general approach, but I have to check the details...

Have you found time for a closer look? Since this is currently the only ticket in the review queue with priority critical, perhaps we should try to get this into Sage 6.5?


  • Ticket #16964

    • Property Status changed from new to needs_review
    • Property Authors changed from to Martin von Gagern
    • Property Branch changed from to u/gagern/ticket/16964
    • Property Commit changed from to e7acd96040fb43eebed0e3df0f1b1c7613d49bc1
  • Ticket #16964 – Description

    v7 v13  
    1 I just spent 8 hours in an attempt to solve a polynomial system of equations using ideal.variety(). After these 8 hours I was left with the following error message:
     1When computing the variety of some ideal, then excessive amounts of time are apparently spent sorting the solutions. (In one example, the variety was essentially computed in 7½ hours but the sorting wasn't finished even 1½ hours after that.) This is due to the fact that comparison between complex algebraic numbers is done lexicographically, which means that quite often the real parts of complex conjugate numbers will have to be compared for equality, which can be a very costly operation.
    3 {{{
    4   File "sage/rings/polynomial/", line 604, in __call__
    5     return self.f(self._instance, *args, **kwds)
    6   File "sage/rings/polynomial/", line 2671, in variety
    7     V.sort()
    8   File "sage/rings/", line 3889, in __cmp__
    9     rcmp = cmp(self.real(), other.real())
    10   File "sage/rings/", line 4529, in __cmp__
    11     return self._sub_(other).sign()
    12   File "sage/rings/", line 4864, in sign
    13     return self.sign()
    14   File "sage/rings/", line 4867, in sign
    15     self.exactify()
    16   File "sage/rings/", line 3600, in exactify
    17     self._set_descr(self._descr.exactify())
    18   File "sage/rings/", line 7849, in exactify
    19     left.exactify()
    20   File "sage/rings/", line 3600, in exactify
    21     self._set_descr(self._descr.exactify())
    22   File "sage/rings/", line 7594, in exactify
    23     rv.exactify()
    24   File "sage/rings/", line 3600, in exactify
    25     self._set_descr(self._descr.exactify())
    26   File "sage/rings/", line 7849, in exactify
    27     left.exactify()
    28   File "sage/rings/", line 3600, in exactify
    29     self._set_descr(self._descr.exactify())
    30   File "sage/rings/", line 7851, in exactify
    31     gen = left._exact_field().union(right._exact_field())
    32   File "sage/rings/", line 2362, in union
    33     newpol, self_pol, k = pari_nf.rnfequation(my_factor, 1)
    34   File "gen.pyx", line 7454, in sage.libs.pari.gen.gen.rnfequation (build/cythonized/sage/libs/pari/gen.c:37964)
    35   File "handle_error.pyx", line 90, in sage.libs.pari.handle_error._pari_handle_exception (build/cythonized/sage/libs/pari/handle_error.c:1181)
    36 sage.libs.pari.gen.PariError: not enough precomputed primes
    37 }}}
    39 This is extremely annoying, since apparently the result of the computation was available at that point, and it was only sorting the result which failed.
     3Originally the computation even resulted in a Pari exception (“not enough precomputed primes”). This no longer occurs (since the pari upgrade from #15767). So the focus of this ticket is now the excessive amount of time required for comparisons, even without an exception.