Identifying the name/provenance of a technique to find the nullspace vectors of a matrix by random sampling and the conjugate residual method

I have got a large sparse matrix $A \in \mathbb R^{n \times n}$ and I want to find non-trivial elements in the kernel/nullspace of this matrix. How can this be done? I would like to learn more about a particular method that seems to be folklore.

Most people that I have talked to regard this problem as an instance of an eigenvalue problem and recommend, e.g., the power method for this. For general $A$, this might a very good recommendation. But assume $A$ is symmetric-positive semidefinite, like, e.g., the stiffness matrix of the Poisson system with natural boundary conditions.

Let us choose some random vector $x_0 \in \mathbb R^n$, which can be assembled by a probability distribution. Let us use the Conjugate Residual method (CRM) with $x_0$ as a starting vector and right-hand side $0 \in \mathbb R^n$ (!). The CRM converges to a solution $x \in \mathbb R^n$. This solution is the projection of $x_0$ along the range of $A$ onto the nullspace of $A$. With high probability, we have found a non-trivial nullspace vector.

Similar ideas can be applied to many other Krylow space iterative methods. Whereas I have been told that this trick is generally known, it seems to be folklore. But it seems to be too useful for me to not even have a proper name.

Does this "trick" have a proper name, and why does it lead such a shadowy existence?

-
 Seriously? Nothing to tell about that? – Martin Aug 12 '12 at 12:47 I'm not able to answer this question, but there are a few points that I do not understand. Are you interested in just a few vectors of the null space, or in an orthonormal basis? If matrix $A$ arises from the discretization of a differential operator, then usually the null space is known; which applications do you have in mind for which it useful to compute some/all vectors of the null space? – Stefano M Aug 12 '12 at 16:01 I am interested in a orthonormal basis for the nullspace. The matrices which I deem suitable for this come from numerical electromagnetism; the kernel has a small dimension, and a priori the kernel is not known. – Martin Aug 13 '12 at 10:16 SVD is too expensive? It gives a basis for the Nullspace. – Gabriel Landi Aug 16 '12 at 23:42 I'm confused. Most Krylov methods require that $b$ be nonzero, otherwise you end up with a trivial Krylov subspace. – Aron Ahmadia Aug 17 '12 at 20:18
show 2 more comments

1 Answer

Ilic et al (2007) wrote a paper to describe an alternative technique to solve a system of linear equations. The paper can be found at http://dx.doi.org/10.1002%2fnla.509. A portion of this algorithm is the computation of the nullspace of a large sparse matrix.

As I recall, the technique described is only exhibited when the nullity of $A$ is one. I do believe that the theoretical results hold for higher nullities.

-