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

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.