Parallel integer relation detection: Techniques and applications

Authors:
David H. Bailey and David J. Broadhurst

Journal:
Math. Comp. **70** (2001), 1719-1736

MSC (2000):
Primary 11Y16; Secondary 11-04

DOI:
https://doi.org/10.1090/S0025-5718-00-01278-3

Published electronically:
July 3, 2000

MathSciNet review:
1836930

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Let be a vector of real numbers. An *integer relation algorithm* is a computational scheme to find the integers , if they exist, such that . In the past few years, integer relation algorithms have been utilized to discover new results in mathematics and physics. Existing programs for this purpose require very large amounts of computer time, due in part to the requirement for multiprecision arithmetic, yet are poorly suited for parallel processing.

This paper presents a new integer relation algorithm designed for parallel computer systems, but as a bonus it also gives superior results on single processor systems. Single- and multi-level implementations of this algorithm are described, together with performance results on a parallel computer system. Several applications of these programs are discussed, including some new results in mathematical number theory, quantum field theory and chaos theory.

**1.**David H. Bailey, ``Multiprecision Translation and Execution of Fortran Programs'',*ACM Transactions on Mathematical Software*, vol. 19, no. 3, 1993, pp. 288-319.**2.**David H. Bailey, ``A Fortran-90 Based Multiprecision System'',*ACM Transactions on Mathematical Software*, vol. 21, no. 4, 1995, pg. 379-387. This software and documentation is available from the URL`http://www.nersc.gov/~dhbailey`.**3.**David H. Bailey, Jonathan M. Borwein and Roland Girgensohn, ``Experimental Evaluation of Euler Sums'',*Experimental Mathematics*, vol. 4, no. 1, 1994, pp. 17-30. MR**96e:11168****4.**David H. Bailey, Peter B. Borwein and Simon Plouffe, ``On The Rapid Computation of Various Polylogarithmic Constants'',*Mathematics of Computation*, vol. 66, no. 218, 1997, pp. 903-913. MR**98d:11165****5.**David H. Bailey and David Broadhurst, ``A Seventeenth-Order Polylogarithm Ladder''. This manuscript is available from the URL`http://xxx.lanl.gov/abs/math.NA/9905048`.**6.**David Borwein and Jonathan M. Borwein, ``On An Intriguing Integral and Some Series Related to '',*Proceedings of the American Mathematical Society*, vol. 123, 1995, pp. 111-118. MR**95e:11137****7.**David Borwein, Jonathan M. Borwein and Roland Girgensohn, ``Explicit Evaluation of Euler Sums'',*Proceedings of the Edinburgh Mathematical Society*, vol. 38, 1995, pp. 277-294. MR**96f:11106****8.**Jonathan M. Borwein and Peter B. Borwein,*Pi and the AGM*, John Wiley, New York, 1987. MR**89a:11134****9.**Jonathan M. Borwein, David M. Bradley and David J. Broadhurst, ``Evaluations of -fold Euler/Zagier Sums: A Compendium of Results for Arbitrary '',*Electronic Journal of Combinatorics*, vol. 4, no. 2, 1997, #R5. MR**98b:11091****10.**Jonathan M. Borwein, David M. Bradley, David J. Broadhurst and Petr Lisonek, ``Combinatorial Aspects of Multiple Zeta Values'',*Electronic Journal of Combinatorics*, vol. 5, no. 1, 1998, #R38. MR**99g:11100****11.**Jonathan M. Borwein and David J. Broadhurst, ``Apéry-like Reductions to Multiple Clausen Values and Euler Sums'', in preparation.**12.**David J. Broadhurst, John A. Gracey and Dirk Kreimer, ``Beyond the Triangle and Uniqueness Relations: Non-zeta Counterterms at Large from Positive Knots'',*Zeitschrift für Physik*, vol. C75, 1997, pp. 559-574. MR**98k:81178****13.**David J. Broadhurst and Dirk Kreimer, ``Association of Multiple Zeta Values with Positive Knots via Feynman Diagrams up to 9 Loops'',*Physics Letters*, vol. B393, 1997, pp. 403-412. MR**98g:11101****14.**David J. Broadhurst, ``Massive 3-loop Feynman Diagrams Reducible to SC Primitives of Algebras of the Sixth Root of Unity'', preprint,*European Physical Journal C*Part. Fields. vol. 8, 1999, pp. 313-333. The manuscript is available from the URL`http://xxx.lanl.gov/abs/hep-th/9803091`. CMP**2000:08****15.**David J. Broadhurst, ``Polylogarithmic Ladders, Hypergeometric Series and the Ten Millionth Digits of and ', preprint, March 1998. The manuscript is available from the URL`http://xxx.lanl.gov/abs/math/9803067`.**16.**Sid Chatterjee and Herman Harjono, ``MPFUN++: A Multiple Precision Floating Point Computation Package in C++'', University of North Carolina, Sept. 1998. This software is available from the URL`http://www.cs.unc.edu/Research/HARPOON/mpfun++`.**17.**Jack J. Dongarra, ``Performance of Various Computers Using Standard Linear Equations Software'', University of Tennessee Computer Science Technical Report, CS-89-85, 1999. The Linpack software is available from the URL`http://www.netlib.org/linpack`.**18.**Helaman R. P. Ferguson, David H. Bailey and Stephen Arno, ``Analysis of PSLQ, an Integer Relation Finding Algorithm'',*Mathematics of Computation*, vol. 68, 1999, pp. 351-369. MR**99c:11157****19.**Helaman R. P. Ferguson and Rodney W. Forcade, ``Generalization of the Euclidean Algorithm for Real Numbers to All Dimensions Higher Than Two'',*Bulletin of the American Mathematical Society*, vol. 1, 1979, pp. 912-914. MR**80i:10039****20.**William Gropp, Ewing Lusk and Anthony Skjellum,*Using MPI: Portable Parallel Programming with the Message-Passing Interface*, MIT Press, Cambridge, Mass., 1996.**21.**J. Hastad, B. Just, J. C. Lagarias and C. P. Schnorr, ``Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers'',*SIAM Journal of Computing*, vol. 18, 1989, pp. 859-881. MR**90g:11171****22.**Derrick H. Lehmer, ``Factorization of Certain Cyclotomic Functions'',*Annals of Mathematics*, vol. 34, 1933, pp. 461-479.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y16,
11-04

Retrieve articles in all journals with MSC (2000): 11Y16, 11-04

Additional Information

**David H. Bailey**

Affiliation:
Lawrence Berkeley Laboratory, MS 50B-2239, Berkeley, California 94720

Email:
dhbailey@lbl.gov

**David J. Broadhurst**

Affiliation:
Open University, Department of Physics, Milton Keynes MK7 6AA, United Kingdom

Email:
D.Broadhurst@open.ac.uk

DOI:
https://doi.org/10.1090/S0025-5718-00-01278-3

Received by editor(s):
October 20, 1999

Published electronically:
July 3, 2000

Additional Notes:
The work of the first author was supported by the Director, Office of Computational and Technology Research, Division of Mathematical, Information, and Computational Sciences of the U.S. Department of Energy, under contract number DE-AC03-76SF00098.

Article copyright:
© Copyright 2000
American Mathematical Society