2
$\begingroup$

Are there any special algorithms which solves a sparse linear system efficiently when the rhs of the system has only a few nonzero elements or the the rhs is a basis vector ?

Edit:

The size of the matrix has commonly more than a few ten thousand entries and is complex, unsymmetric but square. I want to calculate the solution to the system many times but not more than the size of the rhs. The rhs changes but has a constant number in the range of 1 to 200 non zero entries. This value is fix, but the position in the vector change for each run.

$\endgroup$
4
  • $\begingroup$ How large is the matrix? Krylov subspace methods use matrix-vector multiplications so at least those iterations will be possible to perform extremely fast although many might be needed. $\endgroup$ – mathreadler Jul 6 '16 at 9:24
  • $\begingroup$ Maybe even using the geometric series $(I-A)^{-1} = I+A+A^2+\cdots$ could be fruitful. $\endgroup$ – mathreadler Jul 6 '16 at 9:29
  • $\begingroup$ "or the rhs is a basis vector" - i.e. you want a particular column of the inverse? $\endgroup$ – J. M. isn't a mathematician Jul 6 '16 at 14:37
  • $\begingroup$ so to say, yes. a column of the inverse is what I get when solving with with a basis vector ... $\endgroup$ – JaW. Jul 7 '16 at 11:36
1
$\begingroup$

Suppose we want to find solution to $AX = Y$ where $A$ is a sparse matrix and $Y$ is a sparse vector.

Even if $Y$ is sparse you still need to factorize the matrix $A$ for example using the LU factorization $LU = PAQ$, where $P$, $Q$ are permutation matrices. Then $X = QU^{-1}L^{-1}PY$.

The only places, where the sparsity of $Y$ can be used, are triagular solves $L^{-1}z$ and $U^{-1}w$ with sparse triangular matrices $L$, $U$, sparse vector $z$ and possibly sparse vector $w$ (in general $w$ can be dense).

There are specialized algorithms for solving sparse triangular systems with sparse RHS, mathematically equivalent to triangular solvers with dense RHS, but with very different implementation.

In general factorization step cannot be avoided or simplified when RHS is sparse.

Iterative solvers are not helpful here, since they always assume, that RHS is dense.

$\endgroup$
2
  • $\begingroup$ "There are specialized algorithms for solving sparse triangular systems with sparse RHS, mathematically equivalent to triangular solvers with dense RHS, but with very different implementation." can you point me to some references for that? $\endgroup$ – JaW. Jul 8 '16 at 8:01
  • $\begingroup$ implementation of triangular solver with sparse RHS can be found in Davis, Timothy A. Direct methods for sparse linear systems. Vol. 2. Siam, 2006. Implementation can be found in SuiteSparse library created by T. Davis. Sparse LU solvers usualy does not support sparse RHS. The only solver I know, which supports sparse RHS, is MUMPS. In this library you may also find implementation of this algorithm. $\endgroup$ – Pawel Kowal Jul 8 '16 at 12:16
0
$\begingroup$

There are bunch of solvers that can do that. You can look for a reference here: https://eigen.tuxfamily.org/dox/group__TopicSparseSystems.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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