#853: Add a pslq implementation to Sage
--------------------------------------------+-------------------------------
Reporter: was | Owner: was
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-wishlist
Component: number theory | Keywords:
Author: Paul Zimmermann, Alex Ghitza | Upstream: N/A
Reviewer: David Kirkby | Merged:
Work_issues: need advice on interface |
--------------------------------------------+-------------------------------
Comment(by zimmerma):
I got some more information about PSLQ by David Bailey, who agreed that I
forward it to the Sage
developers (the references [1] and [2] are those from pslq-1.0.c):
{{{
Comments: Reference [1] in your note is the original PSLQ paper, but
the algorithm as presented there is quite cumbersome, as it involves
(needlessly) many full-matrix operations. Reference [2] stated an
abbreviated but equivalent version; unfortunately, however, it includes
one bug. Thus I strongly suggest that you base your implementation on
the following paper:
David H. Bailey and David J. Broadhurst, "Parallel Integer Relation
Detection: Techniques and Applications," /Mathematics of Computation/,
vol. 70, no. 236 (Oct 2000), pg. 1719-1736. Our preprint copy is
available at:
http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf
The basic PSLQ algorithm is stated on page 2, and should work well as
stated (please let me know if you have any problems). A two-level and a
three-level variant are also described, which are faster but quite a bit
more complicated.
However, if you are really serious, I suggest that you try the
"multi-pair" variant of PSLQ, which is presented in the above paper
beginning on page 10. Although we devised this scheme originally to be
suitable for parallel processing, we have found that even on a single
processor system it runs significantly faster, and is significantly more
effective in recovering relations when the input data is given only to
limited precision. Two- and a three-level variants of the multi-pair
scheme, in analogy to the two- and three-level versions of the regular
PSLQ, are also given in the paper. These are much faster than the basic
multi-pair PSLQ scheme, because they perform most operations using
ordinary double-precision arithmetic, updating the multi-precision
arrays only occasionally when needed.
In my own work, I always use the multi-pair PSLQ. I use the basic
multi-pair PSLQ for n up to 10 or 20 and for modest precision. For
larger n, and, say, 500-digit or more precision, I generally use
two-level multi-pair scheme. For truly "heroic" calculations (e.g., n >
100 and precision level > 2000 digits), I use the three-level multi-pair
scheme, since it has advantages for very large calculations and runs
well on a parallel system -- see some case studies mentioned in the
above paper.
Please let me know if it works for you. And if you have any questions,
I would be pleased to respond. If you wish, you can look at the
implementations of PSLQ and the multi-pair PSLQ schemes (in both C++ and
Fortran-90) that we have bundled with our ARPREC package:
http://crd.lbl.gov/~dhbailey/mpdist
}}}
I will try to modify my code to use the "basic PSLQ algorithm" described
in the paper
mentioned above. However in the short term I won't be able to implement
the multi-pair
variant. Thus if somebody wants to do it, please proceed. Alternatively,
one might use
the PSLQ variants from ARPREC (if the license is ok).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/853#comment:17>
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.
