为什么间接存储零?
假设每行代表一个用户,每列代表一种可能的商品。每名用户只接触少数商品,但商品总数非常大。稠密表格要为每个用户与商品的组合分配位置,连没有发生的组合也不例外。最小二乘和许多迭代算法都需要矩阵向量乘积,因此我们希望只访问已存储的条目,而不是扫描整个表格。
本节使用压缩稀疏行(CSR)格式。稀疏描述的是矩阵及其表示方式,并不保证后续结果也稀疏。设 是 实矩阵,,。数组下标从 0 开始;区间 包含 而不包含 。先讨论精确算术,浮点累加及硬件成本需另行衡量。
三个数组及其不变量
这种表示由三个数组,以及把它们与矩阵联系起来的不变量组成。
定义 4.4.1
(CSR 表示)
一个存有 个条目的 矩阵的 CSR 表示,由长度为 的数组 value、col 和长度为 的数组 rowptr 组成,并满足以下不变量:
rowptr[0] = 0,rowptr[m] = s,指针均为非递减整数;- 对于第 行半开区间
[rowptr[i], rowptr[i+1])中的位置 ,col[k]是 中的整数,value[k]是第 行的一个贡献。
所表示的矩阵为
其中空和为零。空行的两个相邻指针相等。
这个约定允许同一行重复列下标,也允许存储显式零; 是存储条目数,不一定是数学上非零元素的个数。程序库对 CSR 规范格式的定义并不完全相同:一种常见约定要求每行列下标有序、重复项已合并,但仍可存储显式零。再删除这些零,便得到更严格的无零表示。这些约定便于比较和某些运算,但排序、合并及删除零也有构造成本。以下乘法不要求规范顺序。
常见错误
(把一行的指针区间当作闭区间)
第 行拥有从 rowptr[i] 起、但不包括 rowptr[i+1] 的位置。若 rowptr = (0, 2, 2, 4),第 行只拥有位置 和 。若循环也访问位置 rowptr[i+1],第 行就会取得属于第 行的位置 ,空的第 行也会看起来非空。正是半开约定使相邻各行恰好划分位置 。
定理 4.4.2
(用同一份存储计算正向与转置乘积)
给定有效 CSR 数组,将 和 初始化为零。遍历每行 的每个存储位置 ,向 加入 value[k] * x[col[k]],并向 加入 value[k] * y[i]。结束时 ,;重复列和空行也适用。
证明
(重新分组已存储的贡献)
固定行 ,算法所得为
第二个等号将有限和按列分组,并应用表示不变量。同理,固定列 ,分散累加得到
这正是 和 的各个坐标。空和贡献零。证明不依赖行内存储次序;不过浮点算术中改变次序可能改变舍入结果。
两个计算其实是同一个有限和,只是用两种方式分组。
证明透视
证明用到不变量的哪些部分
指针条件使各行区间恰好划分位置 ,因此每个存储贡献都恰好被访问一次,并归入正确的行;col 的范围条件则保证每次读取 、每次写入 都合法。关键一步是重新分组一个以存储位置为下标的有限和:按行分组得到 的坐标,按列分组得到转置乘积的坐标。重复的列下标无须特别处理,因为所表示矩阵的定义本来就把它们相加,而重新分组也以同样方式相加。论证利用精确加法的交换律与结合律来忽略访问次序;在浮点运算中失效的正是这一步,次序改变可能改变舍入后的和。
例题 4.4.3
(空行与两个乘积)
令
第二行对应空区间 。取 ,逐行求和得到 。取 ,把各行贡献散加到列,得到 。由于第二行为空, 的第二个坐标没有影响。可用内积检验: 与 都等于 。
概念视角结构
同一组数组按列存储了转置
把三个数组中行与列的角色互换来读:rowptr 变成列指针数组,col 变成行索引数组。它们于是构成 矩阵 的压缩稀疏列(CSC)表示,因为第 行中的位置 把 value[k] 计入 的 元。因此无须另存转置副本。正向乘积沿每个已存储的行收集,而转置乘积正是这个 CSC 矩阵逐列分散累加的自然做法,所以它的写入可能互相冲突。
存储条目与非零元素可以不同,下面的边界情形说明了这一点。
例题 4.4.4
(互相抵消的重复项)
对一个 矩阵,设 rowptr = [0, 2, 2, 3],col = [1, 1, 3],value = [2, -2, 5]。第 行拥有位置 ,两者都在列 ,故 。第 行对应空区间 。第 行拥有位置 ,故 。因此数学上只有一个非零元素,尽管存储了 个条目。乘法算法仍给出正确答案:对 ,它算出 、、。合并重复项并删除零之后,只剩一个存储条目。
实现与成本
以下函数假设数据入口已经验证 CSR 不变量。它只遍历一次存储数据,返回稠密输出向量,包括仍为零的坐标;不会暗中排序或合并重复项。在普通 Python 中,0.0 初始化使累加使用浮点运算,即使输入是整数也可能舍入;精确算术定理描述的是基础运算,并非这段代码的逐位精确保证。
def csr_products(m, n, rowptr, col, value, x, y):
forward = [0.0] * m
transpose = [0.0] * n
for i in range(m):
for k in range(rowptr[i], rowptr[i + 1]):
j = col[k]
a = value[k]
forward[i] += a * x[j]
transpose[j] += a * y[i]
return forward, transpose
命题 4.4.5
(CSR 乘积的成本)
在随机访问、单位操作成本模型下,csr_products 需要 时间,输出另需 额外空间。CSR 数组本身占 个元素。
证明
(计算循环次数)
初始化输出需要 次写入。外层循环执行 次,第 行的内层循环执行 rowptr[i+1] - rowptr[i] 次。这些次数相加后逐项相消,得到 rowptr[m] - rowptr[0] ,所以只做常数工作量的内层循环体总共执行 次。总成本为 。唯一的新存储是两个输出列表,大小分别为 和 ;CSR 数组的长度则为 、 和 。
稠密输入则需要 个元素。这里计算元素而非字节:数值和索引的位宽、内存对齐都会影响实际空间。输入向量共需 个元素;上述成本不包括构造、验证、磁盘读写、通信及设备间传输。若 接近 ,索引开销可能使 CSR 不划算。若 极大,即使遍历很少的条目,初始化稠密转置输出也可能占主要成本。
若每个工作线程负责不同输出行,按行计算正向乘积比较容易并行化。转置乘法则不同:不同的行可能写入同一列,不同步的并发更新可能丢失贡献。应使用适当的归约、原子操作或按列存储,并计入相应内存、通信和浮点次序的影响。这些都需要实际设计,不能仅由稀疏性保证。
常见错误
(像正向乘积一样并行化转置乘积)
设两行各在列 有一个存储条目,数值分别为 和 ,且 。正确坐标为 。若两个线程都先读到初值 ,各自计算后不同步地写回,一次写入可能覆盖另一次,最终只剩 或 。按行分工对正向乘积是安全的,只因为每行写入自己的输出坐标;转置乘积则需要归约或原子更新。
反例模式
稀疏输入不代表每个中间结果都稀疏
设 是一个 矩阵,第一行为 ,其余元素为零。它在 个位置中只有 个非零元素,但 有 个非零元素。因此显式构造 可能破坏存储优势。计算 时,两次稀疏乘法可以避免存储这个稠密中间矩阵;这本身并不能改善条件数,也不能证明某个求解器收敛。
这种两遍计算在小例子上很容易实行。
例题 4.4.6
(用两次稀疏遍历代替稠密中间矩阵)
在上面的矩阵中取 ,于是 rowptr = [0, 3, 3, 3]、col = [0, 1, 2]、value = [1, 1, 1],并令 。正向遍历给出 。以 作转置遍历,把 散加到每一列,得到 。直接计算, 是 全一矩阵,。两次遍历各只触及 个存储条目,从未存储 的 个元素。
练习与解答
快速检查
(对第一个例题中的矩阵,计算 时的 。)
把每行已存储的贡献相加。
解答 · 答案
三行的和分别为 、空行的 和 ,所以 。
快速检查
(写出 不含重复项、不存储零的 CSR 数组。)
逐行列出非零元素。
解答 · 答案
第 行在列 有 ,第 行在列 有 。因此 value = [7, 1]、col = [2, 0]、rowptr = [0, 1, 2];此时 ,且 rowptr[2] = s,符合要求。
快速检查
(矩阵有 行、 列和 个存储条目。行指针数组有多少项?函数的时间界计算了什么?)
利用定义中的长度和成本命题。
解答 · 答案
rowptr 有 项。时间界 计算的是初始化、行遍历和存储条目上的基本操作,并非耗时预测,也不包括构造数组的成本。