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.
$\begingroup$
$\endgroup$
Add a comment
|