PSLQ 算法

一种可用于查找实数 整数关系 的算法 , ..., 使得

并非所有 都为零。虽然该算法通过操作格来运行，但它不会将其简化为短向量基，因此不是 格缩减 算法。PSLQ 基于平方和部分和方案（如 PSOS 算法），使用 QR 分解 实现。它由 Ferguson 和 Bailey (1992) 开发。Ferguson等人 (1999) 随后开发了一个大大简化的算法版本，该版本还将算法扩展到复数和四元数。Ferguson等人 (1999) 还证明了 PSLQ 与 HJLS 算法 不同。

PSLQ 算法在迭代次数上是多项式有界的，其迭代次数受 的多项式限制，并使用数值稳定的矩阵缩减程序 (Ferguson and Bailey 1992)。由于巧妙的技术允许在许多中间步骤中使用机器算术，PSLQ 往往比 Ferguson-Forcade 算法 和 LLL 算法 更快。LLL 算法 相比之下，必须使用中等精度，尽管通常不如 HJLS 算法。

虽然 LLL 算法 是一种比 PSLQ 更通用的 格缩减 算法，但使用 LLL 来获得整数关系在某种意义上是一种“技巧”，而使用 PSLQ，人们要么得到一个关系，要么得到多项式次数和系数大小的下界，关系必须满足这些界限。