Title: The PSLQ Algorithm for Empirical Data,
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.