Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Email: helamanf@super.org

David H. Bailey
Affiliation: Lawrence Berkeley Lab, Mail Stop 50B-2239, Berkeley, CA 94720
Email: dhb@nersc.gov

Steve Arno
Email: arno@super.org

DOI: http://dx.doi.org/10.1090/S0025-5718-99-00995-3
PII: S 0025-5718(99)00995-3
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