📚 课程目录第1章课程导入与稀疏线性系统概览

1. 课程导入与稀疏线性系统概览

在科学计算与工程仿真中，我们经常需要求解形如 Ax = b 的线性方程组。当未知量个数 n 达到十万、百万甚至更大时，矩阵 A 中绝大多数元素往往为零——这类矩阵被称为稀疏矩阵，对应的方程组就是稀疏线性系统。本课程围绕"如何高效、稳定地求解这类系统"展开，从数据结构、算法原理到工程实践逐层深入。

什么是稀疏线性系统

严格地说，稀疏性是一个相对概念。工程上常用稀疏度（非零元个数 nnz 与总元素数 n² 之比）或稀疏率来刻画。例如一个 n = 100000 的二维五点差分矩阵，每行仅约 5 个非零元，nnz ≈ 5×10⁵，而总元素数为 10¹⁰，非零占比仅约 5×10⁻⁵。若按稠密方式存储，需要约 80 GB（双精度），而稀疏存储只需几 MB。稀疏性带来的不仅是存储节省，更关键的是计算量从 O(n³) 量级降到与 nnz 相关的量级。

需要强调的是，稀疏矩阵的"零"通常具有结构意义：它代表网格节点之间没有直接耦合、物理量之间没有直接关联。因此稀疏模式本身携带了问题的拓扑信息，这也是后续选择重排序、预条件策略的重要依据。

稀疏系统的典型来源与应用场景

稀疏线性系统几乎遍布所有计算科学与工程领域，常见来源包括：

偏微分方程离散化：有限差分、有限元、有限体积法将连续问题离散为网格上的代数方程，每个节点只与相邻节点耦合，形成带状或块状稀疏矩阵。这是最经典的来源。
网络与图问题：电路仿真中的节点导纳矩阵、社交网络与网页排名（如 PageRank 的迭代）、最短路径与网络流，其矩阵非零模式直接对应图的边。
最小二乘与数据拟合：大规模回归、计算机视觉中的 bundle adjustment，法方程矩阵通常稀疏且对称正定。
马尔可夫链与排队网络：状态转移矩阵的稳态求解，非零元对应可达状态转移。
机器学习与优化：稀疏特征下的逻辑回归、图神经网络中的邻接传播，均涉及稀疏矩阵向量乘。

这些场景的共同点是：问题规模大、矩阵高度稀疏、且往往需要反复求解（如非线性迭代、时间步进中的每步求解）。因此求解器的效率直接决定整体仿真或训练的可行性。

课程目标与学习路径

本课程的目标是让学习者建立"从问题到算法、从算法到实现、从实现到调优"的完整能力链。学习路径大致分为四个层次：

基础层：理解稀疏性、存储格式、稀疏矩阵的基本运算（矩阵向量乘、转置、加法），能正确构造和读写稀疏矩阵。
算法层：掌握直接法（稀疏 LU/Cholesky、填充与重排序）与迭代法（Jacobi、Gauss-Seidel、共轭梯度、GMRES、BiCGSTAB）的原理、收敛条件与适用边界。
加速层：理解预条件技术（对角、ILU、不完全 Cholesky、代数多重网格）如何改善条件数、加速收敛。
实践层：能够针对具体问题选择存储格式与求解器，使用 Eigen、SciPy、PETSc 等工具实现，并通过残差、迭代次数、耗时等指标评估与调优。

需要提醒的是，稀疏求解没有"万能算法"。同一矩阵，直接法可能因填充爆炸而内存不足，迭代法可能因条件数差而不收敛。因此本课程强调根据矩阵结构、对称性、正定性、规模与精度需求做选择，而不是死记某一种方法。

稀疏矩阵存储格式：COO、CSR、CSC

存储格式决定了内存布局，也深刻影响算法选择与性能。三种最基础的格式如下：

COO（坐标格式）：用三个数组分别记录非零元的行索引、列索引和数值，长度均为 nnz。它最直观、易于从三元组列表构造，适合作为"输入格式"和格式转换的中间态；但随机访问效率低，且相同位置重复项需要合并。

CSR（压缩稀疏行）：按行组织，用 values（非零值）、col_indices（列索引）、row_ptr（长度为 n+1 的行偏移指针）三个数组表示。第 i 行的非零元位于 values[row_ptr[i] : row_ptr[i+1]]。CSR 对按行遍历极其高效，是稀疏矩阵向量乘 y = Ax 和行-oriented 迭代法（如 Gauss-Seidel）的首选。

CSC（压缩稀疏列）：与 CSR 对称，按列组织，用 col_ptr 记录每列起始位置。它适合按列访问的场景，例如 Aᵀx 的计算、列主元的稀疏 LU 分解，以及某些按列更新的迭代格式。

选择经验：若算法以"逐行累加"为主（如 SpMV、行松弛），用 CSR；若以"逐列处理"或需要转置运算为主（如列主元分解、AᵀA 相关计算），用 CSC；构造阶段用 COO 最方便，构造完成后转换为 CSR/CSC 再进入计算内核。

下面这张图概括了三种格式的组织方式及其与算法选择的对应关系：

理解格式差异后，一个常见的实践问题是：格式转换本身有成本。COO 转 CSR 需要按行排序并统计每行非零数，复杂度约为 O(nnz log nnz)（排序）或 O(nnz + n)（计数排序）。因此在大规模问题中，应尽量在构造阶段就规划好目标格式，避免在迭代循环内反复转换。此外，CSR 的 SpMV 内核虽然高效，但存在负载不均衡问题——每行非零数差异大时，多线程并行会出现"长行拖尾"。这也是后续章节讨论并行稀疏计算与格式优化（如 ELL、SELL-C-σ）的动机。

从格式到算法：一个判断起点

面对一个具体问题，可以先问三个问题：矩阵是否对称正定？规模与 nnz 是否允许直接分解的填充？是否需要多次求解同一矩阵？若对称正定且条件数可控，共轭梯度（CG）配合 CSR 是自然起点；若非对称，则考虑 GMRES 或 BiCGSTAB；若需要高精度且填充可接受，稀疏 LU/Cholesky 配合重排序更稳健。这些判断将在后续章节逐一展开，本节只需建立"格式—算法—场景"的关联意识。

常见误区：把稀疏矩阵当作稠密矩阵存储后再调用通用求解器。这在 n 稍大时会迅速耗尽内存，且计算量白白浪费在零元上。另一个误区是忽视格式与访问模式的匹配，例如用 CSC 做逐行 SpMV，性能会明显下降。

本节建立了稀疏线性系统的基本图景：它是什么、从哪里来、为什么重要，以及存储格式如何影响后续算法选择。接下来的章节将从稀疏矩阵的基本运算与 SpMV 内核开始，逐步进入直接法、迭代法与预条件的核心内容。