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.