Abstract

Applying a permuted diagonal similarity transform DPAP^TD^{-1} to a matrix A before calculating its eigenvalues can improve the speed and accuracy with which the eigenvalues are computed. This is often called balancing . This report summarizes previous work and presents new results on both the theory and practice of finding good permutation matrices P and good diagonal matrices D. In the theory section we present results on balancing in the infinity norm, including a novel, finite algorithm which runs in O(n^4) time; on weighted balancing, which we define for non-negative, irreducible matrices and prove minimizes the 2-norm of the balanced matrix; and on choosing D to explicitly minimize the condition numbers of eigenvalues. In the section on implementation, we discuss our sparse implementation of the dense algorithm found in several linear algebra packages. Our implementation is faster than the dense algorithm when the density of the matrix is less than or equal to approximately .5. We then discuss a set of algorithms for matrices that are not given explicitly, i.e. the only operation available on the matrix is matrix-vector multiplication and perhaps matrix-transpose-vector multiplication. We motivate these Krylov-based algorithms, then present test results on a set of matrices from applications. On these matrices, one version of our algorithm is found to return matrices whose norms are within a factor of 2.5 of the norm of the balanced matrices returned by the explicit algorithm. We conclude with open questions raised by our report.

The entire report: gzipped postscript