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.
Presuming you are concerned with ease of implementation, and since you know that the matrix in question is positive semidefinite, one possibility would be to proceed as follows: Given the sparse representation, it is fast to perform a matrixvector 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 semidefinite (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! 


There is a large literature on this, but see: http://graal.enslyon.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. 

