#6084: [needs work] Improved p-adic polynomials
---------------------------+------------------------------------------------
Reporter: roed | Owner: roed
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-4.7.1
Component: padics | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: David Roe
Merged: | Dependencies:
---------------------------+------------------------------------------------
Comment(by roed):
I will build a copy of 4.7.1.alpha2 overnight and port the patches to
there.
The key idea of this patch is that a polynomial over Zp should not be
stored as a list of coefficients, but instead as an element of ZZ[x],
together with some sort of precision object that records the precision to
which each coefficient is known. There are two main benefits of this
approach:
1. One can use fast algorithms for things like polynomial multiplication,
rather than being forced back on naive multiplication due to a desire to
preserve precision. For example, Karatsuba multiplication uses the
identity
(f,,0,, + x^n^ f,,1,,) (g,,0,, + x^n^ g,,1,,) = (f,,0,, g,,0,,) + (f,,1,,
g,,1,,) x^2n^ + ((f,,0,, + f,,1,,)(g,,0,, + g,,1,,) - f,,0,, g,,0,, -
f,,1,, g,,1,,)x^n^
This can lose precision over the naive definition since there are more
additions than needed. But if one computes an approximation over ZZ and
then determines precision separately, one can use Karatsuba or FFT
algorithms at will.
1. If one wants to use different methods for tracking precision (see
below), the separation makes the implementation more modular and thus
easier to implement and maintain.
These patches implement two kinds of polynomials: an anchored polynomial
type which stores an approximation (in ZZ[x] for example) and a precision
object, and a floating polynomial type which stores a common power of p
for all the coefficients together with an anchored polynomial (thus
allowing polynomials over Qp).
There are three kinds of precision defined so far:
* Flat precision. The precision of every entry is just a constant value
n. This is certainly the fastest option, and frequently is perfectly
adequate.
* Jagged precision. Each coefficient has its own precision, subject only
to the precision cap of the base ring. This is mainly for backward
compatibility, but might also be useful in generating functions (maybe?).
* Newton precision. The Newton polygon of the polynomial and of the
precision are stored. This is the default precision type, since it
provides a compromise between the previous two types, and having precision
above the Newton polygon is useless for evaluating the polynomial anyway.
I'll write more about the contents of the individual patches and some more
of the contents tomorrow morning.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6084#comment:16>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
