In minisymposium: Tropical Algebra in Numerical Linear AlgebraThu 12:00–12:30, Room AV 01.12
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.