介绍稀疏向量方法的文献。

引言

1. 稀疏矩阵方法得到广泛应用，但是稀疏向量方法没有得到重视，即我们一般不会考虑向量的稀疏性。
2. 在求解方程组时，稀疏向量方法在两种情况下很实用，1）右手项是稀疏的；2）我们只需要得到解向量的一部分元素。
3. 稀疏向量算法的主要优势是求解速度更快。

稀疏分解

一般的线性方程组可以表述为 ，其中 是一个非奇异矩阵，并且可以进一步分解为

如果 是对称矩阵，那么 ；如果 是 incidence symmetric, 那么 不是 的转置，但是二者的稀疏结构相同。

稀疏向量方法适用于任何一个非奇异的矩阵 ，但是如果 满足 incidence symmetric，那么可以简化表达式。

求解过程可以分为两步，向前求解和向后求解。对于稀疏向量算法，向前求解必须按列执行，向后求解必须按行执行（见附录A）。

不同的存储格式可以用于存储 和 ，但是对于稀疏向量算法，我们需要直接获取 矩阵中的每一列的非对角的非零元素，这一般可以得到满足。

附录 A 的内容直接放在下面

附录 A - 求解过程

这里 其实还是可以分为两步， 和 ，第一步就是常规的三角方程组求解，第二步其实就是 的每个元素除以 相应位置的对角线元素。这两步在计算过程中可以合二为一。

以一个 的矩阵方程组为例，假设 分解为 ，这里 矩阵按列存储， 矩阵按行存储，因此向前求解过程按照外积方法（求出的解再除以 的对角线元素），向后求解过程按照内积方法，过程如下

稀疏向量求解

右手项 很多情况下是稀疏的，但是解向量 一般不是稀疏的。接下来我们说到的“稀疏向量”要么指的是一个稀疏向量 ，要么就是指我们感兴趣的 向量的子集，可以语境来判断是哪一种情况。

如果右手项 是稀疏的，那么向前求解时，我们只需要 的一部分列（因为采用外积方式，如果 ，那么就不需要使用 列），这称为快速向前求解 (fast forward, FF)。如果我们只需要向量 的一部分元素，那么向后求解时，我们只需要使用 的一部分行（行号对应需要向量 的这部分元素的序号，这里应该还需要这部分行中的其它非零元素的行），这称为快速向后求解 (fast back, FB)。 稀疏向量的核心原理就是有效确定 FF 和 FB 中 和 的子集。

使用 FF 相对于全向前求解 (full forward solution) 的相对优势 R 计算公式如下

FB 的 R 值类似。

分解路径

稀疏向量方法中的向前分解可以采用下面简单的算法得到

1. 将 的所有元素设为0，然后加入 中给定的非零元素（“解压”右手项）。设 k 是第一个非零元素。
2. 对 的第 k 列执行向前分解（因为 k 列之前的解均为 0）。
3. 将 k 改为此时 中下一个非零元素的位置。
4. 如果 k = N ，程序终止。不然，回到步骤2。

这个算法确保在 FF 中只执行必要的非零操作，但是它在第一步和第三步比较浪费时间。FB 也有一个类似的算法。

更加高效的算法需要用到**分解路径 (factorization paths)**的概念，以下也简称路径。稀疏向量的一个分解路径定义为 FF 中使用的 矩阵的列的有序列表，或者 FB 中 矩阵的行的列表。分解路径在 FF 中按照向前的顺序执行，在 FB 中按照向后的顺序执行。在 FF 和 FB 中可能使用相同或者不同的路径。

对于一个 singleton （只有一个非零元素的向量），可以使用下面的算法决定其路径。

1. 设 k 是路径中的第一个数字
2. 得到 矩阵的第 k 列 (或 矩阵的第 k 行 ) 非对角线上的最小的非零元素，替换 k ，并加入到路径中。
3. 如果 k = N ，退出。不然，回到步骤2 。

一个一般的稀疏向量可以视为多个 singletons 的组合，其路径也是这些 singletons 的路径的并集。

路径的性质可以通过下面一个例子来说明。下图1为 20个节点的图，图2是相应的 阵和 阵的结构。

对于这个图的一个路径表格见下表，其描述所有的 singleton 的路径，任何一个 singleton 均可以直接从这个表格追溯到，首先起始节点为 K ，然后追踪 K 的 NEXT 列，一直到 K=N。举个例子，对于 K=4 的 singleton，其路径为 {4,10,13,18,19,20} 。但是注意这个路径表格在实践中不会生成，因为相应的信息均在 或 矩阵中。

路径表格一个图像描述见下图，对于 FF 方向是从低到高，对于 FB 则是从高到低。

下面是一个对于多个非零元素的稀疏向量查找路径的算法。

1. 首先从稀疏向量中第一个非零元素开始，按照上面的方法查找其 singleton 的路径，这个路径通常都会终止于 N 。
2. 确定稀疏向量中下一个不在之前路径中的非零元素，查找其 singleton 路径直到找到某个元素已经出现在之前的路径中了。
3. 将新形成的路径片段合并到之前路径的前端。
4. 如果稀疏向量中所有非零元素均在路径中，退出。不然，回到步骤2。

举个例子，假设我们有一个在 2,6,7,12 位置上具有非零元素的稀疏向量。第一步通过节点2找到的路径为 {2,11,12,15,17,18,19,20} 。第二个找到的路径片段为 {6,16} ，第三个为 {7,14}，第四个没有任何路径片段。总的路径为 {7,14,6,16, 2,11,12,15,17,18,19,20} 。
从图像来看，这些路径组成的子图如下

在 FF 中，一个节点/未知数的求解需要知道子图中所有在其前面的节点的值。但是在交会点之前的分支可以按照任何顺序计算，也就是说 {7,14}, {6,16}, {2,11,12,15} 这三个分支可以按照任意顺序计算，然后再计算 {17,18,19,20} 。FB 类似，不过方向相反。

举个例子，在 FF 过程，对于子图中的某个节点 k ，只有在其前面的节点在计算过程中才会影响右手项 k 位置的值。比如节点 12，那么在求解节点2 和节点 11 时均会修改右手项节点 12 的值，但是求解节点 6 不会影响右手项节点 12 的值（因为在 矩阵中 (12,6) 不在第6列中）。

稀疏向量操作的初始化

我们需要避免对路径之外的位置进行归零(zeroing)，这里总共分为4种情况。其实这里只有涉及 FF 方法，才涉及到归零的操作（首先将右手项路径中或全部位置设为 0.0，然后再将右手项中的非零元素加进来）。

实验结果

1. 对于 singletons ，稀疏向量算法具有优势。
2. 随着随机选择的非零元素的增加，路径长度和计算时间随之增加，虽然增加幅度相对缓慢，但是这也说明当随机选择的非零元素越来越多时，稀疏向量算法的优势就逐渐消除。

结论

稀疏向量算法的效果取决于向量的稀疏程序，以及向量与系数矩阵的拓扑关系。

文献

1. Tinney W F, Brandwajn V, Chan S M. Sparse vector methods[J]. IEEE transactions on power apparatus and systems, 1985 (2): 295-301.