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

I am wondering whether there is an efficient algorithm to traverse all the $N\times N$ perfect quadratic forms $Q$ inside the polyhedron $e_j^T Q e_j \geq 1$, $j = 1\ldots m$, where $e_j$ are some given integer vectors (so I am not only after unimodular-inequivalent perfect forms, but equivalent ones too). In other words, an algorithm that can give me the vertices of this polyhedron, where the vertices must be positive definite. One way is to find all the vertices of that polyhedron and keep the positive definite ones, but since some vertices are not positive definite, that is a rather inefficient enumeration algorithm I guess. So I'm wondering whether there is already an efficient algorithm only moving inside the positive semidefinite cone and returning the positive definite vertices? Also, when it comes to complexity, how many inequalities $m$ and how large dimensions $N$ can one hope to handle?
Thank you very much for any comments.

share|improve this question
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.