An improved LLL algorithm (Q2465313): Difference between revisions

The paper is devoted to the presentation of a new way to look at the reduction algorithm of \textit{A. K. Lenstra, H. W. Lenstra jun.} and \textit{L. Lovasz} [(LLL); Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)] which leads to a new implementation method that performs better than the original scheme of this algorithm. In the beginning of the paper, the idea of the reduced basis and the LLL algorithm are presented based on the description of the problem of integer lest squares. Next, the idea of a reduced basis is extend to that of a reduced triangular matrix, and a new algorithm is presented based on this extension. It is shown that the two methods (the LLL reduction algorithm and the proposed new one) are producing identical numerical results in exact arithmetic. The only difference lies in the used transformation. Some numerical examples are given to illustrate how the numerical results produced by the proposed new method can be significantly better than those produced by the original LLL scheme.