Abstract:
Envelope methods for solving sparse systems of linear equations require
the matrix to be reordered so that the nonzeros are near the diagonal.
Optimal reorderings are known to be NP-complete, but a variety of
heuristics have been proposed. In this paper we describe a
multilevel approach for finding small envelope orderings and related
ordering problems.
We show that our approach generally produces better answers than traditional
methods based on a breadth first traversal of the graph of the matrix,
while our run-times are significantly faster than methods which require
the computation of the Fiedler vector of the graph (spectral methods).
The main competitor to our algorithm would be the recent version
of the Sloan algorithm due to Kumfert and Pothen, which
runs faster and often produces better quality orderings.
Our algorithm allows the user to easily adjust the time-quality
trade-off by tuning a single parameter.
Many sparse matrices arise from the discretization of structures in two or three dimensions (grids or meshes). The coordinates of the grid points are then readily available. We describe a version of our algorithm that utilizes such geometry information. This technique can also be used in multilevel graph partitioning.