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.