### Abstract

8 research into Hungarian scaling of linear systems is that a given matrix typically has a range of 9 possible Hungarian scalings and direct or iterative solvers may behave quite differently under each of 10 these scalings. Since standard algorithms for computing Hungarian scalings return only one scaling, 11 it is natural to ask whether a superior performing scaling can be obtained by searching within the 12 set of all possible Hungarian scalings. To this end we propose a method for computing a Hungarian 13 scaling that is optimal from the point of view of a measure of diagonal dominance. Our method uses 14 max-balancing, which minimizes the largest off-diagonal entries in the scaled and permuted matrix.

15 Numerical experiments illustrate the increased diagonal dominance produced by max-balanced Hun-

16 garian scaling as well as the reduced need for row interchanges in Gaussian elimination with partial

17 pivoting and the improved stability of LU factorizations without pivoting. We additionally find that

18 applying the max-balancing scaling before computing incomplete LU preconditioners improves the 19 convergence rate of certain iterative methods. Our numerical experiments also show that the Hun-

20 garian scaling returned by the HSL code MC64 has performance very close to that of the optimal

21 max-balanced Hungarian scaling, which further supports the use of this code in practice.

Language | English |
---|---|

Pages | 320-346 |

Journal | SIAM Journal On Matrix Analysis and Applications (SIMAX) |

Volume | 40 |

Issue number | 1 |

Early online date | 26 Feb 2019 |

DOIs | |

Status | Published - 2019 |

### Cite this

*SIAM Journal On Matrix Analysis and Applications (SIMAX)*,

*40*(1), 320-346. https://doi.org/10.1137/15M1024871

**MAX-BALANCED HUNGARIAN SCALINGS.** / Hook, James; Pestana, Jennifer; Tisseur, Francoise; Hogg, Jonathan .

Research output: Contribution to journal › Article

*SIAM Journal On Matrix Analysis and Applications (SIMAX)*, vol. 40, no. 1, pp. 320-346. https://doi.org/10.1137/15M1024871

}

TY - JOUR

T1 - MAX-BALANCED HUNGARIAN SCALINGS

AU - Hook, James

AU - Pestana, Jennifer

AU - Tisseur, Francoise

AU - Hogg, Jonathan

PY - 2019

Y1 - 2019

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

U2 - 10.1137/15M1024871

DO - 10.1137/15M1024871

M3 - Article

VL - 40

SP - 320

EP - 346

JO - SIAM Journal On Matrix Analysis and Applications (SIMAX)

T2 - SIAM Journal On Matrix Analysis and Applications (SIMAX)

JF - SIAM Journal On Matrix Analysis and Applications (SIMAX)

SN - 0895-4798

IS - 1

ER -