0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I guess I should add that lattice reduction uses Gram-Schmidt in its processing. $\endgroup$ May 17 '15 at 23:57
5
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Not exactly minimizes, but approximately, in the sense made precise in LLL. $\endgroup$ Nov 19 '14 at 1:50
  • $\begingroup$ In particular, it is mentioned in the docs that the method implemented is the Storjohann version of LLL. $\endgroup$
    – J. M.'s torpor
    Aug 28 '15 at 7:25
  • 3
    $\begingroup$ @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). $\endgroup$ Aug 28 '15 at 14:17
  • $\begingroup$ @Daniel, oh, nice! I was wondering when it'd be implemented. Maybe someday I can try out 10.2... :) $\endgroup$
    – J. M.'s torpor
    Aug 28 '15 at 14:27
  • $\begingroup$ @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). $\endgroup$ Aug 28 '15 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.