Max-balanced Hungarian scalings

James Hook, Jennifer Pestana, Francoise Tisseur, Jonathan Hogg

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

A Hungarian scaling is a diagonal scaling of a matrix that is typically applied along with a permutation to a sparse linear system before calling a direct or iterative solver. A matrix that has been Hungarian scaled and reordered has all entries of modulus less than or equal to 1 and entries of modulus 1 on the diagonal. An important fact that has been largely overlooked by the previous research into Hungarian scaling of linear systems is that a given matrix typically has a range of possible Hungarian scalings and direct or iterative solvers may behave quite differently under each of these scalings. Since standard algorithms for computing Hungarian scalings return only one scaling, it is natural to ask whether a superior performing scaling can be obtained by searching within the set of all possible Hungarian scalings. To this end we propose a method for computing a Hungarian scaling that is optimal from the point of view of a measure of diagonal dominance. Our method uses max-balancing, which minimizes the largest off-diagonal entries in the scaled and permuted matrix. Numerical experiments illustrate the increased diagonal dominance produced by max-balanced Hungarian scaling as well as the reduced need for row interchanges in Gaussian elimination with partial pivoting and the improved stability of LU factorizations without pivoting. We additionally find that applying the max-balancing scaling before computing incomplete LU preconditioners improves the convergence rate of certain iterative methods. Our numerical experiments also show that the Hungarian scaling returned by the HSL code MC64 has performance very close to that of the optimal max-balanced Hungarian scaling, which further supports the use of this code in practice.
LanguageEnglish
Pages320-346
Number of pages27
JournalSIAM Journal on Matrix Analysis and Applications
Volume40
Issue number1
DOIs
Publication statusPublished - 26 Feb 2019

Fingerprint

Scaling
Diagonal Dominance
Pivoting
Balancing
Computing
Modulus
Numerical Experiment
LU Factorization
Iterative Solver
Iterative Solvers
Sparse Linear Systems
Gaussian elimination
Less than or equal to
Preconditioner
Permutation
Rate of Convergence
Linear Systems
Minimise
Iteration
Partial

Keywords

  • max-plus algebra
  • diagonal scaling
  • Hungarian scaling
  • max-balancing
  • diagonal dominance
  • linear systems of equations
  • sparse matrices
  • incomplete LU preconditioner

Cite this

Hook, James ; Pestana, Jennifer ; Tisseur, Francoise ; Hogg, Jonathan . / Max-balanced Hungarian scalings. In: SIAM Journal on Matrix Analysis and Applications. 2019 ; Vol. 40, No. 1. pp. 320-346.
@article{5dc601c218f94783bbc047d13ad0146c,
title = "Max-balanced Hungarian scalings",
abstract = "A Hungarian scaling is a diagonal scaling of a matrix that is typically applied along with a permutation to a sparse linear system before calling a direct or iterative solver. A matrix that has been Hungarian scaled and reordered has all entries of modulus less than or equal to 1 and entries of modulus 1 on the diagonal. An important fact that has been largely overlooked by the previous research into Hungarian scaling of linear systems is that a given matrix typically has a range of possible Hungarian scalings and direct or iterative solvers may behave quite differently under each of these scalings. Since standard algorithms for computing Hungarian scalings return only one scaling, it is natural to ask whether a superior performing scaling can be obtained by searching within the set of all possible Hungarian scalings. To this end we propose a method for computing a Hungarian scaling that is optimal from the point of view of a measure of diagonal dominance. Our method uses max-balancing, which minimizes the largest off-diagonal entries in the scaled and permuted matrix. Numerical experiments illustrate the increased diagonal dominance produced by max-balanced Hungarian scaling as well as the reduced need for row interchanges in Gaussian elimination with partial pivoting and the improved stability of LU factorizations without pivoting. We additionally find that applying the max-balancing scaling before computing incomplete LU preconditioners improves the convergence rate of certain iterative methods. Our numerical experiments also show that the Hungarian scaling returned by the HSL code MC64 has performance very close to that of the optimal max-balanced Hungarian scaling, which further supports the use of this code in practice.",
keywords = "max-plus algebra, diagonal scaling, Hungarian scaling, max-balancing, diagonal dominance, linear systems of equations, sparse matrices, incomplete LU preconditioner",
author = "James Hook and Jennifer Pestana and Francoise Tisseur and Jonathan Hogg",
year = "2019",
month = "2",
day = "26",
doi = "10.1137/15M1024871",
language = "English",
volume = "40",
pages = "320--346",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "1",

}

Max-balanced Hungarian scalings. / Hook, James; Pestana, Jennifer; Tisseur, Francoise; Hogg, Jonathan .

In: SIAM Journal on Matrix Analysis and Applications, Vol. 40, No. 1, 26.02.2019, p. 320-346.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Max-balanced Hungarian scalings

AU - Hook, James

AU - Pestana, Jennifer

AU - Tisseur, Francoise

AU - Hogg, Jonathan

PY - 2019/2/26

Y1 - 2019/2/26

N2 - A Hungarian scaling is a diagonal scaling of a matrix that is typically applied along with a permutation to a sparse linear system before calling a direct or iterative solver. A matrix that has been Hungarian scaled and reordered has all entries of modulus less than or equal to 1 and entries of modulus 1 on the diagonal. An important fact that has been largely overlooked by the previous research into Hungarian scaling of linear systems is that a given matrix typically has a range of possible Hungarian scalings and direct or iterative solvers may behave quite differently under each of these scalings. Since standard algorithms for computing Hungarian scalings return only one scaling, it is natural to ask whether a superior performing scaling can be obtained by searching within the set of all possible Hungarian scalings. To this end we propose a method for computing a Hungarian scaling that is optimal from the point of view of a measure of diagonal dominance. Our method uses max-balancing, which minimizes the largest off-diagonal entries in the scaled and permuted matrix. Numerical experiments illustrate the increased diagonal dominance produced by max-balanced Hungarian scaling as well as the reduced need for row interchanges in Gaussian elimination with partial pivoting and the improved stability of LU factorizations without pivoting. We additionally find that applying the max-balancing scaling before computing incomplete LU preconditioners improves the convergence rate of certain iterative methods. Our numerical experiments also show that the Hungarian scaling returned by the HSL code MC64 has performance very close to that of the optimal max-balanced Hungarian scaling, which further supports the use of this code in practice.

AB - A Hungarian scaling is a diagonal scaling of a matrix that is typically applied along with a permutation to a sparse linear system before calling a direct or iterative solver. A matrix that has been Hungarian scaled and reordered has all entries of modulus less than or equal to 1 and entries of modulus 1 on the diagonal. An important fact that has been largely overlooked by the previous research into Hungarian scaling of linear systems is that a given matrix typically has a range of possible Hungarian scalings and direct or iterative solvers may behave quite differently under each of these scalings. Since standard algorithms for computing Hungarian scalings return only one scaling, it is natural to ask whether a superior performing scaling can be obtained by searching within the set of all possible Hungarian scalings. To this end we propose a method for computing a Hungarian scaling that is optimal from the point of view of a measure of diagonal dominance. Our method uses max-balancing, which minimizes the largest off-diagonal entries in the scaled and permuted matrix. Numerical experiments illustrate the increased diagonal dominance produced by max-balanced Hungarian scaling as well as the reduced need for row interchanges in Gaussian elimination with partial pivoting and the improved stability of LU factorizations without pivoting. We additionally find that applying the max-balancing scaling before computing incomplete LU preconditioners improves the convergence rate of certain iterative methods. Our numerical experiments also show that the Hungarian scaling returned by the HSL code MC64 has performance very close to that of the optimal max-balanced Hungarian scaling, which further supports the use of this code in practice.

KW - max-plus algebra

KW - diagonal scaling

KW - Hungarian scaling

KW - max-balancing

KW - diagonal dominance

KW - linear systems of equations

KW - sparse matrices

KW - incomplete LU preconditioner

U2 - 10.1137/15M1024871

DO - 10.1137/15M1024871

M3 - Article

VL - 40

SP - 320

EP - 346

JO - SIAM Journal on Matrix Analysis and Applications

T2 - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 1

ER -