Krylov平衡算法

直接平衡算法如GEBAL和SPBALANCE计算精确的行和列范数，这使得它们不适用于条目未明确给出的稀疏矩阵。在[81]和[82]中，我们描述了三种仅使用克里洛夫信息（即矩阵-向量和/或矩阵转置-向量乘积）来访问原始矩阵的新平衡算法。KRYLOVCUTOFF算法，即算法7.1，在我们的测试矩阵上表现最佳。

由于A未明确给出，我们假设可以计算Az和A^Tz的函数是可用的。（有关仅使用Az而不使用A^Tz的克里洛夫算法KRYLOVAZ的描述，请参见[82]。）在步骤(1)中，\vert\vert A\vert\vert _{\infty}可以通过将A与随机\pm 1向量相乘并取结果绝对值的最大分量来近似。

迭代次数t和cutoff值由用户决定，因为最佳停止准则和cutoff值可能取决于矩阵A。基于实验证据，我们选择了t的默认值为5，cutoff的默认值为10^{-8}。这意味着平衡最多需要10次矩阵-向量乘法，因此与随后的特征值计算相比，成本可能非常低。

算法 7.1: 用于NHEP的Krylov平衡算法(KRYLOVCUTOFF)
(1) \text{normA} = \Vert A\Vert_\infty
(2) for i=1,n, D(i)=1
(3) for j=1,2,..., t
(4)     z = \text{一个长度为} n \text{的随机} \pm 1\text{向量}
(5)     p = D(A(D^{-1}z))
(6)     r = D^{-1}(A^T(Dz))
(7)     for i=1,2,...,n
(8)         if (|p(i)| > \text{cutoff} \cdot \text{normA}) and (r(i) \neq 0)
(9)             D(i) = D(i) \cdot \sqrt{|r(i)/p(i)|}
(10)        end if
(11)    end for
(12) end for