Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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!

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.