Question

Let $A \in \mathbb{Z}^{n \times n}$ be a positive semidefinite sparse matrix. I am looking for asymptotically fast algorithms for computing the nullspace basis of $A$ (or just random elements in the nullspace). I wonder whether there are methods that can exploit the fact that $A$ is positive semidefinite to achieve better perfomance.

Answer 1

Presuming you are concerned with ease of implementation, and since you know that the matrix in question is positive semi-definite, one possibility would be to proceed as follows: Given the sparse representation, it is fast to perform a matrix-vector multiply. Thus you can use the use power iteration (see http://en.wikipedia.org/wiki/Power_iteration) to find the largest eigenvalue. Note, since you might have many degenerate top eigenvectors, you need to watch for the convergence of the Rayleigh quotient, not the convergence to a specific eigenvector. Anyway, call the largest eigenvalue $\lambda$. Since your eigenvalue must be an integer, you probably don't need many iterations to figure out which one you are converging to. Now, multiply the original matrix by -1 and add $\lambda$ to each diagonal element. This is, compute $M' = -M + \lambda I$

This new matrix will also be positive semi-definite (presuming you used to right $\lambda$), but now the vectors that were in the null space will have an eigenvalue of $\lambda$, and any other vector will have an eigenvalue of at most $\lambda - 1$. This means you should easily be able to find a random element of the null space via power iteration on $M'$

Hope that helps!

Answer 2

There is a large literature on this, but see:

http://graal.ens-lyon.fr/MUMPS/doc/ud_2010/Vasseur_talk.pdf

The fact that the coefficients are integers is not very relevant -- once you find your subspace, you can find the lattice in it.