#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 gagern):
Replying to [comment:2 gagern]:
> The division `r1/r2` for the example from the ticket description still
takes extremely long. Surprisingly, the step which takes so long is not
the computation of the resultant, its factors or its roots. No, it's the
`candidate.exactify()` step which turns an `ANRoot` element into an
`ANExtensionElement`. The `do_polred` in there is taking ages. Any
suggestions how that might be avoided? It's “only” a degree 80 polynomial
we're dealing with.
I compared this with Mathematica. Apart from the fact that I prefer Sage's
way of presenting these numbers, I first
[http://mathematica.stackexchange.com/q/76413/8395 couldn't get
Mathematica] to do elementary arithmetic on these two numbers at all. But
using [http://mathematica.stackexchange.com/a/76423/8395 a different
approach], I managed to do so. In Mathematica the division takes about
twice as long as the other three operations, which makes sense considering
that the resulting minimal polynomial has twice the degree. But it's only
a distinction between 0.1 and 0.2 seconds, so there should be no
mathematically unavoidable reason why Sage takes as long as it takes.
Should we try to avoid polred completely? I have the impression that this
ticket here moves the focus away from “an algebraic number field extension
and some polynomial in its generator” towards “a defining polynomial and
an isolating interval”. The change is gradual, and we definitely want to
keep the former aspect available if we want to simplify cases where all
operations take place in the same number field. But since we no longer use
unions for all operations, the nice and small description of the field
generator appears to be less important. And the way I understand it,
`do_polred` is responsible for finding such a nice and small generator.
Should I try omitting that?
--
Ticket URL: <http://trac.sagemath.org/ticket/17886#comment:8>
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.
