Finding Exact and Approximate Block Structures for ILU Preconditioning

Sparse matrices which arise in many applications often possess a block structure that can be exploited in iterative and direct solution methods. These block-matrices have as their entries small dense blocks with constant or variable dimensions. Block versions of incomplete LU factorizations which have been developed to take advantage of such structures give rise to a class of preconditioners that are among the most effective available. This paper presents general techniques for automatically determining block structures in sparse matrices. A standard "graph compression" algorithm used in direct sparse matrix methods is considered along with two other algorithms which are also capable of unraveling approximate block structures.