46、稀疏矩阵基本操作与特征值特征向量计算

稀疏矩阵基本操作与特征值特征向量计算

1. 稀疏矩阵的基本操作

1.1 ij 形式的稀疏矩阵

对于无权图的邻接矩阵，如果所有元素的值都相等，那么只需要指定行索引向量i和列索引向量j即可。若图是有向图，向量i、j（必要时还有向量s，用于存储非零元素的值）的长度等于弧的数量K；若图是无向图，邻接矩阵A是对称的，理论上只需存储下三角部分（即i > j的非零元素），但为了方便某些操作（如遍历节点的邻居），通常会存储矩阵A所有非零元素的索引，此时向量i、j的长度是边数量的两倍，即M = 2K。

使用 ij 形式进行矩阵 - 向量乘法比使用完整的邻接矩阵更高效。设x是一个N维列向量，矩阵 - 向量乘积y = Ax可以按以下算法计算：

Algorithm 9 Matrix vector multiplication (ij-form) Input: i, j, s, x Output: y = Ax 1: y ←⃗0 2: for k = 0 to M −1 do 3: y[i[k]] ←