#16964: Speed up comparisons in QQbar
-------------------------------------+-------------------------------------
Reporter: gagern | Owner:
Type: defect | Status: needs_review
Priority: critical | Milestone: sage-6.5
Component: number fields | Resolution:
Keywords: variety qqbar cmp | Merged in:
singular | Reviewers:
Authors: Martin von Gagern | Work issues:
Report Upstream: N/A | Commit:
Branch: | e7acd96040fb43eebed0e3df0f1b1c7613d49bc1
u/gagern/ticket/16964 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Old description:
> 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:
>
> {{{
> File "sage/rings/polynomial/multi_polynomial_ideal.py", line 604, in
> __call__
> return self.f(self._instance, *args, **kwds)
> File "sage/rings/polynomial/multi_polynomial_ideal.py", line 2671, in
> variety
> V.sort()
> File "sage/rings/qqbar.py", line 3889, in __cmp__
> rcmp = cmp(self.real(), other.real())
> File "sage/rings/qqbar.py", line 4529, in __cmp__
> return self._sub_(other).sign()
> File "sage/rings/qqbar.py", line 4864, in sign
> return self.sign()
> File "sage/rings/qqbar.py", line 4867, in sign
> self.exactify()
> File "sage/rings/qqbar.py", line 3600, in exactify
> self._set_descr(self._descr.exactify())
> File "sage/rings/qqbar.py", line 7849, in exactify
> left.exactify()
> File "sage/rings/qqbar.py", line 3600, in exactify
> self._set_descr(self._descr.exactify())
> File "sage/rings/qqbar.py", line 7594, in exactify
> rv.exactify()
> File "sage/rings/qqbar.py", line 3600, in exactify
> self._set_descr(self._descr.exactify())
> File "sage/rings/qqbar.py", line 7849, in exactify
> left.exactify()
> File "sage/rings/qqbar.py", line 3600, in exactify
> self._set_descr(self._descr.exactify())
> File "sage/rings/qqbar.py", line 7851, in exactify
> gen = left._exact_field().union(right._exact_field())
> File "sage/rings/qqbar.py", line 2362, in union
> newpol, self_pol, k = pari_nf.rnfequation(my_factor, 1)
> File "gen.pyx", line 7454, in sage.libs.pari.gen.gen.rnfequation
> (build/cythonized/sage/libs/pari/gen.c:37964)
> File "handle_error.pyx", line 90, in
> sage.libs.pari.handle_error._pari_handle_exception
> (build/cythonized/sage/libs/pari/handle_error.c:1181)
> sage.libs.pari.gen.PariError: not enough precomputed primes
> }}}
>
> 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.
New description:
When 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.
Originally 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.
--
Comment (by gagern):
Changing description to turn focus from pari exception to performance.
Replying to [comment:11 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 URL: <http://trac.sagemath.org/ticket/16964#comment:13>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
