Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction
Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction
复制标题
DOI：
10.1090/s0025-5718-2012-02545-2
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
X. Chang;D. Stehlé;G. Villard
中科院分区：
文献类型：
--
作者：
X. Chang;D. Stehlé;G. Villard
1982年，Arjen Lenstra，Hendrik Lenstra Jr.和Laszlo Lovasz引入了一个有效可计算的概念，即欧几里得格的基约简，现在通常称为LLL-约简。精确的定义涉及基矩阵的QR分解的R因子。加速LLL简化算法的一种自然方法是使用R因子的（浮点）近似值。在这篇文章中，我们调查的QR分解的一个LL-减少的基础上的因子R的准确性。我们的主要贡献是第一次充分严格的扰动分析的R-因子的LLL-约化矩阵列的扰动。我们的研究结果应该是非常有用的设计LL型算法依赖于浮点近似。
In 1982, Arjen Lenstra, Hendrik Lenstra Jr. and Laszlo Lovasz introduced an efficiently computable notion of reduction of basis of a Euclidean lattice that is now commonly referred to as LLL-reduction. The precise definition involves the R-factor of the QR factorisation of the basis matrix. A natural mean of speeding up the LLL reduction algorithm is to use a (floating-point) approximation to the R-factor. In the present article, we investigate the accuracy of the factor R of the QR factorisation of an LLL-reduced basis. Our main contribution is the first fully rigorous perturbation analysis of the R-factor of LLL-reduced matrices under column-wise perturbations. Our results should be very useful to devise LLL-type algorithms relying on floating-point approximations.