存储与工作量

在表5.1的最后几列中，我们给出了因式分解所需的存储量和工作量的估计。

“向量数量”

表示需要存储多少个向量。2的含义是显而易见的；“中等”意味着所需向量数是所求特征值数量m的倍数，例如3m到5m。“少量”比中等更少，例如m+10，而“大量”则更多。

“分解”

指示是否需要额外的矩阵存储。“LL^{\ast}”表示稀疏的Cholesky分解，“LDL^{\ast}”表示稀疏的对称非定态高斯消元法，而“ILU”是不完全分解。它应该比其他两种方法更紧凑，需要的算术工作量更少。

我们注意到，诸如计算小于给定实数\alpha或位于给定区间[\alpha, \beta]内的A - \lambda B的特征值数量这样的任务，并不需要计算特征值，因此可以便宜得多。关键工具是矩阵惯性，如第4.1节（第页）所述。假设B为正定矩阵，这一方法可以很容易地扩展到A - \lambda B的情况。总之，设

A - \alpha B = L_{\alpha} D_{\alpha} L^T_{\alpha}, \quad A - \beta B = L_{\beta} D_{\beta} L^T_{\beta}

分别为矩阵A - \alpha B和A - \beta B的LDL^{T}分解，我们假设D_{\alpha}和D_{\beta}是非奇异的对角矩阵。关于LDL^{T}分解的软件可用性信息，请参阅第10.3节。然后，A - \lambda B在[\alpha, \beta]区间内的特征值数量等于\nu(D_{\beta}) - \nu(D_{\alpha})，其中\nu(D)表示负对角元素的数量。