A Block Ordering Method for Sparse Matrices

Block iterative methods used for the solution of linear systems of algebraic equations can perform better when the diagonal blocks of the corresponding matrix are carefully chosen. A method is presented based on combinatorial considerations which permutes the rows and columns of a general matrix in such a way that relatively dense blocks of various sizes appear along the diagonal. The method is particularly useful when no natural partitioning of the matrix is available. Two parameters govern the method which is $O(n + \nu )$ in time and space, where n is the order of the matrix and $\nu $ is the number of nonzeros in the matrix. Numerical test results are presented which illustrate the performance of both the ordering algorithm and the block iterative methods with the resulting orderings.