引子
在看Gurobi优化器文档时,其GRBloadmodel方法中说约束矩阵的非零值是以压缩稀疏列(Compressed Sparse Column,CSC)的方式存储的。但是并不是很清楚什么才是压缩稀疏列,于是baidu了下系数矩阵存储方式,记录如下。在下面的稀疏矩阵表示方式中,都以下面的矩阵为例子。
三元组
(row_index,col_index,value)
按行存储
[(1,1,10),(1,5,-2), //第1行
(2,1,3), (2,2,9),(2,6,3), //第2行
(3,2,7),(3,3,8),(3,4,7), //第3行
(4,1,3),(4,5,5), //第4行
(5,2,8),(5,4,9),(5,5,9), //第5行
(6,2,4),(6,5,2),(6,6,-1)] //第6行
按列存储
[(1,1,10),(2,1,3),(4,1,3), //第1列
(2,2,9),(3,2,7),(5,2,8),(6,2,4), //第2列
(3,3,8), //第3列
(3,4,7),(5,4,9), //第4列
(1,5,-2),(4,5,5),(5,5,9),(6,5,2), //第5列
(2,6,3),(6,6,-1)] //第6列
压缩稀疏行(Compressed Sparse Row)
value[]:按照行的顺序,依次为非零元素的值
col_index[]:按照列的下标计数,依次标记每个非零元素所在的列的下标
row_ptr[]:对col_index中的元素下标进行计数,row_ptr中的下标表示列数,存储的值为当前列中非零值在row_index中第一次出现的位置。
index = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14, 15,16] //数组下标
value = [10,-2, 3, 9, 3, 7, 8, 7, 3, 5, 8, 9, 9, 4, 2, -1] //按行读取时,依次出现的非零值
col_index = [1, 5, 1, 2, 6, 2, 3, 4, 1, 5, 2, 4, 5, 2, 6, 6] //按行读取时,依次出现非零值所在的列下标
row_ptr = [1, 3, 6, 9,11,14] //按行读取时,每一行中第一个出现的非零值在value数组中的下标值,可以参考三元组中按行存储。
稀疏矩阵的压缩稀疏行式存储中需要存储的为value,col_index,row_ptr三个数组。
压缩稀疏列(Compressed Sparse Column)
value[]:按照列的顺序,依次为非零元素的值
row_index[]:按照行的下标计数,依次标记每个非零元素所在的行的下标
col_ptr[]:对row_index中的元素下标进行计数,col_ptr中得下标表示列数,存储的值为当前列中非零值在row_index中第一次出现的位置。
index = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14, 15,16] //数组下标
value = [10, 3, 3, 9, 7, 8, 4, 8, 7, 9, -2, 5, 9, 2, 3, -1] //按列读取时,依次出现的非零值
row_index = [1, 2, 4, 2, 3, 5, 6, 3, 3, 5, 1, 4, 5, 6, 2, 6] //案列读取时,依次出现非零值所在的行下标
col_ptr = [1, 4, 8, 9,11,15] //按列读取时,每一列中第一个出现的非零值在value数组中的下标值,可以参考三元组中按列存储。
稀疏矩阵的压缩稀疏列式存储中需要存储的为value,row_index,col_ptr三个数组。