ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Tropical Algebra in Numerical Linear Algebra

Thu 12:00–12:30, Room AV 01.12
Max-balanced Hungarian scalings
Jennifer Pestana (University of Strathclyde)
Joint work with James Hook (University of Manchester); Fran{\c c}rise Tisseur (University of Manchester)

Before solving linear systems with nonsymmetric coefficient matrices by sparse direct or iterative methods one may apply a Hungarian scaling and optimal assignment permutation. Scaling and permuting in this way results in a matrix with entries of modulus one on the diagonal, and of modulus at most one off the diagonal.

What is perhaps not widely appreciated in matrix computations is that a matrix usually has many Hungarian scalings, which may behave quite differently under direct or indirect solvers. In this talk we use tropical algebra to characterize the set of Hungarian scalings. We then discuss one particular Hungarian scaling, the max-balancing scaling, which minimizes the largest off-diagonal entries in the matrix. The result is a matrix that tends to be diagonally dominant than one computed with the standard approach. This may be beneficial for both direct and iterative solvers, as our numerical experiments show.