注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

数据挖掘

学习数据挖掘

 
 
 

日志

 
 

稀疏矩阵存储  

2014-03-29 15:29:53|  分类: Python |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://eduunix.ccut.edu.cn/index2/edu/%C7%E5%BB%AA%B4%F3%D1%A7%BC%C6%CB%E3%BB%FA%BF%CE%B3%CC/%B2%A2%D0%D0%BC%C6%CB%E3/text/ch06/se04/6_4_1_2.htm


缩行存储格式(简称CSR存储格式)也用三个一维数组来存储矩阵信息,与坐标存储格式不同的是,它在行方向进行了简单压缩,进一步缩小了存储空间。具体来说(见图6.4.2):

  √ 第一个数组V存放各个非零元素的值,并且各个元素按照行从小到大的顺序放置(这隐含了同一行的元素要放在一起),同一行的各个元素之间按照任意顺序排列。
  √ 第二个数组J存放V中各个元素的列坐标。
  √ 第三个数组I存放J(或V)中各个行第一个项目的首位置。

  因此,V和J中各有q(矩阵中非零元素的个数)个项目,而I中的项目数等于矩阵的行数。
     稀疏矩阵存储 - 小坏 - 三十而立
       图6.4.2 CSR存储格式(稀疏矩阵见图6.4.1(a))

  仍然沿用6.4.1.1小节的矩阵基本参数,得到CSR存储格式的空间占用情况:
         稀疏矩阵存储 - 小坏 - 三十而立
  对照上式与坐标存储格式的空间占用表达式,可以知道,CSR存储格式不一定比坐标存储格式节省空间,只有当行数小于矩阵中非零元素个数的时候才是这样。

  根据对称性,也有缩列存储格式(CSC:Compressed Sparse Col Format),其空间占用为:
         稀疏矩阵存储 - 小坏 - 三十而立


对于很多元素为零的稀疏矩阵,仅存储非零元素可使矩阵操作效率更高。现有许多种稀疏矩阵的存储方式,但是多数采用相同的基本技术,即存储矩阵所有的非零元素到一个线性数组中,并提供辅助数组来描述原数组中非零元素的位置。


以下是几种常见的稀疏矩阵存储格式:

1. Coordinate Format (COO)

这种存储方式的主要优点是灵活、简单。仅存储非零元素以及每个非零元素的坐标。

使用3个数组进行存储:valuesrows, andcolumn

values: 实数或复数数据,包括矩阵中的非零元素, 顺序任意。

rows: 数据所处的行。

columns: 数据所处的列.

参数:矩阵中非零元素的数量 nnz,3个数组的长度均为nnz.

2. Diagonal Storage Format (DIA)

If the sparse matrix has diagonals containing only zero elements, then the diagonal storage format can be used to reduce the amount of information needed to locate the non-zero elements. This storage format is particularly useful in many applications where the matrix arises from a finite element or finite difference discretization.

The Intel MKL diagonal storage format is specified by two arrays:values anddistance, and two parameters:ndiag, which is the number of non-empty diagonals, andlval, which is the declared leading dimension in the calling (sub)programs. 

values

A real or complex two-dimensional array is dimensioned aslval byndiag. Each column of it contains the non-zero elements of certain diagonal ofA. The key point of the storage is that each element invalues retains the row number of the original matrix. To achieve this diagonals in the lower triangular part of the matrix are padded from the top, and those in the upper triangular part are padded from the bottom. Note that the value ofdistance(i) is the number of elements to be padded for diagonali.

distance

An integer array with dimension ndiag. Elementi of the arraydistance is the distance betweeni-diagonal and the main diagonal. The distance is positive if the diagonal is above the main diagonal, and negative if the diagonal is below the main diagonal. The main diagonal has a distance equal to zero.


3. Compressed Sparse Row Format (CSR) 

The Intel MKL compressed sparse row (CSR) format is specified by four arrays: thevalues,columns,pointerB, andpointerE. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrixA.

values

A real or complex array that contains the non-zero elements ofA. Values of the non-zero elements ofA are mapped into thevalues array using the row-major storage mapping described above.

columns

Element i of the integer array columns is the number of the column inA that contains thei-th value in thevalues array.

pointerB

Element j of this integer array gives the index of the element in thevalues array that is first non-zero element in a rowj ofA. Note that this index is equal topointerB(j) -pointerB(1)+1 .

pointerE

An integer array that contains row indices, such thatpointerE(j)-pointerB(1) is the index of the element in thevalues array that is last non-zero element in a row j of A.


4. Compressed Sparse Column Format (CSC)

The compressed sparse column format (CSC) is similar to the CSR format, but the columns are used instead the rows. In other words, the CSC format is identical to the CSR format for the transposed matrix. The CSR format is specified by four arrays: valuescolumnspointerB, andpointerE. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrixA.

values

A real or complex array that contains the non-zero elements ofA. Values of the non-zero elements ofA are mapped into thevalues array using the column-major storage mapping.

rows

Element i of the integer array rows is the number of the row inA that contains thei-th value in thevalues array.

pointerB

Element j of this integer array gives the index of the element in thevalues array that is first non-zero element in a columnj ofA. Note that this index is equal topointerB(j) -pointerB(1)+1 .

pointerE

An integer array that contains column indices, such thatpointerE(j)-pointerB(1) is the index of the element in thevalues array that is last non-zero element in a column j ofA.

5. Skyline Storage Format 

The skyline storage format is important for the direct sparse solvers, and it is well suited for Cholesky or LU decomposition when no pivoting is required.

The skyline storage format accepted in Intel MKL can store only triangular matrix or triangular part of a matrix. This format is specified by two arrays:values andpointers. The following table describes these arrays:

values

A scalar array. For a lower triangular matrix it contains the set of elements from each row of the matrix starting from the first non-zero element to and including the diagonal element. For an upper triangular matrix it contains the set of elements from each column of the matrix starting with the first non-zero element down to and including the diagonal element. Encountered zero elements are included in the sets.

pointers

An integer array with dimension (m+1), where m is the number of rows for lower triangle (columns for the upper triangle).pointers(i) -pointers(1)+1 gives the index of element invalues that is first non-zero element in row (column)i. The value ofpointers(m+1) is set tonnz+pointers(1), wherennz is the number of elements in the arrayvalues.

6. Block Compressed Sparse Row Format (BSR) 

The Intel MKL block compressed sparse row (BSR) format for sparse matrices is specified by four arrays:values,columns,pointerB, andpointerE. The following table describes these arrays.

values

A real array that contains the elements of the non-zero blocks of a sparse matrix. The elements are stored block-by-block in row-major order. A non-zero block is the block that contains at least one non-zero element. All elements of non-zero blocks are stored, even if some of them is equal to zero. Within each non-zero block elements are stored in column-major order in the case of one-based indexing, and in row-major order in the case of the zero-based indexing.

columns

Element i of the integer array columns is the number of the column in the block matrix that contains thei-th non-zero block.

pointerB

Element j of this integer array gives the index of the element in thecolumns array that is first non-zero block in a rowj of the block matrix.

pointerE

Element j of this integer array gives the index of the element in thecolumns array that contains the last non-zero block in a rowj of the block matrix plus 1.

7.  ELLPACK (ELL)


8. Hybrid (HYB)   


由ELL+COO两种格式结合而成。


选择稀疏矩阵存储格式的一些经验:

1. DIA和ELL格式在进行稀疏矩阵-矢量乘积(sparse matrix-vector products)时效率最高,所以它们是应用迭代法(如共轭梯度法)解稀疏线性系统最快的格式;

2. COO和CSR格式比起DIA和ELL来,更加灵活,易于操作;

3. ELL的优点是快速,而COO优点是灵活,二者结合后的HYB格式是一种不错的稀疏矩阵表示格式;

4. 根据Nathan Bell的工作,CSR格式在存储稀疏矩阵时非零元素平均使用的字节数(Bytes per Nonzero Entry)最为稳定(float类型约为8.5,double类型约为12.5),而DIA格式存储数据的非零元素平均使用的字节数与矩阵类型有较大关系,适合于StructuredMesh结构的稀疏矩阵(float类型约为4.05,double类型约为8.10),对于Unstructured Mesh以及Random Matrix,DIA格式使用的字节数是CSR格式的十几倍;

5. 从我使用过的一些线性代数计算库来说,COO格式常用于从文件中进行稀疏矩阵的读写,如matrix market即采用COO格式,而CSR格式常用于读入数据后进行稀疏矩阵计算。


 

其他相关链接:

1. Intel MKL 库中使用的稀疏矩阵格式

http://software.intel.com/sites/products/documentation/hpc/mkl/mklman/GUID-9FCEB1C4-670D-4738-81D2-F378013412B0.htm

2. Sparse Matrix Representations & Iterative Solvers, Lesson 1 by Nathan Bell
http://www.bu.edu/pasi/files/2011/01/NathanBell1-10-1000.pdf

来自:http://blog.csdn.net/anshan1984/article/details/8580952


1. sparse模块的官方document地址:http://docs.scipy.org/doc/scipy/reference/sparse.html

2. sparse matrix的存储形式有很多种,见此帖子http://blog.csdn.net/anshan1984/article/details/8580952
不同的存储形式在sparse模块中对应如下:
bsr_matrix(arg1[, shape, dtype, copy, blocksize]) Block Sparse Row matrix
coo_matrix(arg1[, shape, dtype, copy]) A sparse matrix in COOrdinate format.
csc_matrix(arg1[, shape, dtype, copy]) Compressed Sparse Column matrix
csr_matrix(arg1[, shape, dtype, copy]) Compressed Sparse Row matrix
dia_matrix(arg1[, shape, dtype, copy]) Sparse matrix with DIAgonal storage
dok_matrix(arg1[, shape, dtype, copy]) Dictionary Of Keys based sparse matrix.
lil_matrix(arg1[, shape, dtype, copy]) Row-based linked list sparse matrix

3. 要将普通的非稀疏矩阵变为相应存储形式的稀疏矩阵只要如下:(以coo_matrix为例)
A = coo_matrix([[1,2],[3,4]])
或者按照相应存储形式的要求,喂给参数,构建矩阵,以coo为例:
>>> row  = np.array([0,0,1,3,1,0,0])
>>> col  = np.array([0,2,1,3,1,0,0])
>>> data = np.array([1,1,1,1,1,1,1])
>>> coo_matrix((data, (row,col)), shape=(4,4)).todense()
matrix([[3, 0, 1, 0],
        [0, 2, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 1]])
4. hstack和vstack函数可以将稀疏矩阵横向或者纵向合并,比如:
>>> from scipy.sparse import coo_matrix, vstack
>>> A = coo_matrix([[1,2],[3,4]])
>>> B = coo_matrix([[5,6]])
>>> vstack( [A,B] ).todense()
matrix([[1, 2],
        [3, 4],
        [5, 6]])
但是经过测试,如果A和B的数据形式不一样,不能合并。比如A存储的是字符串,B是数字,那么不能合并。也就是说一个矩阵中的数据格式必须是相同的。

5. diags函数可以建立稀疏的对角矩阵

6. 对于大多数(似乎只处了coo之外)稀疏矩阵的存储格式,都可以进行slice操作,比如对于csc,csr。也可以进行arithmetic operations,矩阵的加减乘除,速度很快。
取矩阵的指定列数,比如取矩阵的第1,3,8列:matrix[:,[0,2,7]]

7.sparce矩阵的读取。可以像常规矩阵一样通过下标读取。也可以通过getrow(i),gecol(i)读取特定的列或者特定的行,以及nonzero()读取非零元素的位置。
  评论这张
 
阅读(473)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017