一种有效的LLL规约算法

An Efficient LLL Reduction Algorithm

  • 摘要: 针对Lenstra-Lenstra-Lovász(LLL)规约算法在高维情况下规约耗时较大的特点,采用贪心算法和部分列向量规约,减少LLL算法规约过程中的基向量交换和尺度规约次数,以降低LLL算法的计算复杂度。通过模拟和实测的数据验证,该改进方法可以降低LLL算法的规约耗时,因而对高维模糊度的快速解算具有一定的参考应用价值。

     

    Abstract: The ambiguity resolution is one of the primary problems in GNSS carrier phase measurement. To acquire carrier phase integer ambiguity rapidly and accurately, we often take advantage of integer least-squares (ILS) estimation criterion to resolve ambiguity. Due to ILS problem can be regarded as closest vector problem (CLP) in lattice theory, therefore, lattice reduction could help to accelerate ambiguity enumeration process, shorten the search time, and further to improve the computation efficiency of ambiguity resolution. Among many of lattice reduction algorithms, Lenstra-Lenstra-Lovász (LLL) is a most popular and widely used reduction algorithm in many fields. It includes two reduction conditions, size reduction and basis vector swapping. However, size reduction is aimed at all matrix elements and basis vector swapping is only limited to two adjacent vectors, that will result in the unnecessary elements size reduction and excessive basis vector swapping times. Hence, both of them are not conducive to improving the ambiguity reduction efficiency, especially for high-dimensional ambiguity resolution. To overcome this problem, we adopt the greedy algorithm and partial column vector reduction to reduce the number of basis swapping and size reduction, in this contribution the computing complexity of LLL reduction algorithm is reduced, where LLL reduction algorithm has a long time-consuming under high-dimensional conditions. Simulations and real data validations have clearly shown that the modified LLL reduction algorithm can significantly improve the computational efficiency. Therefore our modified LLL algorithm has a certain useful value for fast resolution under high-dimensional case.

     

/

返回文章
返回