|Ivars Peterson's MathTrek|
February 14, 2000
"Computational algorithms are probably as old as civilization," Francis Sullivan of the Institute for Defense Analyses' Center for Computing Sciences in Bowie, Md., noted in an editorial in the January/February issue of CISE. Ancient tablets bearing Sumerian cuneiform, for example, feature descriptions of procedures for reckoning in base 60.
"Algorithms have advanced in startling and unexpected ways in the 20th century," Sullivan continued. "The algorithms we chose. . .have been essential for progress in communications, health care, manufacturing, economics, weather prediction, defense, and fundamental science. Conversely, progress in these areas has stimulated the search for ever-better algorithms."
Many of the selections are now familiar, finely tuned, heavily used tools. The Metropolis algorithm for Monte Carlo methods, the simplex method in linear programming, the Fast Fourier Transform for analyzing and manipulating digital data, and the Quicksort algorithm fit into this category.
Some, however, are somewhat less familiar. In particular, the so-called PSLQ algorithm has only recently become a computational staple. It gives researchers an efficient method for detecting what are called integer relations. Given a string of n real numbers, x1,. . .,xn, the problem is to find a set of integers a1,. . .,an (if they exist and are not all zero) such that a1x1 +. . .+anxn = 0.
The PSLQ procedure can be regarded as a jazzed-up version of an integer-relation algorithm dating back more than 2,000 years to the Greek geometer Euclid of Alexandria (365-300 B.C.).
The Euclidean algorithm offers a recipe for finding the greatest common divisor of two whole numbers. Suppose the given numbers are 12 and 18. Twelve is evenly divisible by 1, 2, 3, 4, 6, and 12; 18 is evenly divisible by 1, 2, 3, 6, 9, and 18. By comparing the lists, you can see that both numbers are evenly divisible by 1, 2, 3, and 6. Hence, the largest common divisor is 6. Thats easy to figure out by trial and error when the given numbers are small. The Euclidean algorithm works with numbers of any size.
To find the greatest common divisor of 77 and 187 using the Euclidean algorithm involves the process of long division, which you might have first encountered in elementary school. Divide 77 into 187. The remainder is 33. Divide the remainder, 33, into the original divisor, 77. The new remainder is 11. Divide 11 into 33. The remainder is 0. You can then conclude that the greatest common divisor is 11. (See http://www.cut-the-knot.com/blue/Euclid.html.)
Determining the greatest common divisor is an example of finding an integer relation between two numbers. In 1977, mathematician Helaman Ferguson, then at Brigham Young University in Provo, Utah, and colleague Rodney Forcade discovered a generalization of the Euclidean algorithm. The PSLQ version of this scheme now serves as a practical computational scheme for finding integer relations involving more than two numbers and for performing a process known as lattice reduction.
Since that landmark achievement, Ferguson has gained fame as a sculptor of mathematically inspired forms (see Minimal Snow, March 8, 1999). Indeed, he sees an intimate link between his mathematical algorithm and the art of carving. Both are subtractive processes. In the Euclidean algorithm, the mathematician chips away at a pair of numbers until their greatest common divisor is finally revealed. In sculpture, the artist chisels away rock until the envisioned form appears.
The PSLQ algorithm has become an important component of the emerging discipline of experimental mathematics--the use of computers as an exploratory tool in mathematical research. It has been used to discover unknown mathematical identities, such as a remarkable, simple formula for calculating isolated binary digits of the number pi without computing and keeping track of all the preceding numbers (see Pick a Digit, Any Digit, March 2, 1998).
More recently, physicist David J. Broadhurst of the Open University in Milton Keynes, England, has used the PSLQ algorithm to discover unexpected relations in quantum field theory.
Such discoveries may have important ramifications. The pi formula, for instance, raises questions about the long-held but never-proved assumption that pis digits are random. The results in quantum field theory involving Feynman diagrams suggest unsuspected relationships among formulas associated with fundamental particles.
Then there is the wonder of the algorithm itself.
"For me, great algorithms are the poetry of computation," Sullivan remarked in his CISE editorial. "Just like verse, they can be terse, allusive, dense, and even mysterious. But once unlocked, they cast a brilliant new light on some aspect of computing."
Copyright 2000 by Ivars Peterson
Bailey, D.H. 2000. Integer relation detection. Computing in Science & Engineering 2(January/February):24. (See http://computer.org/cise/cs2000/c1024abs.htm).
Bailey, D.H., and D.J. Broadhurst. Preprint. Parallel integer relation detection: Techniques and applications. (Available at http://xxx.lanl.gov/abs/math.NA/9905048.)
Borwein, J.M., and R.M. Corless. 1999. Emerging tools for experimental mathematics. American Mathematical Monthly 106(December):889.
Broadhurst, D.J. Preprint. Massive 3-loop Feynman diagrams reducible to SC* primitives of algebras of the sixth root of unity. (See http://xxx.lanl.gov/abs/hep-th/9803091.)
Ferguson, H.R.P., D.H. Bailey, and S. Arno. 1999. Analysis of PSLQ, an integer relation finding algorithm. Mathematics of Computation 68(January):351.
Peterson, I. 1998. More pieces of pi. Science News 154(Oct. 17):255.
Preuss, P. 2000. An algorithm for the ages: PSLQ: A better way to find integer relations. Available at http://www.lbl.gov/Science-Articles/Archive/pi-algorithm.html.
Sullivan, F. 2000. The joy of algorithms. Computing in Science & Engineering 2(January/February):2.
Helaman Ferguson has a Web site at http://www.helasculpt.com/.
David H. Bailey of the Lawrence Berkeley National Laboratory has a Web page at http://www.nersc.gov/~dhb/, where links to some of his papers on the PSLQ algorithm can be found.
David J. Broadhurst's Web page can be found at http://physics.open.ac.uk/~dbroadhu/.
You can try out a game involving Euclid's algorithm at http://www.cut-the-knot.com/blue/EuclidAlg.html. Additional information about the algorithm can be found at http://mathworld.wolfram.com/EuclideanAlgorithm.html.
The PSLQ algorithm is described at http://mathworld.wolfram.com/PSLQAlgorithm.html.
Comments are welcome. Please send messages to Ivars Peterson at firstname.lastname@example.org.