Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Analysis of PSLQ,
an integer relation finding algorithm

Authors: Helaman R. P. Ferguson, David H. Bailey and Steve Arno
Journal: Math. Comp. 68 (1999), 351-369
MSC (1991): Primary 11A05, 11Y16, 68--04
MathSciNet review: 1489971
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let ${\mathbb{K}}$ be either the real, complex, or quaternion number system and let ${\mathbb{O}}({\mathbb{K}})$ be the corresponding integers. Let $ x = (x_{1}, \hdots , x_{n})$ be a vector in ${\mathbb{K}}^{n}$. The vector $x$ has an integer relation if there exists a vector $m = (m_{1}, \hdots , m_{n}) \in {\mathbb{O}}({\mathbb{K}})^{n}$, $m \ne 0$, such that $m_{1} x_{1} + m_{2} x_{2} + \ldots + m_{n} x_{n} = 0$. In this paper we define the parameterized integer relation construction algorithm PSLQ$(\tau )$, where the parameter $\tau $ can be freely chosen in a certain interval. Beginning with an arbitrary vector $x = (x_{1}, \hdots , x_{n}) \in {\mathbb{K}}^{n}$, iterations of PSLQ$(\tau )$ will produce lower bounds on the norm of any possible relation for $x$. Thus PSLQ$(\tau )$ can be used to prove that there are no relations for $x$ of norm less than a given size. Let $M_{x}$ be the smallest norm of any relation for $x$. For the real and complex case and each fixed parameter $\tau $ in a certain interval, we prove that PSLQ$(\tau )$ constructs a relation in less than $O(n^{3} + n^{2} \log M_{x})$ iterations.

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

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A05, 11Y16, 68--04

Retrieve articles in all journals with MSC (1991): 11A05, 11Y16, 68--04

Additional Information

Helaman R. P. Ferguson
Affiliation: Center for Computing Sciences, 17100 Science Drive, Bowie, MD 20715-4300

David H. Bailey
Affiliation: Lawrence Berkeley Lab, Mail Stop 50B-2239, Berkeley, CA 94720

Steve Arno

Keywords: Euclidean algorithm, integer relation finding algorithm, Gaussian integer, Hamiltonian integer, polynomial time
Received by editor(s): April 12, 1996
Received by editor(s) in revised form: June 9, 1997