Sparse LU for block-sparse matrices

Question

I frequently need to solve linear systems with sparse matrices of moderate dimension (say a few thousand). These matrices are composed entirely of small dense blocks (typically 5-10 in dimension), and the overall block structure is sparse (with a pattern like in a PDE spatial discretization). Currently I am just feeding these to UMFPACK, but I am wondering if there are specialized methods that can take advantage of the dense blocks. I anticipate seeing matrices where these dense blocks can be dozens to a few hundred in dimension, with the overall block pattern maintaining sparsity. For larger dense blocks it seems like there would be a much greater advantage to knowing about the block structure.

Answer 1

I believe that UMFPACK will do a good job not just supporting the dense blocks in your original matrix but any dense blocks that appear in the LU factors during decomposition. UMFPACK, like most state-of-the-art sparse solvers, uses what are commonly called "supernodal" techniques to identify and then exploit these dense blocks to significantly improve performance.

The sparse solver, SuperLU, http://crd-legacy.lbl.gov/~xiaoye/SuperLU/ also uses supernodal techniques (that's what "Super" refers to) so you might consider comparing its performance to UMFPACK for your particular class of problem.