PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 19 February 2004

Maximum-weighted matching strategies and the application to symmetric indefinite systems

Stefan Röllin$^1$ and Olaf Schenk$^2$
$^1$ Integrated Systems Laboratory
Swiss Federal Institute of Technology Zurich
ETH Zurich, CH-8092 Zurich, Switzerland
email: roellin@iis.ee.ethz.ch
$^2$ Departmentof Computer Science Departement
University Basel, Klingelbergstrasse 50
CH-4056 Basel, Switzerland
email: olaf.schenk@unibas.ch

It is now commonly known that maximum-weighted bipartite matching algorithms [2] - devel-oped to place large entries on the diagonal using unsymmetric permutations and scalings - greatly enhance the reliability of linear solvers for unsymmetric linear systems. The goal is to transform the coefficient matrix A with diagonal scaling matrices D_r and D_c and a permutation matrix P_r so as toobtain an equivalent system with a matrix P_rD_rAD_c that is better scaled and more diagonally dom-inant. This preprocessing has a beneficial impact on the accuracy of the solver and it also reduces the need for partial pivoting, thereby speeding up the factorization process. These maximum-weightedmatchings are also applicable to symmetric indefinite systems, but the symmetry of the indefinite systems is lost. Nevertheless, modified weighted matchings can be used for these systems. The goalis to preserve symmetry and to define a symmetric permutation, such that the large elements of the permuted matrix lie on (p * p) diagonal blocks (not necessarily on the diagonal as for unsymmetricmatrices). This technique based on numerical criterion was first presented by Gilbert and Duff [3] and further extended using a structural metric by Duff and Pralet [4]. They limited the block sizeof the diagonal blocks to one or two for Bunch and Kaufmann pivoting with MA57.

Larger diagonal blocks can also be used, but a larger fill-in is to be expected. On the other hand, one has other possibilities to define a weighted matching for indefinite symmetric systems. We willpresent a modification of the maximum-weighted bipartite matching for symmetric indefinite systems and will report numerical experiments on a large set of indefinite symmetric systems. Furthermore,we will compare our symmetric weighted matching method with the PARDISO [1] static Bunch andKaufmann pivoting method that has been evaluated in [5].

References:
1. PARDISO website. http://www.computational.unibas.ch/cs/scicomp/software/pardiso/.
2. I. S. Duff and J. Koster. On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM J. Matrix Analysis and Applications, 22(4):973-996, 2001.
3. I.S. Duff and J.R. Gilbert. Maximum-weighted matching and block pivoting for symmetric indefinite systems. In In Abstract book of Householder Symposium XV, June 17-21, 2002.
4. I.S. Duff and S. Pralet. Symmetric weighted matching and application to indefinite multifrontal solvers. In SIAM Workshop on Combinatorial Scientific Computing (CSC04) , February 25-27, 2004.
5. N.I.M. Gould, Y. Hu, and J.A. Scott. A numerical evaluation of sparse direct solvers for the solution of large sparse, symmetric linear systems of equations. Technical report, Rutherford Appleton Laboratory, 2004. to appear.

Home page