The PSLQ algorithm for empirical data

Feng, Yong; Chen, Jingwei; Wu, Wenyuan

doi:10.1090/mcom/3356

The PSLQ algorithm for empirical data
HTML articles powered by AMS MathViewer

by Yong Feng, Jingwei Chen and Wenyuan Wu HTML | PDF

Math. Comp. 88 (2019), 1479-1501 Request permission

Abstract:

The celebrated integer relation finding algorithm PSLQ has been successfully used in many applications. PSLQ was only analyzed theoretically for exact input data, however, when the input data are irrational numbers, they must be approximate ones due to the finite precision of the computer. When the algorithm takes empirical data (inexact data with error bounded) instead of exact real numbers as its input, how do we theoretically ensure the output of the algorithm to be an exact integer relation?

In this paper, we investigate the PSLQ algorithm for empirical data as its input. Firstly, we give a termination condition for this case. Secondly, we analyze a perturbation on the hyperplane matrix constructed from the input data and hence disclose a relationship between the accuracy of the input data and the output quality (an upper bound on the absolute value of the inner product of the exact data and the computed integer relation), which naturally leads to an error control strategy for PSLQ. Further, we analyze the complexity bound of the PSLQ algorithm for empirical data. Examples on transcendental numbers and algebraic numbers show the meaningfulness of our error control strategy.

References

László Babai, Bettina Just, and Friedhelm Meyer auf der Heide, On the limits of computations with the floor function, Inform. and Comput. 78 (1988), no. 2, 99–107. MR 955578, DOI 10.1016/0890-5401(88)90031-4
D. H. Bailey, ARPREC: A C++/Fortran-90 arbitrary precision package, Available at http://www.davidhbailey.com/dhbsoftware, accessed in November, 2017.
D. H. Bailey, MPFUN2015: A high-precision software directory, Available at http://www.davidhbailey.com/dhbsoftware, accessed in November, 2017.
D. H. Bailey, MPFUN: A portable high performance multiprecision package, Tech. Report RNR-90-022, NASA Ames Research Center, December 1990.
D. H. Bailey, Integer relation detection, Computing in Science & Engineering 2 (2000), no. 1, 24–28.
D. H. Bailey, A collection of mathematical formulas involving $\pi$, (2016), Available at http://www.davidhbailey.com/dhbpapers/pi-formulas.pdf.
D. H. Bailey and Jonathan M. Borwein, High-precision arithmetic in mathematical physics, Mathematics 3 (2015), no. 2, 337–367.
David H. Bailey, Jonathan M. Borwein, and Jason S. Kimberley, Computer discovery and analysis of large Poisson polynomials, Exp. Math. 26 (2017), no. 3, 349–363. With an appendix by Watson Ladd. MR 3642112, DOI 10.1080/10586458.2016.1180565
David H. Bailey and David J. Broadhurst, Parallel integer relation detection: techniques and applications, Math. Comp. 70 (2001), no. 236, 1719–1736. MR 1836930, DOI 10.1090/S0025-5718-00-01278-3
Jonathan M. Borwein and Petr Lisoněk, Applications of integer relation algorithms, Discrete Math. 217 (2000), no. 1-3, 65–82 (English, with English and French summaries). Formal power series and algebraic combinatorics (Vienna, 1997). MR 1766260, DOI 10.1016/S0012-365X(99)00256-3
Jingwei Chen, Damien Stehlé, and Gilles Villard, A new view on HJLS and PSLQ: sums and projections of lattices, ISSAC 2013—Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2013, pp. 149–156. MR 3206352, DOI 10.1145/2465506.2465936
Yong Feng, Jingwei Chen, and Wenyuan Wu, Two variants of HJLS-PSLQ with applications, SNC 2014—Proceedings of the 2014 Symposium on Symbolic-Numeric Computation, ACM, New York, 2014, pp. 88–96. MR 3392719, DOI 10.1145/2631948.2631965
H, R. P. Ferguson and D. H. Bailey, A polynomial time, numerically stable integer relation algorithm, Tech. Report RNR-91-032, NASA Ames Research Center, 1992. http://davidhbailey.com/dhbpapers/pslq.pdf
Helaman R. P. Ferguson, David H. Bailey, and Steve Arno, Analysis of PSLQ, an integer relation finding algorithm, Math. Comp. 68 (1999), no. 225, 351–369. MR 1489971, DOI 10.1090/S0025-5718-99-00995-3
Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
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
Ch. Hermite, Sur l’intégration des fractions rationnelles, Ann. Sci. École Norm. Sup. (2) 1 (1872), 215–218 (French). MR 1508584
Bettina Just, Integer relations among algebraic numbers, Mathematical foundations of computer science 1989 (Porąbka-Kozubnik, 1989) Lecture Notes in Comput. Sci., vol. 379, Springer, Berlin, 1989, pp. 314–320. MR 1036810, DOI 10.1007/3-540-51486-4_{7}8
R. Kannan, A. K. Lenstra, and L. Lovász, Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Math. Comp. 50 (1988), no. 181, 235–250. MR 917831, DOI 10.1090/S0025-5718-1988-0917831-4
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
Saruchi, Ivan Morel, Damien Stehlé, and Gilles Villard, LLL reducing with the most significant bits, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 367–374. MR 3239948, DOI 10.1145/2608628.2608645
Allen Stenger, Experimental math for Math Monthly problems, Amer. Math. Monthly 124 (2017), no. 2, 116–131. MR 3608241, DOI 10.4169/amer.math.monthly.124.2.116