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 is not given explicitly, we assume functions for computing and are available. (See [82] for a description of KRYLOVAZ, a Krylov algorithm which uses only and not .) In line (1) can be approximated by multiplying with a vector of random s and taking the largest component of the absolute value of the result.

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