#16964: Speed up comparisons in QQbar
-------------------------------------+-------------------------------------
Reporter: gagern | Owner:
Type: defect | Status: positive_review
Priority: critical | Milestone: sage-6.5
Component: number fields | Resolution:
Keywords: variety qqbar cmp | Merged in:
singular | Reviewers: Vincent Delecroix
Authors: Martin von Gagern | Work issues:
Report Upstream: N/A | Commit:
Branch: | 3f4afef46ab6a042cb2678394031cb5c26d89b1a
u/vdelecroix/16964 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by gagern):
Replying to [comment:30 jdemeyer]:
> Using resultants, you can find a polynomial which has (a - b) as a root.
Up to now I had assumed that most arithmetic in QQbar would eventually be
performed using resultants. But it seems I was mistaken.
{{{
sage: x = polygen(ZZ)
sage: p1 = x^5 + 6*x^4 - 42*x^3 - 142*x^2 + 467*x + 422
sage: p2 = p1((x-1)^2)
sage: r1 = QQbar.polynomial_root(p2, CIF(1, (2.1, 2.2)))
sage: r2 = QQbar.polynomial_root(p2, CIF(1, (2.8, 2.9)))
sage: a,b = polygens(QQ, 'a,b')
sage: %time p3 = r1.minpoly()(a + b).resultant(r2.minpoly()(b), b)
CPU times: user 62 ms, sys: 0 ns, total: 62 ms
Wall time: 68 ms
sage: [r for f in p3.factor()
....: for r in f[0].univariate_polynomial().roots(QQbar, False)
....: if r._value.overlaps(r1._value - r2._value)]
[-0.7266314748516305?*I]
sage: %time p4 = (r1 - r2).minpoly()
}}}
One possible root of `p3` is `b=r2` and `a+b=r1` which means `a=r1-r2`. So
eliminating `b` we get a (reducible, not minimal) polynomial in `a` which
has that difference as one of its roots, just as you indicated. I try to
identify that by looking at the roots `r` of the factors `f`, checking
whether they overlap the numeric interval. The single result I obtain has
zero real part, thus indicating that we should sort by imaginary part.
I lost patience waiting for that final result of `p4`, which should do
pretty much the same thing in my opinion. My question is, why is it
computed the way it is? Why do arithmetic operators for algebraic numbers
compute some costly unions of number fields (which I believe is what they
are doing), instead of using resultants to describe their results? And
should we start some major rewrite effort to change that, i.e. to base
most if not all arithmetic operations on resultants?
I can think of two possible problems. One is that we might be dealing with
a special case here, and that perhaps number field unions are in general
cheaper than resultants. If that were the case, what does that mean for
speeding up comparisons? Another possible problem I can imagine is that
the resultant could factor into several distinct polynomials, some of
which might share a root. If that were the case, numeric refinement
wouldn't be able to help choosing the right factor. Should we perhaps not
factor the resultant polynomial, but instead compute roots for the fully
expanded form?
I get the impression that this might trigger some major work. I hope that
the reviewed changes can land as they are, while we investigate (in some
other branch) how to tackle this more generic approach.
--
Ticket URL: <http://trac.sagemath.org/ticket/16964#comment:31>
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.
