I have a large sparse matrix A which is column rank-defficient. Typical size of A is over 100000x100000. In my computation, I need the matrix W whose columns span the null space of A. But I do not know how to fastly compute all the columns of W.
If A is small-scale, I know there are several numerical methods based on matrix factorization, such as LU, QR, SVD. But for large-scale matrices, I can not find an efficient iterative method to do this.
Could you please give me some help?
If you apply the sparse methods
available to solve the linear system: A( n by n) *x (n by 1) = 0 ( n by 1), you will get one null space solution x1(n by 1)
Solve now for the Augmented linear system : Ax=0 and x1*x= 0, you will get a null space vector x2 which is also orthogonal to x1.
Proceeding this way recursively, the matrix W can be constructed as the array of the set of mutually orthogonal column vectors: x1, x2,.. and so on.
If the matrix is sparse then a sparse LU will enable you to compute the null space. (Row &/or column swaps (= pivoting) may be necessary or useful to keep memory and time costs low.) But otherwise this will become very expensive. Even just storing such a matrix would take (in double precision floating point) over 80GB. Any solver would be an out-of-core type of solver, but would be extremely expensive.
An alternative, if the matrix is real symmetric, is to use the Lanczos method or a variant such as the Lehoucq & Sorensen ARPACK method. More precisely, ARPACK is a restarted Arnoldi method. Then you look for when you have the zero eigenvalue (or simply a very small eigenvalue). The corresponding eigenvector(s) gives a basis for the null space. ARPACK is a semi-iterative method, and so there is a trade-off between the accuracy of the eigenvalues (and eigenvectors) and the number of iterations performed.
- Badges
- Science topic
- Similar topics
- Biological Science
- Microbiology
- Microorganisms
- Bacteria