I have a set of linear equations, $Ax=b$. And about half of the elements in the right-hand side (vector $b$) are equal to zero. My system matrix $A$ is a sparse complex matrix. And $A$ is in the size range of $2000 \times 2000$. I am currently using LU decomposition to solve the system.

Is there a way that I can take both advantages of sparsity and the zero elements in $b$ when solving the set of equations?

  • $\begingroup$ When solving the triangle systems, you can certainly use the sparseness of $b$. Davis' book on sparse matrix methods is one reference. $\endgroup$ – vibe Jul 2 '20 at 23:02
  • $\begingroup$ when you say LU, do you mean a dense LU, or a sparse LU solver? $\endgroup$ – Thijs Steel Jul 3 '20 at 7:36
  • $\begingroup$ Thanks @vibe. I'll refer this book. $\endgroup$ – HKK Jul 3 '20 at 22:03
  • $\begingroup$ @Thijs Steel, It would be great if I can use a sparse LU solver and still get the advantage of the sparsity of b. $\endgroup$ – HKK Jul 3 '20 at 22:03
  • 1
    $\begingroup$ In my experience, unless the dimensions of $b$ are much larger than 2000, sparse right hand sides aren't any faster in practice when solving linear systems. The sparsity of $A$, however, is almost always worth investigating. Most sparse solvers I have encountered won't accept a sparse right hand side, or will just create a temporary dense version of it for the calculations. For instance, Matlab's LU solver uses UMFPACK (written by Davis as mentioned by @vibe), which does not support sparse right hand sides. $\endgroup$ – Charlie S Jul 7 '20 at 16:53

Unfortunately, the problem as stated is not quite restrictive enough to meaningfully exploit. For any "interesting" sparse matrix $\mathbf A$, even if the forcing data $\mathbf b$ is sparse, the solution data $\mathbf x$ will still be fully populated/dense.

However, there is a nearby problem that does have exploitable structure: if $\mathbf b$ is sparse, and you only care about a subset of the entries of $\mathbf x$, then it is possible to find them using less time/space than the naive approach (in which you compute all of $\mathbf x$ and then sift out the ones you want).

Unfortunately this algorithm is not commonplace, but I can at least point you to my own implementation. I think MUMPS might have a similar capability, their names pop up often when you look for these sorts of tricks (sparsity-exploiting backsolves). The earliest mention of this idea that I have found is in a thesis by T. Slavova (who was advised by the MUMPS team).

  • $\begingroup$ Thanks for the explanation. I'm interested in only a subset of x corresponds to the non-zero elements of 'b'. I'll refer the references you mentioned. $\endgroup$ – HKK Oct 1 '20 at 15:20

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.