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

Full-text PDF

View in AMS MathViewer

Abstract | References | Similar Articles | Additional Information

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.

**[1]**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**, https://doi.org/10.1016/0890-5401(88)90031-4- [2]
D. H. Bailey,
*ARPREC: A C++/Fortran-90 arbitrary precision package*, Available at`http://www.davidhbailey.com/dhbsoftware`, accessed in November, 2017. - [3]
D. H. Bailey,
*MPFUN2015: A high-precision software directory*, Available at`http://www.davidhbailey.com/dhbsoftware`, accessed in November, 2017. - [4]
D. H. Bailey,
*MPFUN: A portable high performance multiprecision package*, Tech. Report RNR-90-022, NASA Ames Research Center, December 1990. - [5]
D. H. Bailey,
*Integer relation detection*, Computing in Science & Engineering**2**(2000), no. 1, 24-28. - [6]
D. H. Bailey,
*A collection of mathematical formulas involving*, (2016), Available at`http://www.davidhbailey.com/dhbpapers/pi-formulas.pdf`. - [7]
D. H. Bailey and Jonathan M. Borwein,
*High-precision arithmetic in mathematical physics*, Mathematics**3**(2015), no. 2, 337-367. **[8]**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**, https://doi.org/10.1080/10586458.2016.1180565**[9]**David H. Bailey and David J. Broadhurst,*Parallel integer relation detection: techniques and applications*, Math. Comp.**70**(2001), no. 236, 1719–1736. MR**1836930**, https://doi.org/10.1090/S0025-5718-00-01278-3**[10]**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**, https://doi.org/10.1016/S0012-365X(99)00256-3**[11]**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**, https://doi.org/10.1145/2465506.2465936**[12]**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**- [13]
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` **[14]**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**, https://doi.org/10.1090/S0025-5718-99-00995-3**[15]**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****[16]**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**, https://doi.org/10.1137/0218059**[17]**Ch. Hermite,*Sur l’intégration des fractions rationnelles*, Ann. Sci. École Norm. Sup. (2)**1**(1872), 215–218 (French). MR**1508584****[18]**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**, https://doi.org/10.1007/3-540-51486-4_78**[19]**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**, https://doi.org/10.1090/S0025-5718-1988-0917831-4**[20]**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**, https://doi.org/10.1007/BF01457454**[21]**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**, https://doi.org/10.1145/2608628.2608645**[22]**Allen Stenger,*Experimental math for Math Monthly problems*, Amer. Math. Monthly**124**(2017), no. 2, 116–131. MR**3608241**, 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

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

Email:
wuwenyuan@cigit.ac.cn

DOI:
https://doi.org/10.1090/mcom/3356

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