Contents
Next: Applications of the
Up: Recognizing Numerical
Previous: Introduction
2. The PSLQ Integer Relation Algorithm
In 1991 a new algorithm, known as ``PSLQ'' algorithm, was developed by
Ferguson [12]. It appears to combine some of the best features
separately possessed by previous algorithms, including fast run times,
numerical stability, numerical efficiency (i.e. successfully
recovering a relation when the input is known to only limited
precision), and a guaranteed completion in a polynomially bounded
number of iterations. More recently a much simpler formulation of
this algorithm was developed, and it has been extended to the complex
number field
[13]. This newer, simpler version of PSLQ can be stated as
follows:
Let x be the n-long input real vector, and let nint denote the
nearest integer function (for exact half-integer values, define nint
to be the integer with greater absolute value). Let . Then perform the following:
Initialize:
- Set the matrices A and B to the identity.
- For to n: Set ;
endfor.
Set .
For to n: ;
endfor.
- Compute the matrix H as follows:
For to n: for to n - 1: set ;
endfor; if then set ; for to i - 1: set ; endfor;
endfor.
- Perform full reduction on H, simultaneously updating
and B:
For to n: for to 1 step -1: ; for to j:
; endfor; for
to n: ; endfor;
endfor; endfor.
Repeat until precision is exhausted or a relation has been detected:
- Select m such that is maximal when i = m.
- Exchange entries m and m + 1 of y, corresponding rows of
A and H, and corresponding columns of B.
- If then update H as follows:
Set
and . Then for to n: ; endfor.
- Perform block reduction on H, simultaneously updating and B:
For to n: for to 1 step
-1: ;
for to j: ; endfor;
for to n: ; endfor; endfor; endfor.
- Norm bound: Compute , where denotes
the j-th row of H. Then there can exist no relation vector whose
Euclidean norm is less than M.
- Termination test: If the largest entry of A exceeds the level
of numeric precision used, then precision is exhausted. If the
smallest entry of the y vector is less than the detection threshold,
a relation has been detected and is given in the corresponding column
of B.
With regards to the termination criteria in step 6, it sometimes
happens that a relation is missed at the point of potential detection
because the y entry is not quite as small as the detection threshold
being used (the threshold is typically set to the ``epsilon'' of the
precision level). When this happens, however, one will note that the
ratio of the smallest and largest y vector entries is suddenly very
small, provided sufficient numeric precision is being used. In a
normal computer run using the PSLQ algorithm, prior to the detection
of a relation, this ratio is seldom smaller than . Thus if
this ratio suddenly decreases to a very small value, such as
, then almost certainly a relation has been detected --- one
need only adjust the detection threshold for the algorithm to
terminate properly and output the relation. When detection does
occur, this ratio may be thought of as a ``confidence level'' of the
detection.
As a general rule, one can expect to detect a relation of degree n,
with coefficients of size , provided that the input vector is
known to somewhat greater than m n digit precision, and provided
that computations are performed using at least this level of numeric
precision.
Contents
Next: Applications of the
Up: No Title
Previous: Introduction