Determinant of a symmetric, positive semidefinite, sparse integer matrix I'm looking for an algorithm that calculates the (log) determinant of a symmetric, positive semidefinite, sparse integer matrix.  Does such an algorithm exist that can exploit both sparsity and integer structure for faster calculation, compared to more general purpose determinant calculating routines?
 A: The folks in the linear programming space look at similar problems. They don't need the determinant, but a typical first step in computing a determinant is an LU factorization, and that they are interested in. 
The QSOPT_ex Rational LP solver probably has some code in there that will do the job for you, but you'll have to dig around for it. This paper by Cook and Steffy, "Solving Very Sparse Rational Systems of Equations", talks about QSOpt_ex and other approaches. Unfortunately, the links in this paper are stale, but perhaps some Google sleuthing can turn up an updated location for the code and test problems.
I've also seen references to a "fraction-free" LU factorization. This paper (PDF) talks about how to do fraction-free LU factorizations. However, it does not deal with sparse matrices. You could could perhaps adapt some simple sparse factorization code, like CSparse, and to work with the fraction-free or rational values.
Once you have an LU factorization, say $PA=LD^{-1}U$, then the determinant would simply be $\prod_i L_{ii} U_{ii} / \prod_i D_{ii}$. Obviously you can use arbitrary-precision integer multiplication and division to compute that exactly.
EDIT: I'm really not sure why I missed that your matrix was symmetric positive definite. Of course you could do sparse Cholesky then instead of sparse LU. In that case, check out Tim Davis' LDL, which is a very compact sparse factorization engine, that I am sure could be adapted readily to rationals.
