Parallel integer relation detection: Techniques and applications
Authors:
David H. Bailey and David J. Broadhurst
Journal:
Math. Comp. 70 (2001), 17191736
MSC (2000):
Primary 11Y16; Secondary 1104
Published electronically:
July 3, 2000
MathSciNet review:
1836930
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: 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 multilevel 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. 288319.
 2.
David H. Bailey, ``A Fortran90 Based Multiprecision System'', ACM Transactions on Mathematical Software, vol. 21, no. 4, 1995, pg. 379387. 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, Experiment.
Math. 3 (1994), no. 1, 17–30. MR 1302815
(96e:11168)
 4.
David
Bailey, Peter
Borwein, and Simon
Plouffe, On the rapid computation of various
polylogarithmic constants, Math. Comp.
66 (1997), no. 218, 903–913. MR 1415794
(98d:11165), http://dx.doi.org/10.1090/S0025571897008569
 5.
David H. Bailey and David Broadhurst, ``A SeventeenthOrder 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 𝜁(4), Proc. Amer.
Math. Soc. 123 (1995), no. 4, 1191–1198. MR 1231029
(95e:11137), http://dx.doi.org/10.1090/S0002993919951231029X
 7.
David
Borwein, Jonathan
M. Borwein, and Roland
Girgensohn, Explicit evaluation of Euler sums, Proc. Edinburgh
Math. Soc. (2) 38 (1995), no. 2, 277–294. MR 1335874
(96f:11106), http://dx.doi.org/10.1017/S0013091500019088
 8.
Jonathan
M. Borwein and Peter
B. Borwein, Pi and the AGM, Canadian Mathematical Society
Series of Monographs and Advanced Texts, John Wiley & Sons Inc., New
York, 1987. A study in analytic number theory and computational complexity;
A WileyInterscience Publication. MR 877728
(89a:11134)
 9.
J.
M. Borwein, D.
M. Bradley, and D.
J. Broadhurst, Evaluations of 𝑘fold Euler/Zagier sums: a
compendium of results for arbitrary 𝑘, Electron. J. Combin.
4 (1997), no. 2, Research Paper 5, approx. 21. The
Wilf Festschrift (Philadelphia, PA, 1996). MR 1444152
(98b:11091)
 10.
Jonathan
M. Borwein, David
M. Bradley, David
J. Broadhurst, and Petr
Lisoněk, Combinatorial aspects of multiple zeta values,
Electron. J. Combin. 5 (1998), Research Paper 38, 12. MR 1637378
(99g:11100)
 11.
Jonathan M. Borwein and David J. Broadhurst, ``Apérylike Reductions to Multiple Clausen Values and Euler Sums'', in preparation.
 12.
D.
J. Broadhurst, J.
A. Gracey, and D.
Kreimer, Beyond the triangle and uniqueness relations: nonzeta
counterterms at large 𝑁 from positive knots, Z. Phys. C
75 (1997), no. 3, 559–574. MR 1461268
(98k:81178), http://dx.doi.org/10.1007/s002880050500
 13.
D.
J. Broadhurst and D.
Kreimer, Association of multiple zeta values with positive knots
via Feynman diagrams up to 9 loops, Phys. Lett. B 393
(1997), no. 34, 403–412. MR 1435933
(98g:11101), http://dx.doi.org/10.1016/S03702693(96)016231
 14.
David J. Broadhurst, ``Massive 3loop 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. 313333. The manuscript is available from the URL http://xxx.lanl.gov/abs/hepth/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, CS8985, 1999. The Linpack software is available from the URL http://www.netlib.org/linpack.
 18.
Helaman
R. P. Ferguson, David
H. Bailey, and Steve
Arno, Analysis of PSLQ, an integer relation
finding algorithm, Math. Comp.
68 (1999), no. 225, 351–369. MR 1489971
(99c:11157), http://dx.doi.org/10.1090/S0025571899009953
 19.
H.
R. P. Ferguson and R.
W. Forcade, Generalization of the Euclidean
algorithm for real numbers to all dimensions higher than two, Bull. Amer. Math. Soc. (N.S.) 1
(1979), no. 6, 912–914. MR 546316
(80i:10039), http://dx.doi.org/10.1090/S027309791979146913
 20.
William Gropp, Ewing Lusk and Anthony Skjellum, Using MPI: Portable Parallel Programming with the MessagePassing Interface, MIT Press, Cambridge, Mass., 1996.
 21.
J.
Håstad, B.
Just, J.
C. Lagarias, and C.P.
Schnorr, Polynomial time algorithms for finding integer relations
among real numbers, SIAM J. Comput. 18 (1989),
no. 5, 859–881. MR 1015261
(90g:11171), http://dx.doi.org/10.1137/0218059
 22.
Derrick H. Lehmer, ``Factorization of Certain Cyclotomic Functions'', Annals of Mathematics, vol. 34, 1933, pp. 461479.
 1.
 David H. Bailey, ``Multiprecision Translation and Execution of Fortran Programs'', ACM Transactions on Mathematical Software, vol. 19, no. 3, 1993, pp. 288319.
 2.
 David H. Bailey, ``A Fortran90 Based Multiprecision System'', ACM Transactions on Mathematical Software, vol. 21, no. 4, 1995, pg. 379387. 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. 1730. 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. 903913. MR 98d:11165
 5.
 David H. Bailey and David Broadhurst, ``A SeventeenthOrder 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. 111118. 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. 277294. 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érylike 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: Nonzeta Counterterms at Large from Positive Knots'', Zeitschrift für Physik, vol. C75, 1997, pp. 559574. 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. 403412. MR 98g:11101
 14.
 David J. Broadhurst, ``Massive 3loop 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. 313333. The manuscript is available from the URL http://xxx.lanl.gov/abs/hepth/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, CS8985, 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. 351369. 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. 912914. MR 80i:10039
 20.
 William Gropp, Ewing Lusk and Anthony Skjellum, Using MPI: Portable Parallel Programming with the MessagePassing 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. 859881. MR 90g:11171
 22.
 Derrick H. Lehmer, ``Factorization of Certain Cyclotomic Functions'', Annals of Mathematics, vol. 34, 1933, pp. 461479.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
11Y16,
1104
Retrieve articles in all journals
with MSC (2000):
11Y16,
1104
Additional Information
David H. Bailey
Affiliation:
Lawrence Berkeley Laboratory, MS 50B2239, 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:
http://dx.doi.org/10.1090/S0025571800012783
PII:
S 00255718(00)012783
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 DEAC0376SF00098.
Article copyright:
© Copyright 2000 American Mathematical Society
