Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What are the easiest brute force algorithms for solving closest and shortest vector problems?

I want to find an arbitrary, but small ($\lesssim 20$) number of lattice vectors closest to a given point. Since I consider low spatial dimension of four or less, the hardness of the closest vector problem is not an important issue for me. On the other hand, I want guaranteed solutions, so no approximations. Is the easiest way to use the standard lattice reductions, such as the LLL algorithm?

share|improve this question
    
I'd say this is almost better to ask over at mathematica.stackexchange, my bet is that if you ask nicely, you will even get working code for your problem. –  Per Alexandersson Feb 27 '13 at 6:38
    
Thanks. I'm not searching for a Mathematica implementation (Python actually). I'm also ok implementing it myself. –  Anton Akhmerov Feb 27 '13 at 18:01
add comment

2 Answers 2

up vote 1 down vote accepted

I know this in the language of quadratic forms. Once you have expressed your form in any somewhat reduced form, you have $f(x) = (1/2) x^T A x$ where $A$ is a symmetric positive and integral matrix. To find all $f(x) \leq M$ what I do is find the largest possible value of each $x_i$ by Lagrange multipliers. This surrounds the ellipsoid by a rectangular shape. The diagonal entries of $A^{-1}$ are involved, as are some square roots. Then you just run a multiple loop, exhausting the rectangle thing. If this does not give enough short vectors, increase $M.$ The main point here is that you have small dimension.

It is also possible to more precisely describe the ellipsoid, using the quadratic formula or the like, thus investigating fewer useless points. But for low dimension I would say it does not matter.

share|improve this answer
add comment

This sounds like you should consider the Fincke-Pohst algorithm. There are many implementations, see for example these slides.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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