Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have a basis for an integer lattice formed by the vectors $\vec v_1, \vec v_2, \ldots,\vec v_n$. Then let $A$ be the augmented matrix $( \vec v_1| \space \vec v_2| \cdots |\space \vec v_n)$.

Here is my question: is there an algorithm which performs elementary column operations on $A$ such that $\max(\|\vec u_1\|_p, \|\vec u_2\|_p, \ldots, \|\vec u_n\|_p)$ is a minimum, where $\vec u_i$ represent the new column vectors? The specific cases $p=1$, $p=2$, and $p=\infty$ are of particular interest to me.


Here are my thoughts for a slow-as-molasses approach:

I could first apply the LLL algorithm to get my vectors within a reasonable distance of the origin. Once that is done, a $L_p$ unit $n$-sphere could be drawn centered at the origin with radius stretched to the longest of the vectors. We could then brute-force the answer by checking every possible basis within this $n$-sphere.


EDIT:

It looks like the $p=\infty$ case can be reduced to a simpler problem, which is simply minimizing the absolute value of the largest element in the matrix. I have also found an article which looks promising in that it may have the answer for the $p=1$ case, but I'm having difficulty understanding some of the notation.

share|improve this question
1  
For $p = 2$, this is surely NP-hard, but if you insist, algorithms do exist that solve such problems. You could do an enumeration, and look for the $n$ shortest vectors (and some more if they are dependent). Several other methods exist, but all known methods are at least exponential in the dimension $n$. –  TMM Dec 30 '12 at 2:25
    
This review article includes, in section 5, a discussion of both a superexponential enumeration algorithm that "currently seems to outperform other techniques" and a merely exponential sieving algorithm. –  pyramids Nov 20 '13 at 12:26

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.