Direct Balancing

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 $A$ 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 $P$ that makes $PAP^T$ 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 $1529$ blocks of maximum size $90$, whereas GEBAL found $1146$ blocks of maximum size $854$. 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 $O(N_z)$ time, where $N_z$ 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.