# 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? Commented Aug 12, 2012 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? Commented Aug 12, 2012 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. Commented Aug 13, 2012 at 10:16
• SVD is too expensive? It gives a basis for the Nullspace. Commented Aug 16, 2012 at 23:42
• I'm confused. Most Krylov methods require that $b$ be nonzero, otherwise you end up with a trivial Krylov subspace. Commented Aug 17, 2012 at 20:18

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.