# Mathematica Lattice Reduce Command

I'm going through a very old copy of "Mathematica: A System for Doing Mathematics by Computer" for self practice.

I'm on chapter 3, and ran into the LatticeReduce command.

Quick question: Is the lattice reduce command just basically just doing Gram Schmidt Orthogonalization?

Thanks.

• I guess I should add that lattice reduction uses Gram-Schmidt in its processing. May 17, 2015 at 23:57

No, it is not doing a Gram-Schmidt procedure.

One way to note that this is distinct from Gram-Schmidt is that Gram-Schmidt produces an orthonormal basis, whereas the example outputs in the Documentation Center page for LatticeReduce are neither normalized nor orthogonal.

Instead, LatticeReduce returns a basis $B$ comprised of linear combinations of integer multiples of the original basis vectors with minimal orthogonality defect, i.e., it minimizes $$\delta(\mathbf B)=\frac{\prod\limits_{i=1}^N \left|B_i\right|}{\sqrt{\det\left(\mathbf B^\top\mathbf B\right)}}.$$ This has the effect of making the resulting basis "most cube-like". Szabolcs mentioned in a comment that the internal implementation is the Lenstra-Lenstra-Lovász algorithm (see this).

See the Wiki page on lattice reduction for more info.

• Not exactly minimizes, but approximately, in the sense made precise in LLL. Nov 19, 2014 at 1:50
• In particular, it is mentioned in the docs that the method implemented is the Storjohann version of LLL. Aug 28, 2015 at 7:25
• @J.M. I had no idea that was in the documentation (even worse, it had to be me that put it there). As of 10.2 we use a method due to Nguyen and Stehle. Sometimes referred to as L^2 (though there are now at least two such). Aug 28, 2015 at 14:17
• @Daniel, oh, nice! I was wondering when it'd be implemented. Maybe someday I can try out 10.2... :) Aug 28, 2015 at 14:27
• @J.M. Actually it was implemented a few years ago, we just never told anyone. Was available via undocumented SystemOption. Some day I may even wrap up L1+ (if it doesn't wrap me up first). Aug 28, 2015 at 15:25