Balancing sparse matrices for computing eigenvalues

Applying a permuted diagonal similarity transform DPAP(T)D(-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 randomized balancing algorithms for matrices that are not given explicitly, i.e. given a vector x, we can compute only Ax and perhaps A(T)x. 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. (C) 2000 Elsevier Science Inc. All rights reserved.