Krylov Balancing Algorithms

Direct balancing algorithms such as GEBAL and SPBALANCE calculate exact row and column norms, making them inappropriate for sparse matrices whose entries are not given explicitly. In [81] and [82] we describe three new balancing algorithms which use only Krylov information, i.e., matrix-vector and/or matrix-transpose-vector multiplies, to access the original matrix. The KRYLOVCUTOFF algorithm, Algorithm 7.1, performs best of all three Krylov algorithms on our test matrices.

Since $A$ is not given explicitly, we assume functions for computing $Az$ and $A^Tz$ are available. (See [82] for a description of KRYLOVAZ, a Krylov algorithm which uses only $Az$ and not $A^Tz$.) In line (1) $\vert\vert A\vert\vert _{\infty}$ can be approximated by multiplying $A$ with a vector of random $\pm 1$s and taking the largest component of the absolute value of the result.

The number of iterations $t$ and the value of cutoff are left to the user since the best stopping criteria and cutoff value can depend on the matrix $A$. Based on experimental evidence, we chose default values of $5$ for $t$ and $10^{-8}$ for cutoff. This means that balancing costs at most 10 matrix-vector multiplications, and so is probably very cheap compared to subsequent eigenvalue calculations.