KEITH MATTHEWS' LLL PAGE

Extended gcd and Hermite normal form algorithms via lattice basis reduction, G. Havas, B.S. Majewski, K.R. Matthews, Experimental Mathematics, Vol 7 (1998) 125-136.: I believe these algorithms are among the best for obtaining
(a) small multipliers for the extended gcd problems and more generally
(b) small unimodular transformation matrices for the Hermite normal form of an mxn matrix A.
The algorithms were inspired by limiting versions of LLL applied to [I_m|NⁿA₁|···|NA_n] as N gets large. The three LLLGCD algorithms are available in CALC, as is the LLLHNF algorithm. Also see unpublished addenda or published addenda

Short solutions of AX=B using a LLL-based Hermite normal form algorithm (pdf 123K) (18th August 1998): This uses the Havas, Majewski, Matthews HNF algorithm below to test for solubility in integers of a system of integer linear equations. A short solution is also found in the case of solubility. (The algorithm is available in my CALC program as axb().)

Short multipliers for the extended gcd problem (pdf 182K) (11th January 2001): This is a heuristic algorithm which usually delivers shorter multipliers than the one found by the LLL-based method. It will produce the shortest multipliers for 3 numbers and the shortest multipliers in this case are fully described. The algorithm is available in my CALC program as lllgcd0().

Slides for a LLL gcd/Hermite normal form seminar (pdf): These were given at TU München and 13th Czech-Slovak Number Theory Conference, Ostravice, September 1997.

LLL Hermite normal form algorithm example

Minimal multipliers for consecutive Fibonacci numbers, K.R. Matthews, Acta Arith. 75 (1996) 205-218.: The LLL gcd algorithm above always produces the shortest multipliers when the input are m consecutive Fibonacci numbers. With much experimentation and guesswork, I found formulae for these shortest multipliers involving the integer part symbol.

MLLL pseudocode (pdf) (9th October 1997) (implemented in CALC.): This is an implementation of the original algorithm of M. Pohst in his paper A modification of the LLL-algorithm, J. Symbolic Computation 4 (1987) 123-128

Smith Normal form with MLLL: At George Havas' suggestion in 1992, I wrote a program to use the MLLL algorithm to prevent coefficient explosion in obtaining the Smith canonical form of an integer matrix. The idea is simple but effective - bring in MLLL when the coefficients exceed a prescribed limit. This usually results in very small row vectors, often unit vectors and is implemented in my CALC program. In practice one gets unimodular P and Q with smallish entries such that PAQ=SNF(A).
The exact integer arithmetic involved in the underlying Gram-Schmidt process slows things down for large matrices of size bigger than (say) 150x300.

Last modified 6th February 2007