Bilkent University
Department of Computer Engineering


A Hypergraph-partitioning-based Matrix Reordering Algorithm for Profile Reduction


Seher Acer
PhD Student
Computer Engineering Department
Bilkent University

The profile of a symmetric matrix is defined as the sum of the distance of the first non-zero entry of a row to the diagonal over all rows. Methods for solving large sparse systems of linear equations usually require the profile of the matrix to be small for both efficiency and less storage. The problem of reordering a given matrix for minimum profile is known to be NP-hard, but a variety of heuristics have been proposed. In this work, we propose a hypergraph-partitioning-based matrix reordering algorithm for profile reduction which uses fixed vertices in recursive-bisection paradigm. The algorithm reduces the profile of a given matrix by basically finding reorderings that move the non-zeros below the diagonal right and up as much as possible at each recursive-bisection step. We compared our results with those of several well-known and commonly-used profile reduction algorithms on three data-sets that were often used for this problem. Our algorithm achieves about 20% improvement in average, compared to the results of the best of the existing profile reduction algorithms.


DATE: 11 November, 2013, Monday @ 15:40