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?<\/p>\n
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.<\/p>","DOI":"10.1090\/mcom\/3356","type":"journal-article","created":{"date-parts":[[2018,3,21]],"date-time":"2018-03-21T09:41:20Z","timestamp":1521625280000},"page":"1479-1501","source":"Crossref","is-referenced-by-count":5,"title":["The PSLQ algorithm for empirical data"],"prefix":"10.1090","volume":"88","author":[{"given":"Yong","family":"Feng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingwei","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenyuan","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0890-5401(88)90031-4","article-title":"On the limits of computations with the floor function","volume":"78","author":"Babai, L\u00e1szl\u00f3","year":"1988","journal-title":"Inform. and Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0890-5401","issn-type":"print"},{"key":"2","unstructured":"D. H. Bailey, ARPREC: A C++\/Fortran-90 arbitrary precision package, Available at \\url{http:\/\/www.davidhbailey.com\/dhbsoftware}, accessed in November, 2017."},{"key":"3","unstructured":"D. H. Bailey, MPFUN2015: A high-precision software directory, Available at \\url{http:\/\/www.davidhbailey.com\/dhbsoftware}, accessed in November, 2017."},{"key":"4","unstructured":"D. H. Bailey, MPFUN: A portable high performance multiprecision package, Tech. Report RNR-90-022, NASA Ames Research Center, December 1990."},{"key":"5","doi-asserted-by":"crossref","unstructured":"D. H. Bailey, Integer relation detection, Computing in Science & Engineering 2 (2000), no. 1, 24\u201328.","DOI":"10.1109\/5992.814653"},{"key":"6","unstructured":"D. H. Bailey, A collection of mathematical formulas involving \ud835\udf0b, (2016), Available at \\url{http:\/\/www.davidhbailey.com\/dhbpapers\/pi-formulas.pdf}."},{"key":"7","doi-asserted-by":"crossref","unstructured":"D. H. Bailey and Jonathan M. Borwein, High-precision arithmetic in mathematical physics, Mathematics 3 (2015), no. 2, 337\u2013367.","DOI":"10.3390\/math3020337"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1080\/10586458.2016.1180565","article-title":"Computer discovery and analysis of large Poisson polynomials","volume":"26","author":"Bailey, David H.","year":"2017","journal-title":"Exp. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"issue":"236","key":"9","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.1090\/S0025-5718-00-01278-3","article-title":"Parallel integer relation detection: techniques and applications","volume":"70","author":"Bailey, David H.","year":"2001","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1-3","key":"10","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0012-365X(99)00256-3","article-title":"Applications of integer relation algorithms","volume":"217","author":"Borwein, Jonathan M.","year":"2000","journal-title":"Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/2465506.2465936","article-title":"A new view on HJLS and PSLQ: sums and projections of lattices","author":"Chen, Jingwei","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450320597"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/2631948.2631965","article-title":"Two variants of HJLS-PSLQ with applications","author":"Feng, Yong","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450329637"},{"key":"13","unstructured":"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. \\url{http:\/\/davidhbailey.com\/dhbpapers\/pslq.pdf}"},{"issue":"225","key":"14","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1090\/S0025-5718-99-00995-3","article-title":"Analysis of PSLQ, an integer relation finding algorithm","volume":"68","author":"Ferguson, Helaman R. P.","year":"1999","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"15","series-title":"Johns Hopkins Studies in the Mathematical Sciences","isbn-type":"print","volume-title":"Matrix computations","author":"Golub, Gene H.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781421407944","edition":"4"},{"issue":"5","key":"16","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/0218059","article-title":"Polynomial time algorithms for finding integer relations among real numbers","volume":"18","author":"H\u00e5stad, J.","year":"1989","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"17","doi-asserted-by":"crossref","first-page":"215","DOI":"10.24033\/asens.82","article-title":"Sur l\u2019int\u00e9gration des fractions rationnelles","volume":"1","author":"Hermite, Ch.","year":"1872","journal-title":"Ann. Sci. \\'{E}cole Norm. Sup. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0012-9593","issn-type":"print"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/3-540-51486-4_78","article-title":"Integer relations among algebraic numbers","author":"Just, Bettina","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/3540514864"},{"issue":"181","key":"19","doi-asserted-by":"publisher","first-page":"235","DOI":"10.2307\/2007927","article-title":"Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers","volume":"50","author":"Kannan, R.","year":"1988","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"20","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra, A. K.","year":"1982","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1145\/2608628.2608645","article-title":"LLL reducing with the most significant bits","author":"Saruchi","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450325011"},{"issue":"2","key":"22","doi-asserted-by":"publisher","first-page":"116","DOI":"10.4169\/amer.math.monthly.124.2.116","article-title":"Experimental math for Math Monthly problems","volume":"124","author":"Stenger, Allen","year":"2017","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-317\/S0025-5718-2018-03356-7\/mcom3356_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2019-88-317\/S0025-5718-2018-03356-7\/S0025-5718-2018-03356-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-317\/S0025-5718-2018-03356-7\/S0025-5718-2018-03356-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:04:11Z","timestamp":1776801851000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-317\/S0025-5718-2018-03356-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":22,"journal-issue":{"issue":"317","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["S0025-5718-2018-03356-7"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3356","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2018,6,20]]}}}