Next: Direct Balancing Up: Non-Hermitian Eigenvalue Problems Previous: Introduction   Contents   Index

# Balancing Matrices   T. Chen and J. Demmel

Numerical algorithms that compute the eigenvalues of a nonsymmetric matrix typically make roundoff errors of size roughly , where is the machine precision. Therefore, applying a simple and accurate similarity transform
to reduce the norm of the matrix , or to reduce the condition numbers of some subset of 's eigenvalues, can make the computed eigenvalues of more accurate.

For example, consider the matrix

Choosing gives

Whereas is approximately , is approximately . Furthermore, the condition numbers of the eigenvalues of are all approximately , whereas the condition numbers of the eigenvalues of range in magnitude from to .

Osborne [346] first noted that the norm of a matrix can often be reduced with a similarity transform of the form

 (120)

where is a diagonal matrix. Looking at irreducible matrices and ignoring their diagonal elements, Osborne also proved that the which minimizes also balances in the -norm: a matrix is balanced in the -norm if for any , the -norm of row is the same as the -norm of column . He introduced the first balancing algorithm, which repeatedly sweeps through the diagonal entries of , updating to balance row and column .

Although balancing in the -norm is equivalent to minimizing the Frobenius norm, balancing a matrix in an arbitrary norm may not have such a simple effect on a matrix norm. Other work discusses the mathematical properties of using diagonal scaling to balance matrices and to minimize matrix norms [81,82]. Focusing on practice instead of theory, we present here two styles of algorithms for balancing sparse matrices. The algorithms are analyzed more thoroughly in [81] and [82]; software can be accessed through the book's homepage, ETHOME.

Subsections

Next: Direct Balancing Up: Non-Hermitian Eigenvalue Problems Previous: Introduction   Contents   Index
Susan Blackford 2000-11-20