In mathematics, the goal of lattice basis reduction is to find a basis with short, nearly orthogonal vectors when given an integer lattice basis as input. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice. Finding a reduced lattice basis is also closely related to the problem in crystallography of finding a unique unit cell. Historically reduction theory was first studied by Lagrange (1773) and independently by Gauss (1801), in order to classify binary quadratic forms, a classic problem in number theory. In a little sidenote to a book review in 1831, Gauss mentions that the reduction theory for certain quadratic forms is equivalent to finding a unit cell for point lattices and he sees the relevance for crystallography. This close relationship in number theory and geometry of point lattices inspired much of the successive work on quadratic forms culminating in Minkowski's important work "Geometry of Numbers" (1896 and 1910).
Nearly orthogonal One measure of nearly orthogonal is the orthogonality defect. This compares the product of the lengths of the basis vectors with the volume of the parallelepiped they define. For perfectly orthogonal basis vectors, these quantities would be the same. Any particular basis of n {\displaystyle n} vectors may be represented by a matrix B {\displaystyle B} , whose columns are the basis vectors b i , i = 1 , … , n {\displaystyle b_{i},i=1,\ldots ,n} . In the fully dimensional case where the number of basis vectors is equal to the dimension of the space they occupy, this matrix is square, and the volume of the fundamental parallelepiped is simply the absolute value of the determinant of this matrix det ( B ) {\displaystyle \det(B)} . If the number of vectors is less than the dimension of the underlying space, then volume is det ( B T B ) {\displaystyle {\sqrt {\det(B^{T}B)}}} . For a given lattice Λ {\displaystyle \Lambda } , this volume is the same (up to sign) for any basis, and hence is referred to as the determinant of the lattice det ( Λ ) {\displaystyle \det(\Lambda )} or lattice constant d ( Λ ) {\displaystyle d(\Lambda )} . The orthogonality defect is the product of the basis vector lengths divided by the parallelepiped volume;
δ ( B ) = Π i = 1 n ‖ b i ‖ det ( B T B ) = Π i = 1 n ‖ b i ‖ d ( Λ ) {\displaystyle \delta (B)={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{\sqrt {\det(B^{T}B)}}}={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{d(\Lambda )}}}
From the geometric definition it may be appreciated that δ ( B ) ≥ 1 {\displaystyle \delta (B)\geq 1} with equality if and only if the basis is orthogonal. If the lattice reduction problem is defined as finding the basis with the smallest possible defect, then the problem is NP-complete. However, there exist polynomial time algorithms to find a basis with defect δ ( B ) ≤ c {\displaystyle \delta (B)\leq c} where c is some constant depending only on the number of basis vectors and the dimension of the underlying space (if different). This is a good enough solution in many practical applications, such as in the factoring of polynomials
In two dimensions For a basis consisting of just two vectors, there is a simple and efficient method of reduction closely analogous to the Euclidean algorithm for the greatest common divisor of two integers. As with the Euclidean algorithm, the method is iterative; at each step the larger of the two vectors is reduced by adding or subtracting an integer multiple of the smaller vector. The pseudocode of the algorithm, often known as Lagrange's algorithm or the Lagrange-Gauss algorithm, is as follows:
… excerpt ends here. Continue reading the full article.
