Balancing Matrices
  T. Chen and J. Demmel

Numerical algorithms that compute the eigenvalues of a nonsymmetric matrix $A$ typically make roundoff errors of size roughly $\epsilon_M\Vert A\Vert$, where $\epsilon_M$ is the machine precision. Therefore, applying a simple and accurate similarity transform
$DAD^{-1}$ to reduce the norm of the matrix $A$, or to reduce the condition numbers of some subset of $A$'s eigenvalues, can make the computed eigenvalues of $A$ more accurate.

For example, consider the matrix

$$A = \left[ \begin{array}{ccc} 1&0&10^{-4}\\ 1&1&10^{-2}\\ 10^4&10^2&1 \end{array} \right].$$

Choosing $D = \mbox{diag}(100, 1, .01)$ gives

$$B=DAD^{-1}=\left[\begin{array}{ccc}1&0&1\\ 10^{-2}&1&1\\ 1&1&1\end{array}\right].$$

Whereas $\vert\vert A\vert\vert _F$ is approximately $10^4$, $\vert\vert B\vert\vert _F$ is approximately $2.6$. Furthermore, the condition numbers of the eigenvalues of $B$ are all approximately $1$, whereas the condition numbers of the eigenvalues of $A$ range in magnitude from $10^1$ to $10^3$.

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

$$B=DAD^{-1},$$ (120)

where $D$ is a diagonal matrix. Looking at irreducible matrices and ignoring their diagonal elements, Osborne also proved that the $D$ which minimizes $\vert\vert B\vert\vert _F$ also balances $B$ in the $2$-norm: a matrix is balanced in the $\alpha$-norm if for any $i$, the $\alpha$-norm of row $i$ is the same as the $\alpha$-norm of column $i$. He introduced the first balancing algorithm, which repeatedly sweeps through the diagonal entries of $D$, updating $D_{ii}$ to balance row and column $i$.

Although balancing in the $2$-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.