1998 · 109 citations · 5 references
ComputingComputer ScienceMathematicsAlgorithmsNumber TheoryTheory Of ComputationComputational ComplexityMatrix ComputationNumber-theoretic AlgorithmsNumerical AlgorithmsNumerical AnalysisNumerical Linear AlgebraApplications In Computational Number TheoryPolynomial-time AlgorithmsReal Numbers
Let x =(x1,x2, ···,xn) be a vector of real numbers. x is said to possess an integer relation if there exist integers ai not all zero such that a1x1 + a2x2 + ·· · + anxn =0. Beginning in 1977 several algorithms (with proofs) have been discovered to recover the ai given x. The most efficient of these existing integer relation algorithms (in terms of run time and the precision required of the input) has the drawback of being very unstable numerically. It often requires a numeric precision level in the thousands of digits to reliably recover relations in modest-sized test problems. We present here a new algorithm for finding integer relations, which we have named the “PSLQ ” algorithm. It is proved in this paper that the PSLQ algorithm terminates with a relation in a number of iterations that is bounded by a polynomial in n. Because this algorithm employs a numerically stable matrix reduction procedure, it is free from the numerical difficulties that plague other integer relation algorithms. Furthermore, its stability admits an efficient implementation with lower run times on average than other algorithms currently in use. Finally, this stability can be used to prove that relation bounds obtained from computer runs using this algorithm are numerically accurate.
5
Factoring polynomials with rational coefficients
A. K. Lenstra, H. W. Lenstra, László Lovász · Mathematische Annalen · 1982 · 4K citations · Full text
Solving low-density subset sum problems
Jeffrey C. Lagarias, Andrew Odlyzko · Journal of the ACM · 1985 · 406 citations · Full text
Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
Johan Håstad, Bettina Just, Jeffrey C. Lagarias et al. · SIAM Journal on Computing · 1989 · 104 citations