4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

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.