#17886: Faster qqbar operations using resultants
-------------------------------------+-------------------------------------
Reporter: gagern | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.6
Component: number fields | Resolution:
Keywords: qqbar resultant | Merged in:
exactify minpoly | Reviewers:
Authors: Martin von Gagern | Work issues:
Report Upstream: N/A | Commit:
Branch: | 12a1053f78c9efee9f3e6c88eb2c1c89d2db4312
u/gagern/ticket/17886 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by vdelecroix):
Replying to [comment:4 gagern]:
> One thing that has me worried are cyclotomics. If both arguments are
from cyclotomic fields, then we should do the union (which is fast in that
case) instead of the minpoly and resultant. I haven't figured out how best
to check for that case, though.
For cyclotomics, I really think that we should use the universal
cyclotomic field (and enhanced it):
{{{
sage: UCF = UniversalCyclotomicField()
sage: zeta3 = UCF.gen(3)
sage: zeta5 = UCF.gen(5)
sage: a = zeta3 + 2
sage: b = zeta5 + 1
sage: timeit("a*b")
625 loops, best of 3: 50.2 µs per loop
sage: a_QQbar = QQbar(a)
sage: b_QQbar = QQbar(b)
sage: timeit("a_QQbar*b_QQbar")
625 loops, best of 3: 13.2 µs per loop
sage: timeit("c = a_QQbar*b_QQbar; c.exactify()")
625 loops, best of 3: 774 µs per loop
}}}
> Another thing I fail is that test taken from that ARPREC paper. That
example is really fast in current implementation, precisely because it's
only operating in a single number field, so it doesn't really require any
unions at all. Should we try to detect this fact, i.e. see if both
arguments are either rational or elements of the same number field? My
failure is only later on, where the original code somehow magically knows
that the difference of two equal numbers is zero. I guess that if we did
introduce a special case for equal number field, we might get that for
free even though I don't know exactly how it works.
Definitely. If the two elements have the same parent (i.e. QQ, a number
field or UCF) we should perform the operation directly. Moreover, I hope
to have something fast for comparisons in a given number field #17830 that
would also speed up some comparisons in that case.
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/17886#comment:7>
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.
