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
Osborne [346] first noted that the norm of a matrix can often be reduced
with a similarity transform of the form
(120) |
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.