What's the most efficient way to solve a sparse linear system Ax = b?

In my project I have to solve an over-determined linear system Ax = b, where A is a large and sparse non-square matrix. We've explored A to have the following structural properties:

As can be seen above, A can be divided into two parts: the left part is a block diagonal matrix, which is ideal for solving linear systems. However the right part is a concatenation of several block diagonal matrices, which complicated to problem.

We've studied this structure for weeks but hasn't found an efficient solver that recognizes this structure. So far the best way to solve this is by sparse(A) \ b, which is way faster than pinv(A)*b or simply A\b. We believe there is still room for improvement because now only sparsity is exploited, not the structure.

Does anyone have any advice on how to solve this linear system more efficiently? BTW, what's the computational complexity for sparse(A) \ b?

Thanks in advance!

[Stephen23]

The most efficient and accurate way is also to use \, just as the documentation recommends. If the data is truly sparse then it should be stored as a sparse matrix, then using \ lets MATLAB pick an efficient algorithm. You are unlikely to find anything better. See also related discussions:

https://www.mathworks.com/matlabcentral/answers/323708-is-there-a-faster-way-to-multiply-a-sparse-and-full-matrix-than-standard-multiplication-in-matlab

https://www.mathworks.com/matlabcentral/answers/7058-are-iterative-methods-always-better-than-direct-methods-for-solving-large-linear-systems

https://www.mathworks.com/matlabcentral/answers/309690-improving-performance-of-x-a-b

Answer 1

[KSSV]

If you have GPU, you may consider using mldivide which is same as A\B..and might be faster. YOu can read it here, how the \ works:

http://in.mathworks.com/help/matlab/ref/mldivide.html

Answer 2

[Jess]

There are very few cases where the `\` operator isn't the fastest and roughly the most accurate. I've done a lot of testing of this against other algorithms and packages in the numerical science community. It's really top-notch for almost all cases. For the cases that it wasn't great, it usually had slightly less accuracy than other methods.