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
Additional Information
- Yong Feng
- Affiliation: Chongqing Key Lab of Automated Reasoning and Cognition, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, People’s Republic of China
- MR Author ID: 612618
- Email: yongfeng@cigit.ac.cn
- Jingwei Chen
- Affiliation: Chongqing Key Lab of Automated Reasoning and Cognition, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, People’s Republic of China
- Email: chenjingwei@cigit.ac.cn
- Wenyuan Wu
- Affiliation: Chongqing Key Lab of Automated Reasoning and Cognition, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, People’s Republic of China
- MR Author ID: 802008
- Email: wuwenyuan@cigit.ac.cn
- Received by editor(s): July 17, 2017
- Received by editor(s) in revised form: November 8, 2017, and January 9, 2018
- Published electronically: June 20, 2018
- Additional Notes: The first author was supported by NNSF (China) Grant 11671377 and 61572024.
The second author was supported by NNSF (China) Grant 11501540, CAS “Light of West China” Program and Youth Innovation Promotion Association of CAS.\endgraf The second author is the corresponding author
The third author was supported by NNSF (China) Grant 11471307 and 11771421, Chongqing Research Program (cstc2015jcyjys40001, KJ1705121), and CAS Research Program of Frontier Sciences (QYZDB-SSW-SYS026). - © Copyright 2018 American Mathematical Society
- Journal: Math. Comp. 88 (2019), 1479-1501
- MSC (2010): Primary 11A05, 11Y16; Secondary 68-04
- DOI: https://doi.org/10.1090/mcom/3356
- MathSciNet review: 3904153