The PSLQ algorithm for empirical data
Authors:
Yong Feng, Jingwei Chen and Wenyuan Wu
Journal:
Math. Comp. 88 (2019), 1479-1501
MSC (2010):
Primary 11A05, 11Y16; Secondary 68-04
DOI:
https://doi.org/10.1090/mcom/3356
Published electronically:
June 20, 2018
MathSciNet review:
3904153
Full-text PDF
View in AMS MathViewer
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/10.1016/0890-5401%2888%2990031-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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/S0012-365X%2899%2900256-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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/3-540-51486-4_78
- 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1145/2608628.2608645
- Allen Stenger, Experimental math for Math Monthly problems, Amer. Math. Monthly 124 (2017), no. 2, 116–131. MR 3608241, DOI https://doi.org/10.4169/amer.math.monthly.124.2.116
Retrieve articles in Mathematics of Computation with MSC (2010): 11A05, 11Y16, 68-04
Retrieve articles in all journals with MSC (2010): 11A05, 11Y16, 68-04
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
Keywords:
Integer relation,
PSLQ,
empirical data
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).
Article copyright:
© Copyright 2018
American Mathematical Society
