#16222: Faster exactification using numeric minpoly
-------------------------------------+-------------------------------------
Reporter: gagern | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: Martin von Gagern | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/gagern/ticket/16222 | 998534a33a502a86518f6c541f99cac1ffacdaa5
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by gagern):
* status: needs_review => needs_work
Comment:
I find that it's hard to draw the line. Your example of `QQbar(sqrt(2)) +
1` shows that we want symbolic expressions for minpoly construction even
if some arguments were not explicitely constructed from symbolic
expressions. But where does it stop? In my demo implementation, I decided
that caching the symbolic expression after every elementary operation
would duplicate a lot of information. So I decided to recursively
construct such symbolic expressions. The result is pretty much a
construction of symbolic expressions from the descriptor dag, even though
I didn't think of it that way when I started coding. It can generate
symbolic expression for a lot of things.
And I'm using it unconditionally, which leads to a lot of doctests
failing. Some of them for better:
{{{
line 3653, rt3b.as_number_field_element():
Expected: … defining polynomial y^4 - 4*y^2 + 1, -a^2 + 2 …
Got: … defining polynomial y^2 - 3, a …
line 3755, rt2b._exact_value():
Expected: a^3 - 3*a where a^4 - 4*a^2 + 1 = 0 and a in 1.931851652578137?
Got: a where a^2 - 2 = 0 and a in 1.414213562373095?
line 7171, y.is_complex():
Expected: True
Got: False
}}}
But some of them for worse:
{{{
line 360, sage_input(n, verify=True):
Expected: AA(2)
Got: v = sqrt(AA(2))
v*v
line 7881, sage_input(n):
Expected: QQbar(sqrt(AA(2))) + 1
Got: v = sqrt(QQbar(3))
QQbar(sqrt(AA(2))) + v/v
}}}
I don't have any performance comparisons yet, but I guess that there might
well be cases where the current approach was fast enough, but the whole
detour via symbolic expressions, PARI's algdep and Maxima for verification
might have a severe impact.
So my key concern right now is, when do we want to use this approach, and
when not to? If multithreading in Python were a more natural concept, I'd
be so bold as to suggest that we start both approaches, and the one which
terminates first wins, aborting the other. This might make results
somewhat unpredictable, though. And given the state of threading support
in CPython, I doubt this is realistic in any case.
Here are a few more realistic ways how we could make that case
distinctions in a way that might make sense. I'm not completely happy with
any of them.
1. Only do the algdep approach if at least one number in the descriptor
dag originated from a symbolic expression
2. Limit the reconstruction of symbolic expressions to fewer operations,
mainly elementary arithmetic operations
3. Give control to the user: make exactification using algdep not part of
the normal exactification procedure, but instead the result of an explicit
method invocation
4. Try to detect exactifications which are likely very slow using the
standard approach, e.g. indicated by the expected size of the minpoly for
some union field, and try algdep only on those
--
Ticket URL: <http://trac.sagemath.org/ticket/16222#comment:14>
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.
