We will refer to the traditional dense balancing algorithm, found
in LAPACK, as xGEBAL. It consists of two phases, fully described
in [361].
The first phase permutes the rows
and columns of the matrix so that rows which isolate an
eigenvalue are at the bottom of the matrix and columns which
isolate an eigenvalue are at the left of the matrix. Because
the algorithm assumes balancing is done to improve the accuracy
of computed eigenvalues, there is no reason to balance these
rows and columns from which eigenvalues can already be determined
exactly. The second phase of the algorithm balances the matrix
by iterating over the remaining rows and columns--each row/column
pair is balanced in turn until significant progress can no longer be
made.
The sparse implementation, SPBALANCE, takes as input a matrix
in column compressed format; see §10.1.
Instead of permuting a matrix to be as
upper triangular as possible, SPBALANCE finds a permutation
that makes
as block upper triangular as possible, in the
sense of maximizing the number of diagonal blocks. This reduces the
eigenvalue problem to the easier problem of finding the eigenvalues
of each diagonal block. As the blocks found by SPBALANCE may
be much smaller than those found by GEBAL, the eigenproblem may
be easier. For example, on the 2000 by 2000 tolosa matrix [28],
SPBALANCE found
blocks of maximum size
, whereas GEBAL found
blocks of maximum size
. In addition to the permutation and
scaling arrays returned by LAPACK's xGEBAL, SPBALANCE
also returns the number of diagonal blocks found and the indices of
the diagonal blocks.
The balancing phase
of SPBALANCE, done on the individual diagonal blocks found
in the permuting phase, performs
the same balancing algorithm used in GEBAL, but
on a sparse matrix data structure and running in time,
where
is the number of nonzeros.
In our experiments SPBALANCE is much cheaper than the
subsequent eigenvalue computation.
SPBALANCE is the algorithm of choice when the matrix entries
are given explicitly.