7
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ Seriously? Nothing to tell about that? $\endgroup$
    – shuhalo
    Commented Aug 12, 2012 at 12:47
  • $\begingroup$ 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? $\endgroup$
    – Stefano M
    Commented Aug 12, 2012 at 16:01
  • $\begingroup$ 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. $\endgroup$
    – shuhalo
    Commented Aug 13, 2012 at 10:16
  • $\begingroup$ SVD is too expensive? It gives a basis for the Nullspace. $\endgroup$
    – Gabriel Landi
    Commented Aug 16, 2012 at 23:42
  • $\begingroup$ I'm confused. Most Krylov methods require that $b$ be nonzero, otherwise you end up with a trivial Krylov subspace. $\endgroup$
    – Aron Ahmadia
    Commented Aug 17, 2012 at 20:18

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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