### 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 paper describes
several balancing algorithms for sparse matrices and compares
them against each other and the traditional dense algorithm. We
first discuss our sparse implementation of the dense algorithm;
our code is faster than the dense algorithm when the density of
the matrix is no more than approximately .5, and is much faster
for large, sparse matrices. We next describe a set of balancing
algorithms for matrices that are not given explicitly, i.e. given
a vector x, we can compute only Ax and perhaps A^Tx. We
motivate these Krylov-based algorithms using Perron-Frobenius
theory. Results are given comparing the Krylov-based algorithms
to each other and to the sparse and dense direct balancing
algorithms, looking at norm reduction, running times, and the
accuracy of eigenvalues computed after a matrix is balanced.
We conclude that sparse balancing algorithms are efficient
preconditioners for eigensolvers.
** Key words. ** Balancing, norm minimization, accurate eigenvalues,
sparse matrix algorithms

** AMS subject classifications . ** 65F15, 65F35

The entire report: gzipped postscript