Max-Balanced Hungarian Scalings

A Hungarian scaling is a diagonal scaling of a matrix that is typically appliedalong with a permutation to a sparse linear system before calling a direct oriterative solver. A matrix that has been Hungarian scaled and reordered has allentries of modulus less than or equal to 1 and entries of modulus 1 on thediagonal.An important fact that has been overlooked by the previous research intoHungarian scaling of linear systems is that a given matrix typically has a rangeof possible Hungarian scalings and direct or iterative solvers may behave quitedifferently under each of these scalings.Since standard algorithms for computing Hungarian scalings return only onescaling, it is natural to ask whether a superior performing scaling can beobtained by searching within the set of all possible Hungarian scalings. To thisend we propose a method for computing a Hungarian scaling that is optimal fromthe point of view of diagonal dominance.Our method uses max-balancing, which minimizes the largest off-diagonal entriesin the matrix.Numerical experiments illustrate the increased diagonal dominance produced bymax-balanced Hungarian scaling as well as the reduced need for row interchangesin Gaussian elimination with partial pivoting and the improved stability of LUfactorizations without pivoting.We additionally find that applying the max-balancing scaling before computingincomplete LU preconditioners improves the convergence rate of certainiterative methods.