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$ Jul 6, 2016 at 9:24
  • $\begingroup$ Maybe even using the geometric series $(I-A)^{-1} = I+A+A^2+\cdots$ could be fruitful. $\endgroup$ Jul 6, 2016 at 9:29
  • $\begingroup$ "or the rhs is a basis vector" - i.e. you want a particular column of the inverse? $\endgroup$ Jul 6, 2016 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, 2016 at 11:36

2 Answers 2

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, 2016 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$ Jul 8, 2016 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .