Electronic Joint Business

Solution for E-Business

sparse matrix

稀疏矩阵的存储格式

稀疏矩阵是指矩阵中的元素大部分是零的矩阵。现实问题中的大规模矩阵基本上都是稀疏矩阵,甚至有很多矩阵的稀疏度在 90% 甚至 99% 以上。而稀疏矩阵向量乘 (SpMV Sparse matrix-vector multiplication) 是线性迭代解法器常用的计算内核之一。而稀疏矩阵非零元的存储格式决定了 SpMV 实现时内存访问的效率。本文对几种经典的格式进行了总结和说明。

1. COO 格式(Coordinate Format)
COO 是最简单的存储格式。它采用三个数组 row、col 和 values 保存非零元素的信息。其中 values 保存元素的, 而元素的行坐标和列坐标,则依次分别保存在 row 和 col 中。一般来说,COO 主要用来创建矩阵,因为无法对矩阵的元素进行增删改等操作,一旦矩阵创建成功以后,会转化为其他形式的矩阵。

图1-1 中的矩阵用 COO 格式表示如下

import scipy.sparse as sp
row = [0,0,1,1,2,2,2,3,3]
col = [0,1,1,2,0,2,3,1,3]
values = [1,7,2,8,5,3,9,6,4]
print(sp.coo_matrix((values,(row,col)),shape=(4,4)).toarray())

用 coo_matrix 创建矩阵的时候,相同的行列坐标可以重复出现。当矩阵创建完成后,这些重复坐标的值会被相加。

2. LiL 格式 (List Of Lists)
LiL 格式用两个列表存储每一行的非零元素。一个列表保存每行中的非零元素的值, 另一个列表保存非零元素所在的列坐标。这些列表又作为 values 和 rows 这两个列表的元素来存储。

>>> 阅读全文