Lattice reduction

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).