Performance of matlab direct linear solver with respect to sparsity

Hi,

I'm using Matlab's direct linear solver (backslash operator) to solver a linear system generated from a mixed finite element discretization. Matlab says the matrix is sparse, when checked for sparsity (issparse()), however I know that the stiffness matrix is not that sparse compared to a conventianal finite element discretization. Now I have two questions,

1. I would like to know the effect of sparsity on the linear solver, lets say if the sparsity is increased, will the solver have the same performance, my benchmark for sparsity would be the sparsity of a stiffness matrix generated from a displacement based finite element.
2. I also see that the solver performes much better when I use full matrix (initiallise the stiffness matrix as zeros) compared to sparse. It looks like mutli-threading is fully exploited when full matrices are used (correct me if I'm wrong).

My stiffness matrix is not that big, close to 1e5.

Cheers,

ben

Answer 1

[Christine Tobler]

For sparse matrices, the performance of backslash depends a lot on the specific structure of that sparse matrices (where the nonzeros are placed).

In general, if a dense matrices was stored in sparse format, the backslash command would be slower for that than if it was in stored as a full matrix. This is because the sparse format is trying to exploit sparsity, but the matrix isn't actually sparse. In fact, a matrix needs to have significantly more zeros than nonzeros for a sparse solver to be faster than just calling the dense version.

So if you have tried this out and found that for your matrices, dense is faster than sparse, it's a good idea to stick to that. It's true that sparse algorithms are harder to thread than dense ones, so that can definitely be a factor - some of the sparse solvers do exploit threading, but in a less effective way than the dense ones.

Just to reiterate: The distribution of the nonzeros within a sparse matrix has a large impact on the performance of its solver, just knowing the size and the number of nonzeros isn't enough to predict the speed. The first step in a linear solver is to factorize the matrix (for example, compute triangular matrices L and U with A = L*U). For a sparse matrix, the L and U matrix might have many more nonzeros than the original A - this depends on the sparsity structure of A, and it's why that has a huge impact on performance.

[bensingh dhas]

Thanks for you kind answer. I understand you point that the sparsity pattern has a lot ot do with the efficiency of the solver.

Does matlab have a solver that is suitable for linear equations comming from saddle point problems?