VBARMS: A variable block algebraic recursive multilevel solver for sparse linear systems

Sparse matrices arising from the solution of systems of partial differential equations often exhibit a perfect block structure, meaning that the nonzero blocks in the sparsity pattern are fully dense (and typically small), e.g., when several unknown quantities are associated with the same grid point. Similar block orderings can be sometimes unravelled also on general unstructured matrices, by ordering consecutively rows and columns with a similar sparsity pattern, and treating some zero entries of the reordered matrix as nonzero elements, with a little sacrifice of memory. We show how we can take advantage of these frequently occurring structures in the design of the multilevel incomplete LU factorization preconditioner ARMS (Saad and Suchomel, 2002 [14]) and maximize computational efficiency. (C) 2013 Elsevier B.V. All rights reserved.