Keith Matthews' LLL page
Around 1992, I worked with George Havas, applying the LLL algorithm to finding small multipliers for the extended gcd problem. We also developed a LLL type algorithm for obtaining small unimodular transformation matrices for the Hermite normal form of an integer matrix.
- LLL lecture by Oded Regev, 2004
- Selected applications of LLL in number theory ( Denis Simon)
- Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications, Murray R. Bremner, CRC Press 2011
- 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.
- These algorithms experimentally have the following properties:
(a) small multipliers are obtained for the extended gcd problems and more generally
(b) small unimodular transformation matrices are obtained for the Hermite normal form of an mxn matrix A.
The algorithms were inspired by limiting versions of LLL applied to [Im|NnA1|···|NAn] as N gets large. The three LLLGCD algorithms are available in CALC, as is the LLLHNF algorithm. They are also online as BCMATH programs. 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 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 extended GCD algorithm examples
- LLL Hermite normal form algorithm example
- 4x4 (10th July 1997 noticed and replaced missing part on 6th Feb 2007)
- 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.
- (After 14 years, on writing a BCMATH version of the CALC code, I realise that the pseudo code had errors. Latest version 15/09/2011) MLLL pseudocode (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.
- BCMATH LLL-based integer matrix programs
Last modified 18th October 2011