# Efficient way to solve a set of linear equations $Ax=b$ when $A$ is sparse and some elements of $b$ are equal to zero

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?

• When solving the triangle systems, you can certainly use the sparseness of $b$. Davis' book on sparse matrix methods is one reference. – vibe Jul 2 '20 at 23:02
• when you say LU, do you mean a dense LU, or a sparse LU solver? – Thijs Steel Jul 3 '20 at 7:36
• Thanks @vibe. I'll refer this book. – HKK Jul 3 '20 at 22:03
• @Thijs Steel, It would be great if I can use a sparse LU solver and still get the advantage of the sparsity of b. – HKK Jul 3 '20 at 22:03
• 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. – 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).