An Efficient LLL Reduction Algorithm

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.