Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Analysis of PSLQ, an integer relation finding algorithm
HTML articles powered by AMS MathViewer

by Helaman R. P. Ferguson, David H. Bailey and Steve Arno PDF
Math. Comp. 68 (1999), 351-369 Request permission

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}, \dots , x_{n})$ be a vector in ${\mathbb {K}}^{n}$. The vector $x$ has an integer relation if there exists a vector $m = (m_{1}, \dots , 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}, \dots , 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
Similar Articles
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
  • MR Author ID: 29355
  • Email: dhb@nersc.gov
  • Steve Arno
  • Email: arno@super.org
  • Received by editor(s): April 12, 1996
  • Received by editor(s) in revised form: June 9, 1997
  • Journal: Math. Comp. 68 (1999), 351-369
  • MSC (1991): Primary 11A05, 11Y16, 68--04
  • DOI: https://doi.org/10.1090/S0025-5718-99-00995-3
  • MathSciNet review: 1489971