Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Analysis of PSLQ,
an integer relation finding algorithm


Authors: Helaman R. P. Ferguson, David H. Bailey and Steve Arno
Journal: Math. Comp. 68 (1999), 351-369
MSC (1991): Primary 11A05, 11Y16, 68--04
DOI: https://doi.org/10.1090/S0025-5718-99-00995-3
MathSciNet review: 1489971
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let ${\mathbb{K}}$ be either the real, complex, or quaternion number system and let ${\mathbb{O}}({\mathbb{K}})$ be the corresponding integers. Let $ x = (x_{1}, \hdots , x_{n})$ be a vector in ${\mathbb{K}}^{n}$. The vector $x$ has an integer relation if there exists a vector $m = (m_{1}, \hdots , m_{n}) \in {\mathbb{O}}({\mathbb{K}})^{n}$, $m \ne 0$, such that $m_{1} x_{1} + m_{2} x_{2} + \ldots + m_{n} x_{n} = 0$. In this paper we define the parameterized integer relation construction algorithm PSLQ$(\tau )$, where the parameter $\tau $ can be freely chosen in a certain interval. Beginning with an arbitrary vector $x = (x_{1}, \hdots , x_{n}) \in {\mathbb{K}}^{n}$, iterations of PSLQ$(\tau )$ will produce lower bounds on the norm of any possible relation for $x$. Thus PSLQ$(\tau )$ can be used to prove that there are no relations for $x$ of norm less than a given size. Let $M_{x}$ be the smallest norm of any relation for $x$. For the real and complex case and each fixed parameter $\tau $ in a certain interval, we prove that PSLQ$(\tau )$ constructs a relation in less than $O(n^{3} + n^{2} \log M_{x})$ iterations.


References [Enhancements On Off] (What's this?)

  • 1. Steve Arno and Helaman Ferguson, A new polynomial time algorithm for finding relations among real numbers, Supercomputing Research Center Tech Report SRC-93-093 (March 1993), 1-13.
  • 2. D. H. Bailey and H. R. P. Ferguson, A polynomial time, numerically stable integer relation algorithm, SRC Technical Report SRC-TR-92-066; RNR Technical Report RNR-91-032 (16 December 1991; 14 July 1992), 1-14.
  • 3. D. H. Bailey, J. Borwein, and R. Girgensohn, Experimental evaluation of Euler sums, Experimental Mathematics 3 (October 1994), 17 - 30. MR 96e:11168
  • 4. D. H. Bailey, P. Borwein, and S. Plouffe, On the rapid computation of various polylogarithmic constants, Mathematics of Computation 66 (218) (April 1997), 903 - 913. CMP 97:06
  • 5. D. H. Bailey, Numerical results on the transcendence of constants involving $\pi $, $e$, and Euler's constant, Mathematics of Computation 50 (181) (January 1988), 275 - 281. MR 88m:11056
  • 6. D. H. Bailey, Multiprecision translation and execution of Fortran programs, ACM Transactions on Mathematical Software 19 (3) (1993), 288 - 319.
  • 7. D. H. Bailey, A Fortran-90 based multiprecision system, ACM Transactions on Mathematical Software 21 (4) (1995), 379 - 387..
  • 8. G. Bergman, Notes on Ferguson and Forcade's generalized Euclidean algorithm, University of California at Berkeley, unpublished notes, Nov. 1980.
  • 9. V. Brun, En generalisatiken av kjedebroøken, I, II, Norske Videnskapsselskapets Skrifter I. Matematisk Naturvidenskapelig Klasse 6 (1919, 1920), 1-29, 1-24.
  • 10. V. Brun, Algorithmes euclidiens pour trois et quatre nombres, Treizième Congrès des mathematiciens Scandinaves, tenu a Helsinki 18-23 août 1957, Mercators Trycheri, Helsinki, 1958, pp. 46-64. MR 22:2597
  • 11. H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer-Verlag, Berlin Heidelberg New York, 1993. MR 94i:11105
  • 12. M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr, J. Stern, Improved low-density subset sum algorithms, Computational Complexity 2 (1992), no. 2, 111-128. MR 94e:11141
  • 13. Euclid, translated from the text of Heiberg with introduction and commentary by Sir Thomas L. Heath, The Thirteen Books of Euclid's Elements, Second Edition, revised with additions, unabridged, Volumes I, II, III, Dover Publications, Inc., New York, 1956. MR 17:814b
  • 14. H. R. P. Ferguson and R. W. Forcade, Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two, Bulletin (New Series) of the American Mathematical Society 1 (1979), 912 - 914. MR 80i:11039
  • 15. H. R. P. Ferguson and R. W. Forcade, Multidimensional Euclidean algorithms, (Crelle's) Journal für die reine und angewandte Mathematik 334 (1982), 171 - 181. MR 84d:10015
  • 16. Helaman Ferguson, A short proof of the existence of vector Euclidean algorithms, Proceedings of the American Mathematical Society 97 (1) (May 1986), 8 - 10. MR 87k:11080
  • 17. Helaman Ferguson, A noninductive $GL(n,Z)$ algorithm that constructs integral linear relations for $n$ $Z$-linearly dependent real numbers, Journal of Algorithms (8) (1987), 131 - 145. MR 88h:11096
  • 18. Helaman Ferguson, PSOS: A new integral relation finding algorithm involving partial sums of squares and no square roots, Abstracts of papers presented to the American Mathematical Society 9 (56; 88T-11-75) (March 1988), 214.
  • 19. Rodney W. Forcade, Brun's algorithm, unpublished manuscript (November 1981), 1 - 27.
  • 20. David Fowler, Ratio in early Greek mathematics, Bulletin (New Series) of the American Mathematical Society 1 (6) (November 1979), 807 - 846. MR 82c:01008
  • 21. G. H. Golub and C. F. Van Loan, Matrix Computations, 2nd Edition, The Johns Hopkins University Press, Baltimore, Maryland, 1990. MR 90d:65055
  • 22. C. Hermite, Extraits de lettres de M. Ch. Hermite à M. Jacobi sur differénts objets de la théorie de nombres, (Crelle's) Journal für die Reine und Angewandte Mathematik (3, 4) (1850), 261 - 315.
  • 23. J. Hastad, B. Just, J. C. Lagarias, and C. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM Journal of Computing 18 (1989), 859 - 881. MR 90g:11171
  • 24. C. G. J. Jacobi, Allgemeine Theorie der Kettenbruchahnlichen Algorithmen, in welchen jede Zahl aus drei vorhergehenden gebildet wird (Aus den hinterlassenen Papieren von C. G. J. Jacobi mitgetheilt durch Herrn E. Heine.), Journal für die Reine und Angewandte Mathematik 69 (1) (1868), 29 - 64.
  • 25. R. Kannan, Lattices, basis reduction, and the shortest vector problem, Theory of Algorithms (Pécs, 1984), Colloquia Mathematica Societatis János Bolyai, vol. 44, North-Holland, Amsterdam, 1985, pp. 283-311. MR 87m:90087
  • 26. D. E. Knuth, The Art of Computer Programming, Vol. 2 Seminumerical Algorithms, Second Edition, Addison-Wesley, Reading, MA, 1981. MR 83i:68003
  • 27. J. C. Lagarias, H. W. Lenstra Jr., and C. P. Schnorr, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica 10 (4) (1990), 333 - 348. MR 92a:11075
  • 28. A. K. Lenstra, H. W. Lenstra Jr., and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515 - 534. MR 84a:12002
  • 29. Laszlo Lovasz and Herbert E. Scarf, The generalized basis reduction algorithm, Mathematics of Operations Research 17 (3) (August 1992), 751 - 764. MR 93h:52023
  • 30. O. Perron, Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus, Math. Ann. (64) (1907), 1 - 76.
  • 31. M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Chapter 3: Methods from the Geometry of Numbers, Encyclopedia of Mathematics and its Applications, Cambridge University Press, New York, 1989. MR 92b:11074
  • 32. H. Poincaré, Sur une généralisation des fractions continues, Comptes Rendus Acad. Sci. Paris 99 (1884), 1014 - 1016.
  • 33. Asmus L. Schmidt, Diophantine approximation of complex numbers, Acta Mathematica 134 (1975), 1 - 85. MR 54:10160
  • 34. C. Schnorr and M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems, Fundamentals of Computation Theory (Gosen, 1991), Lecture Notes in Computer Science, vol. 529, Springer-Verlag, Berlin, Heidelberg, New York, 1991, pp. 68-85; also published in Mathematical Programming Series A 66 (2) (1994), 181-199. MR 92g:68007; MR 95j:90064
  • 35. C. Rössner and C. P. Schnorr, A stable integer relation algorithm, FB Mathematik/ Informatik Universität Frankfurt TR-94-016 (1994), 1 - 11.
  • 36. C. P. Schnorr, A more efficient algorithm for lattice basis reduction, Journal of Algorithms 9 (1988), 47 - 62. MR 89h:11086
  • 37. G. Shimura, Fractional and trigonometric expressions for matrices, The American Mathematical Monthly 101 (8) (October 1994), 744 - 758. MR 96e:15053
  • 38. G. Szekeres, Multidimensional continued fractions, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 13 (1970), 113 - 140. MR 47:1763

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A05, 11Y16, 68--04

Retrieve articles in all journals with MSC (1991): 11A05, 11Y16, 68--04


Additional Information

Helaman R. P. Ferguson
Affiliation: Center for Computing Sciences, 17100 Science Drive, Bowie, MD 20715-4300
Email: helamanf@super.org

David H. Bailey
Affiliation: Lawrence Berkeley Lab, Mail Stop 50B-2239, Berkeley, CA 94720
Email: dhb@nersc.gov

Steve Arno
Email: arno@super.org

DOI: https://doi.org/10.1090/S0025-5718-99-00995-3
Keywords: Euclidean algorithm, integer relation finding algorithm, Gaussian integer, Hamiltonian integer, polynomial time
Received by editor(s): April 12, 1996
Received by editor(s) in revised form: June 9, 1997

American Mathematical Society