稀疏矩阵表示与运算

稠密表示为每个位置保留一个槽位，零也占位置；稀疏表示把“这个值在哪里”与“这个值是多少”一起保存。节省值槽位的同时，要付出索引和分组指针的成本。因此有效项少是机会，合适的组织方式才把机会变成实际收益。

CSR 可以理解为把每一行的有效项接成长队，再用一组边界标出每行从哪里开始。读取一行不必搜索全部条目，也不需要为它单独分配一个小对象；顺着两个行指针之间的连续区间就能完成扫描。

一份可以手算恢复的 CSR ​

取

它的一份 CSR 表示是

第零行读取位置 $0,1$ 的两项；第一行的区间是 $[2,2)$，所以为空；第二行读取位置 $2,3$。给定 $x=(1,2,3,4{)}^{\mathrm{\top }}$，逐行计算可得

CSR 的矩阵—向量乘法对每个存储项执行一次乘加，并初始化每行输出，时间为 $O(m+s)$。矩阵本身占 $O(m+s)$ 存储；输入向量长度为 $n$、输出向量长度为 $m$，须按任务另计。把复杂度只写成 $O(s)$，会漏掉大量空行及输出初始化。

重复坐标与零项 ​

组装时可能先后得到 $(0,1,3)$ 与 $(0,1,-3)$。若接口约定重复坐标相加，两项合并后数值为零；这与“只保留最后一次写入”的规则不同。合并后还可以暂时保留该零槽位，再通过显式清理删除它。

有时保留零是有意的，例如提前固定数值迭代中的存储模式，避免每轮重新分配。此时应分别报告结构条目数与实际非零数，不能用其中一个冒充另一个。丢弃一个很小但非零的项则是数值近似，需要额外的误差标准，已不只是表示转换。

网格矩阵为何只有线性多项 ​

在 $q\times q$ 内部网格上离散二维五点模板，令未知量总数 $N=q^2$，$q\ge 1$。若各中心对角项及内部水平、竖直邻接项非零，矩阵共有

个非零项。边界行少几个邻接项，因此不能无条件写成恰好 $5N$；但数量仍为 $\mathrm{\Theta }(N)$，远小于稠密矩阵的 $N^2$。固定边界值的贡献放到右端向量，不需要凭空增加内部未知量之间的连接。

稀疏输入可以产生稠密中间结果 ​

令 $u,v\in {\mathbb{R}}^n$ 全为一，$e_1$ 是第一个标准基向量。方阵 $A=u{e}_1^{\mathrm{\top }}$ 仅第一列非零，$B=e_1{v}^{\mathrm{\top }}$ 仅第一行非零，各有 $n$ 个非零项；乘积 $AB=u{v}^{\mathrm{\top }}$ 却在全部 $n^2$ 个位置非零。乘法输出规模因此不能只从输入条目数推断。

消元也会产生填充。对正定矩阵

消去第一个变量后，剩余 Schur 补为

原来两个未直接耦合的位置出现了非零交叉项。消元顺序改变这种新增连接的过程，这才是重排序影响空间和工作量的原因。

表示应服务主要操作。COO 适合累计组装，再排序合并；CSR 适合逐行遍历和乘向量；CSC 适合逐列操作及一些稀疏直接法。CSR 行内未排序时，查一个指定列号一般要扫描该行；有序时可以二分，但中间插入仍可能移动后续存储，不能同时享有固定数组的所有优势。

非零模式可以用图理路有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。表达：对称方阵中的非零非对角项给出顶点连接，重排序对应重命名变量。这个视角用于解释填充与划分；矩阵定义本身则不要求先有图，长方矩阵也可以直接使用稀疏表示。

符号 Cholesky 分解理路稀疏 Cholesky 的消元图与符号分解Symbolic Cholesky factorization从逐点邻居补团预测 Cholesky 因子位置，证明路径判据，比较两种完整消元次序，并区分结构非零和数值相消。把这一视角变成逐轮算法：消去一个顶点，将其剩余邻居补成团，并记录每列位置。消元树理路消元树与稀疏列依赖Elimination tree · Cholesky elimination tree从因子每列首个下方结构位置构造父指针，证明非零必指向祖先，并用两条独立子链解释依赖、并行与祖先判据的单向性。压缩列依赖，嵌套剖分理路嵌套剖分消元顺序Nested dissection ordering递归把二维网格分隔器排在子域之后，用完整填充账本与逐层前沿计数推导存储和算术界，并说明三维为何更昂贵。则把分隔器排在子域之后，以控制规则网格中的填充和算术量。

迭代求解器常只需要 $x\mapsto Ax$。若模板或算子结构能直接产生这一结果，还可使用不显式存矩阵的实现。比较它与 CSR 时，应同时计算生成系数、索引访问和重复迭代的成本，而不只比较文件里存了多少个数。