#14239: symbolic radical expression for algebraic number
-------------------------------------+-------------------------------------
Reporter: gagern | Owner: davidloeffler
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.2
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: | Reviewers: Marc Mezzarobba
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/gagern/ticket/14239 | 039f4bf3bff139ce2630fe2fb8fd8f542096a498
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by gagern):
Thanks for explaining a bit of what's going on here to cause such delays.
Alternate ways to compute things more efficiently are all very well, but
won't be of use unless I can make this automatic somehow. After all, on
the high level all I do is compare two numbers, without wanting to think
about implementation details.
While investigating this problem, I noticed that for my original length
expression `b` the call `b.minpoly()` works ''really'' fast, whereas
`QQbar(b).minpoly()` takes ages. Makes me wonder whether the
exactification should be somehow based on the minimal polynomial of the
symbolic expression. Or at least leverage some of the machinery which
makes that so fast. That should speed up the kind of comparison I'm using.
Or is that computation somehow inexact?
Let me try to think this through. Naively I'd rewrite
`sage.symbolic.expression_conversions.algebraic` to first compute the
minpoly of the expression in question. I fear that this might take long,
which is a problem in those cases where we don't need the exact
representation. So it would probably be better to only do this on demand.
Which raises several related questions.
* Can we store a reference to a symbolic expression without having to
worry that it will get modified? Are symbolic expressions read-only after
construction?
* Can we afford the cost of storing whole symbolic expressions in addition
to their AA or QQbar converted forms? Or should we try to reconstruct the
symbolic expression from the descriptor DAG when needed?
* How do we link the symbolic expression with the algebraic number? We
could invent a descriptor which is layered around the one returned from
the current conversion approach, but whose `exactify` method will compute
the minimal polynomial of the whole expression instead of recursing.
* On the other hand, we might need access to the current interval, so an
alternative would be storing such information in `AlgebraicNumber_base`
and modify its `exactify` method to take the additional information into
account.
* Are there cases where a symbolic `minpoly` would take significantly more
time than the corresponding recursive `exactify`? If so, can we somehow
detect these cases before we start the symbolic `minpoly` computation?
* We need to find roots for that polynomial, which I'd so via a simple
`p.roots(self.parent(), False)` unless someone suggests otherwise.
* Wen need to compare them to the approximation returned by the nested
descriptor. Which is probably the main reason to have this in
`AlgebraicNumber_base` instead of some `ANDescr` descendant.
* We might have to increase precision until the interval contains no more
than a single solution. Simple with `AlgebraicNumber_base._more_precision`
but difficult or wasteful for `ANDescr`.
Does this approach make sense?
--
Ticket URL: <http://trac.sagemath.org/ticket/14239#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.
