Parallel integer relation detection: Techniques and applications
HTML articles powered by AMS MathViewer
- by David H. Bailey and David J. Broadhurst;
- Math. Comp. 70 (2001), 1719-1736
- DOI: https://doi.org/10.1090/S0025-5718-00-01278-3
- Published electronically: July 3, 2000
- PDF | Request permission
Abstract:
Let $\{x_1, x_2, \cdots , x_n\}$ be a vector of real numbers. An integer relation algorithm is a computational scheme to find the $n$ integers $a_k$, if they exist, such that $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n= 0$. 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.References
- David H. Bailey, âMultiprecision Translation and Execution of Fortran Programsâ, ACM Transactions on Mathematical Software, vol. 19, no. 3, 1993, pp. 288â319.
- 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.
- David H. Bailey, Jonathan M. Borwein, and Roland Girgensohn, Experimental evaluation of Euler sums, Experiment. Math. 3 (1994), no. 1, 17â30. MR 1302815, DOI 10.1080/10586458.1994.10504573
- 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, DOI 10.1090/S0025-5718-97-00856-9
- 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.
- David Borwein and Jonathan M. Borwein, On an intriguing integral and some series related to $\zeta (4)$, Proc. Amer. Math. Soc. 123 (1995), no. 4, 1191â1198. MR 1231029, DOI 10.1090/S0002-9939-1995-1231029-X
- 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, DOI 10.1017/S0013091500019088
- 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 Wiley-Interscience Publication. MR 877728
- J. M. Borwein, D. M. Bradley, and D. J. Broadhurst, Evaluations of $k$-fold Euler/Zagier sums: a compendium of results for arbitrary $k$, Electron. J. Combin. 4 (1997), no. 2, Research Paper 5, approx. 21. The Wilf Festschrift (Philadelphia, PA, 1996). MR 1444152, DOI 10.37236/1320
- 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, DOI 10.37236/1376
- Jonathan M. Borwein and David J. Broadhurst, âApĂ©ry-like Reductions to Multiple Clausen Values and Euler Sumsâ, in preparation.
- D. J. Broadhurst, J. A. Gracey, and D. Kreimer, Beyond the triangle and uniqueness relations: non-zeta counterterms at large $N$ from positive knots, Z. Phys. C 75 (1997), no. 3, 559â574. MR 1461268, DOI 10.1007/s002880050500
- 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. 3-4, 403â412. MR 1435933, DOI 10.1016/S0370-2693(96)01623-1
- 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.
- David J. Broadhurst, âPolylogarithmic Ladders, Hypergeometric Series and the Ten Millionth Digits of $\zeta (3)$ and $\zeta (5)$â, preprint, March 1998. The manuscript is available from the URL http://xxx.lanl.gov/abs/math/9803067.
- 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++.
- 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.
- 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, DOI 10.1090/S0025-5718-99-00995-3
- 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, DOI 10.1090/S0273-0979-1979-14691-3
- William Gropp, Ewing Lusk and Anthony Skjellum, Using MPI: Portable Parallel Programming with the Message-Passing Interface, MIT Press, Cambridge, Mass., 1996.
- 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, DOI 10.1137/0218059
- Derrick H. Lehmer, âFactorization of Certain Cyclotomic Functionsâ, Annals of Mathematics, vol. 34, 1933, pp. 461â479.
Bibliographic Information
- David H. Bailey
- Affiliation: Lawrence Berkeley Laboratory, MS 50B-2239, Berkeley, California 94720
- MR Author ID: 29355
- 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
- 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.
- © Copyright 2000 American Mathematical Society
- 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
- MathSciNet review: 1836930