直接线性求解器简述
  J. Demmel, P. Koev, and X. Li

本书中许多最有效的方法，特别是那些使用位移反转的方法，需要求解形如 (A-\sigma I)x=b 或 (A - \sigma I)^*x=b 的线性系统，其中 \sigma 是一个位移，通常选择为 A 的近似特征值。在这些方法中，大部分时间可能都花在求解这些系统上，因此使用最佳方法至关重要。

求解 (A-\sigma I)x=b 有两种基本方法：直接法和迭代法。直接法通常采用高斯消元的变体。即使在 \sigma 接近特征值且 A-\sigma I 接近奇异时，直接法仍然有效，而此时迭代法最难收敛。第10.4节讨论了迭代求解器以及它们在某些特征值算法（如Jacobi-Davidson算法）中的有效应用。本节仅考虑直接法。

求解 (A-\sigma I)x=b 的直接法包括两个步骤：

1. 计算 A-\sigma I 的分解。这是最昂贵的部分。
2. 利用分解求解 (A-\sigma I)x=b 或 (A - \sigma I)^*x=b。

步骤1通常比步骤2成本高得多（例如，在稠密情况下为 O(n^3) 对 O(n^2)）。分解可以重复用于求解多个不同右端 b 的 (A-\sigma I)x=b。只有当位移 \sigma 改变时，才需要重新计算分解。幸运的是，大多数迭代方法会求解多个具有相同位移但右端不同的线性系统，因此步骤1的执行次数远少于步骤2。

步骤1和步骤2的算法选择取决于 A-\sigma I 的数学结构和 A 的存储结构。数学结构通常指的是 A-\sigma I 是否为厄米矩阵或非厄米矩阵，以及是否为定矩阵或不定矩阵。

厄米且定矩阵：

此时我们计算Cholesky分解
A - \sigma I = \pm LL^T，其中 L 是下三角矩阵。符号的选择取决于 A-\sigma I 是正定矩阵（+）还是负定矩阵（-）。在稀疏情况下，我们可能改为计算 A - \sigma I = \pm PLL^*P^*，其中 P 是置换矩阵。

厄米且不定矩阵：

此时我们计算厄米不定分解 A - \sigma I = PLDL^*P^*，其中 L 是下三角矩阵，P 是置换矩阵，D 是块对角矩阵，块大小为1x1或2x2，或者可能是三对角矩阵。

非厄米矩阵：

此时我们计算三角分解 A - \sigma I = P_1 LU P_2，其中 L 是下三角矩阵，U 是上三角矩阵，P_1 和 P_2 是置换矩阵（有时省略一个 P_i）。

还有许多其他结构和分解方法，例如当 A 是Toeplitz矩阵时（a_{i,j} 仅依赖于 i-j）。

存储结构指的是密集、带状、稀疏（采用第10.1节描述的格式之一）或结构化（例如存储Toeplitz矩阵的第一行和第一列，这决定了其他条目）。稀疏非厄米矩阵也可以存储在稀疏厄米数据结构中，如第10.1节所述。

针对这些数学和存储结构的许多组合，有专门的算法和软件，选择正确的算法可以使大型矩阵的求解时间产生数量级的差异。本节总结了这些问题可用的最佳算法和软件。通常情况下，研究论文中的最佳算法并未作为设计良好且易于访问的软件提供，我们将重点介绍可用的软件。我们推荐维护良好且在公共领域或以低成本提供的软件，除非没有此类软件。

我们考虑四种情况：密集矩阵的方法、带状矩阵的方法、稀疏矩阵的方法以及Toeplitz矩阵等结构化矩阵的方法。