MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.