稀疏矩阵基本操作与特征值特征向量计算
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]] ←