Certification of the QR factor R, and of lattice basis reducedness
Gilles Villard (LIP)
给定 Z^n 中 n 向量的格子基础,我们提出了一个使用 12n^3+O(n^2) 浮点运算的算法来检查基础是否被 LLL 还原。 如果基础减少,那么算法有望回答“是”。 如果基础没有减少,或者使用的精度不足以用于n,并且对基础的数值属性,则算法将回答“失败”。 因此,一个肯定的答案是一个严格的证书。 为了实现证书本身,我们提出了一个浮点算法,用于计算QR矩阵因子的R因子条目的误差边界。 该算法考虑了所有可能的近似和四舍五入错误。 证书的成本 12n^3+O(n^2) 比计算QR因子化本身的数值算法的成本仅高出6倍,证书只能使用矩阵库例程实现。 我们报告的实验表明,为了减少足够的尺寸和质量,证书成功,并确定证书的有效性。 这种有效性适用于认证LLL减少的最快现有浮点异构的输出,而不会减慢整个过程。
Given a lattice basis of n vectors in Z^n, we propose an algorithm using 12n^3+O(n^2) floating point operations for checking whether the basis is LLL-reduced. If the basis is reduced then the algorithm will hopefully answer "yes". If the basis is not reduced, or if the precision used is not sufficient with respect to n, and to the numerical properties of the basis, the algorithm will answer "failed". Hence a positive answer is a rigorous certificate. For implementing the certificate itself, we p...