CARMA Analysis and Number Theory Seminar

3:30 pm

Wednesday, 25th Aug 2010

V205, Mathematics Building


Prof David Bailey

(Berkeley, California)

The PSLQ Algorithm: Techniques for Efficient Computation

The PSLQ algorithm is an algorithm for finding integer relations in a set of real numbers. In particular, if (x1, ..., xn) is a vector of real numbers, then PSLQ finds integers (a1, ..., an), not all zero, such that a1*x1 + a2*x2 + ... + an*xn = 0, if such integers exist. In practice, PSLQ finds a sequence of matrices B_n such that if x is the original vector, then the reduced vector y = x * B_n tends to have smaller and smaller entries, until one entry is zero (or a very small number commensurate with precision), at which point an integer relation has been detected. PSLQ also produces a sequence of bounds on the size of any possible integer, which bounds grow until either precision is exhausted or a relation has been detected.