The quantities every reduction algorithm is defined in terms of
Gram–Schmidt turns a basis into an orthogonal family by subtracting from each vector its projections onto the previous ones. The projection coefficients μij and the squared lengths of the orthogonal vectors are precisely the quantities in which the LLL reduction conditions are stated. The orthogonal vectors themselves are almost never lattice vectors — they are a measuring instrument, not an output.
Learning objectives
- State the Gram–Schmidt recurrence and the meaning of its coefficients.
- Explain why the orthogonal family is not a lattice basis.
- Identify the numerical failure mode of the classical procedure.
- Choose between floating-point and exact integral variants.
- Connect the μ coefficients to the LLL reduction conditions.
Section 01The procedure
The family {b*i} is orthogonal and spans the same real subspace, and the determinant is preserved: det L = ∏ ‖b*i‖. In matrix terms this is the QR decomposition, with the μ forming the unit lower-triangular factor.
The μ coefficients are rational, so b*i generally lies outside the lattice. Reduction algorithms use the b*i only to measure the basis; every vector they actually manipulate is an integer combination of the original basis.
Section 02Numerical behaviour
The classical procedure, implemented exactly as written, loses orthogonality catastrophically when the basis is ill-conditioned — which is precisely the situation in which reduction is needed. The subtractions cancel almost entirely, and the surviving digits are rounding noise.
| Variant | Stability | Cost | When to use |
|---|---|---|---|
| Classical Gram–Schmidt | Poor | 2n3/3 | Never, in floating point |
| Modified Gram–Schmidt | Much better | Same | Default floating-point choice — project one vector at a time |
| Householder QR | Excellent | Higher | When orthogonality must be near machine precision |
| Exact rational / integral | Exact by construction | Highest | Verification, and small dimensions where exactness is affordable |
Modified Gram–Schmidt subtracts each projection immediately rather than accumulating them, so later projections are computed against already-corrected vectors. The operation count is identical; only the rounding behaviour differs. There is no reason to implement the classical form.
Section 03Exact variants and the LLL connection
Working with exact rationals is safe but slow, since the μ have rapidly growing denominators. The integral variant clears these denominators by scaling with the leading principal minors di = ∏j≤i ‖b*j‖2, which are integers for an integer lattice. All arithmetic then stays in ℤ.
The reduction conditions of LLL are stated entirely in these terms:
Production LLL implementations run Gram–Schmidt in floating point for speed, and re-verify the conditions in exact arithmetic whenever a test comes out close to the threshold. This gives near floating-point speed with exact-arithmetic guarantees — and is the reason floating point is acceptable inside an otherwise exact subject.
ReferenceFrequently asked questions
Should the orthogonal vectors be recomputed after every basis update?
No — that would dominate the cost. LLL updates the affected mu coefficients and norms incrementally after each swap or size reduction, touching only the entries that can have changed.
What causes the loss of orthogonality?
Catastrophic cancellation. When a vector is nearly in the span of its predecessors, the subtraction removes almost all of its magnitude and the remainder consists largely of rounding error, so the computed orthogonal vector points in a direction that is essentially arbitrary.
Is Cholesky an alternative?
Yes. Factoring the Gram matrix by Cholesky yields the same information without forming the orthogonal vectors explicitly, and is often preferred when only the mu coefficients and norms are needed — which is the case inside LLL.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.