CARMA Analysis and Number Theory Seminar
3:30 pm
Wednesday, 25th Aug 2010
V205, Mathematics Building
• Download The PSLQ Algorithm: Techniques for Efficient Computation ("California") [109]
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.