Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

The PSLQ algorithm for empirical data


Authors: Yong Feng, Jingwei Chen and Wenyuan Wu
Journal: Math. Comp.
MSC (2010): Primary 11A05, 11Y16; Secondary 68-04
DOI: https://doi.org/10.1090/mcom/3356
Published electronically: June 20, 2018
Full-text PDF

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.


References [Enhancements On Off] (What's this?)


Similar Articles

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

American Mathematical Society