Parallel integer relation detection: Techniques and applications

Let (x(1), x(2),...,x(n)) be a vector of real numbers. An integer relation algorithm is a computational scheme to find the n integers ak, if they exis t, such that a(1)x(1) + a(2)x(2) + ... + a(n)x(n) = 0. In the past few year s, integer relation algorithms have been utilized to discover new results i n mathematics and physics, Existing programs for this purpose require very large amounts of computer time, due in part to the requirement for multipre cision 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 p rocessor systems. Single- and multi-level implementations of this algorithm are described, together with performance results on a parallel computer sy stem. Several applications of these programs are discussed, including some new results in mathematical number theory, quantum field theory and chaos t heory.