我们将传统稠密平衡算法，即LAPACK中的xGEBAL，分为两个阶段，详细描述见[361]。 第一阶段对矩阵A的行和列进行置换，使得能够单独分离出一个特征值的行位于矩阵底部，而能够单独分离出一个特征值的列位于矩阵左侧。由于该算法假设平衡操作旨在提高计算特征值的准确性，因此没有必要对这些已经可以精确确定特征值的行和列进行平衡。第二阶段通过迭代剩余的行和列对矩阵进行平衡——每对行/列依次进行平衡，直到无法再取得显著进展为止。
稀疏实现SPBALANCE的输入是一个采用列压缩格式的矩阵；详见第10.1节。 与将矩阵置换为尽可能上三角形式不同，SPBALANCE寻找一个置换P，使得PAP^T尽可能块上三角化，即最大化对角块的数量。这使得特征值问题简化为寻找每个对角块特征值的较易问题。由于SPBALANCE找到的块可能远小于GEBAL找到的块，因此特征值问题可能更为简单。例如，在2000 x 2000的tolosa矩阵[28]上，SPBALANCE找到了1529个最大尺寸为90的块，而GEBAL找到了1146个最大尺寸为854的块。除了LAPACK的xGEBAL返回的置换和缩放数组外，SPBALANCE还返回找到的对角块数量及其索引。
SPBALANCE的平衡阶段，针对置换阶段发现的对角块进行，采用与GEBAL相同的平衡算法，但在稀疏矩阵数据结构上运行，时间复杂度为O(N_z)，其中N_z为非零元素的数量。在我们的实验中，SPBALANCE比后续的特征值计算成本低得多。当矩阵元素明确给出时，SPBALANCE是首选算法。