### 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