Resolve integer ambiguity based on the global deep grid-based algorithms

Abstract

Grid theory is rather commonly-used through out the research of integer ambiguity. In order to promote the efficiency of computation, it is of great necessity to reduce the correlations of the grid basis through the reduction. The classical reduction algorithm is known as the LLL (Lenstra-Lenstra-Lovász) algorithm. So as to further enhance the reduction effect, the deep-insertion LLL algorithm can be utilized as an alternative to the basis vector exchange algorithm. In practice, the deep-insertion LLL algorithm can achieve a better reduction effect, but it requires more time for reduction. The PotLLL algorithm replaces the basis vector exchange condition of deep-insertion LLL with an improving in the basis quality, and it can run in polynomial time, but with certain limitations. Therefore, this article proposes a global deep-insertion PLLL algorithm (GS-PLLL) to address the issue of integer ambiguity. GS-PLLL adopts a global strategy for deep-insertion processing, and introduces a rotation sorting method for preconditioning the grid basis. Comparative evaluations were conducted using simulation experiments and real-world measurements on the LLL, DeepLLL, PotLLL, and GS-PLLL algorithms. The experimental results indicate that the GS-PLLL algorithm achieves a better reduction effect than the PotLLL algorithm while improving the efficiency of reduction.