Analysis of PSLQ, an integer relation finding algorithm
HTML articles powered by AMS MathViewer
- by Helaman R. P. Ferguson, David H. Bailey and Steve Arno PDF
- Math. Comp. 68 (1999), 351-369 Request permission
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}, \dots , x_{n})$ be a vector in ${\mathbb {K}}^{n}$. The vector $x$ has an integer relation if there exists a vector $m = (m_{1}, \dots , 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}, \dots , 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
- 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.
- 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.
- David H. Bailey, Jonathan M. Borwein, and Roland Girgensohn, Experimental evaluation of Euler sums, Experiment. Math. 3 (1994), no. 1, 17–30. MR 1302815, DOI 10.1080/10586458.1994.10504573
- 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.
- David H. Bailey, Numerical results on the transcendence of constants involving $\pi ,e$, and Euler’s constant, Math. Comp. 50 (1988), no. 181, 275–281. MR 917835, DOI 10.1090/S0025-5718-1988-0917835-1
- D. H. Bailey, Multiprecision translation and execution of Fortran programs, ACM Transactions on Mathematical Software 19 (3) (1993), 288 – 319.
- D. H. Bailey, A Fortran-90 based multiprecision system, ACM Transactions on Mathematical Software 21 (4) (1995), 379 – 387..
- G. Bergman, Notes on Ferguson and Forcade’s generalized Euclidean algorithm, University of California at Berkeley, unpublished notes, Nov. 1980.
- V. Brun, En generalisatiken av kjedebroøken, I, II, Norske Videnskapsselskapets Skrifter I. Matematisk Naturvidenskapelig Klasse 6 (1919, 1920), 1-29, 1-24.
- Viggo Brun, Algorithmes euclidiens pour trois et quatre nombres, Treizième congrès des mathématiciens scandinaves, tenu à Helsinki 18-23 août 1957, Mercators Tryckeri, Helsinki, 1958, pp. 45–64 (French). MR 0111735
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, and Jacques Stern, Improved low-density subset sum algorithms, Comput. Complexity 2 (1992), no. 2, 111–128. MR 1190825, DOI 10.1007/BF01201999
- Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
- Dunham Jackson, A class of orthogonal functions on plane curves, Ann. of Math. (2) 40 (1939), 521–532. MR 80, DOI 10.2307/1968936
- H. R. P. Ferguson and R. W. Forcade, Multidimensional Euclidean algorithms, J. Reine Angew. Math. 334 (1982), 171–181. MR 667456
- W. D. Brownawell and D. W. Masser, Vanishing sums in function fields, Math. Proc. Cambridge Philos. Soc. 100 (1986), no. 3, 427–434. MR 857720, DOI 10.1017/S0305004100066184
- Helaman R. P. Ferguson, A noninductive $\textrm {GL}(n,\textbf {Z})$ algorithm that constructs integral linear relations for $n\;\textbf {Z}$-linearly dependent real numbers, J. Algorithms 8 (1987), no. 1, 131–145. MR 875331, DOI 10.1016/0196-6774(87)90033-2
- 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.
- Rodney W. Forcade, Brun’s algorithm, unpublished manuscript (November 1981), 1 – 27.
- D. H. Fowler, Ratio in early Greek mathematics, Bull. Amer. Math. Soc. (N.S.) 1 (1979), no. 6, 807–846. MR 546311, DOI 10.1090/S0273-0979-1979-14684-6
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
- 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.
- J. Håstad, B. Just, J. C. Lagarias, and C.-P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput. 18 (1989), no. 5, 859–881. MR 1015261, DOI 10.1137/0218059
- 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.
- R. Kannan, Lattices, basis reduction and the shortest vector problem, Theory of algorithms (Pécs, 1984) Colloq. Math. Soc. János Bolyai, vol. 44, North-Holland, Amsterdam, 1985, pp. 283–311. MR 872314
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- 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 (1990), no. 4, 333–348. MR 1099248, DOI 10.1007/BF02128669
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
- László Lovász and Herbert E. Scarf, The generalized basis reduction algorithm, Math. Oper. Res. 17 (1992), no. 3, 751–764. MR 1177735, DOI 10.1287/moor.17.3.751
- O. Perron, Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus, Math. Ann. (64) (1907), 1 – 76.
- M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Encyclopedia of Mathematics and its Applications, vol. 30, Cambridge University Press, Cambridge, 1989. MR 1033013, DOI 10.1017/CBO9780511661952
- H. Poincaré, Sur une généralisation des fractions continues, Comptes Rendus Acad. Sci. Paris 99 (1884), 1014 – 1016.
- Asmus L. Schmidt, Diophantine approximation of complex numbers, Acta Math. 134 (1975), 1–85. MR 422168, DOI 10.1007/BF02392098
- L. Budach (ed.), Fundamentals of computation theory, Lecture Notes in Computer Science, vol. 529, Springer-Verlag, Berlin, 1991. MR 1136064, DOI 10.1007/3-540-54458-5
- C. Rössner and C. P. Schnorr, A stable integer relation algorithm, FB Mathematik/ Informatik Universität Frankfurt TR-94-016 (1994), 1 – 11.
- C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), no. 1, 47–62. MR 925597, DOI 10.1016/0196-6774(88)90004-1
- Goro Shimura, Fractional and trigonometric expressions for matrices, Amer. Math. Monthly 101 (1994), no. 8, 744–758. MR 1299160, DOI 10.2307/2974529
- I. E. Jurut′, An asymptotic formula for the number of representations of integers that are bounded by a number of random summands, Vescī Akad. Navuk BSSR Ser. Fīz.-Mat. Navuk 2 (1972), 5–14 (Russian). MR 0313208
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
- MR Author ID: 29355
- Email: dhb@nersc.gov
- Steve Arno
- Email: arno@super.org
- Received by editor(s): April 12, 1996
- Received by editor(s) in revised form: June 9, 1997
- 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