Complex LLL and Eq. (8) from Wubben et al.

[poulson]

It seems to me that Eq. 8 from [1] is not necessarily satisfied when the input matrix for LLL has complex values. Indeed, said paper seems to embed complex matrices into real arithmetic and run LLL on the embedded matrix.

I started playing around with my own LLL implementation [2], based on [3], which I hope to make distributed and level 3 BLAS friendly, and I am finding that, when I check the satisfaction of Eq. (8) for complex matrices, that it does not hold, as each of the real and imaginary entries of the strictly upper triangle of inv(diag(diag(R)))*R seem to be able to have both real and imaginary entries approaching one half in magnitude. My (completely untested) hypothesis would be that this is fundamental to LLL on complex data and that Eq. (8) should, in this case, be modified to use sqrt(2)/2 instead of 1/2.

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.5464&rep=rep1&type=pdf
[2] elemental/Elemental@623564a
[3] http://perso.ens-lyon.fr/damien.stehle/downloads/HLLL.pdf

[chrisvwx]

Wow, I didn't think anyone had ever looked at my code. Sorry for the late response, I've obviously not been visiting Github.
Yes, I think you're right. See equations 11-13 and Table 1 of [1]. Also eq 5 of [2]. I'll update the package soon to be more clear that the LLL could be improved. And I'll put investigation of this on my to-do list.

[1] https://smartech.gatech.edu/bitstream/handle/1853/39591/gestner_brian_j_201105_phd.pdf
[2] https://arxiv.org/pdf/cs/0607078.pdf

[poulson]

No worries! For what it's worth, I've spent a bit of time working on LLL/BKZ/etc. since the last message and would recommend that, if you're interested in SVP Challenges, to look into the enumeration technique of [1], which, while claimed by several groups, is absolutely dominating the SVP challenges over "BKZ 2.0"'s GNR enumeration and is fairly straight-forward to implement [2]. I've been crunching away on SVP 146 since December or so (and, for what it's worth, an initial aggressive scheme, ala NTL or FPLLL, for reducing the basis primarily in double-precision despite kilobytes of precision being needed to exactly store the inputs is crucial).

[1] https://eprint.iacr.org/2014/980

[2] https://github.com/elemental/Elemental/blob/5a87fdde0eb22005ad5f79f9cb0802f989e930e3/src/number_theory/lattice/Enumerate/Phase.cpp

[chrisvwx]

The SVP challenges are interesting; it sounds like you're deep into work on it. I think it's wonderful that you're working on one of the challenge problems.

My main interest is in using lattice reduction to approximate the CVP for wireless communications for lattices that have between 4 and 16 dimensions. The goal is to do this in fixed-point in an FPGA or an ASIC so it can do many samples a second. I haven't got into this problem deeply; it's not obvious to me if the techniques you describe above (your ref [1]) are applicable to this CVP problem

[poulson]

Ah, thanks. And please let me know if a complex variant of GNR enumeration and/or BKZ would be of use for the MIMO problems; I got an algorithm that I made up working for it this morning: https://github.com/elemental/Elemental/blob/bd7035063dd2088d8ce22cdf2fc29e08f3574a19/src/number_theory/lattice/Enumerate/GNR.cpp