An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction
Hervé Daudé, Philippe Flajolet, Brigitte Vallée · Combinatorics Probability Computing · 1997
The Gaussian algorithm for lattice reduction in dimension 2 is analysed under its standard version. It is found that, when applied to random inputs in a continuous model, the complexity is constant on average, its probability distribution decays geometrically, and the dynamics are characterized by a conditional invariant measure. The proofs make use of connections between lattice reduction, continued fractions, continuants, and functional operators. Analysis in the discrete model and detailed numerical data are also presented.