有限元中稀疏矩阵的存储
2008年10月
第25卷 第5期枣庄学院学报JOURNALOFZAOZHUANGUNIVERSITYOct.2008Vo.l25NO.5
有限元中稀疏矩阵的存储
纪效霞,陈柯
(河海大学结构工程系,江苏南京 210098)
[摘 要]本文主要介绍了稀疏矩阵的定义以及稀疏矩阵的存储方案.并且简要介绍了在有限元通用软件中的稀疏矩阵.
[关键词]稀疏矩阵;有限元;存储方案
[中图分类号]TP311.11[文献标识码]A[文章编号]1004-7077(2008)05-0077-031 稀疏矩阵
1.1 稀疏矩阵的定义
假设m行n列的矩阵含t个非零元素,则称
t为稀疏因子[2].D=通常认为D[0.05的矩阵为稀疏矩阵.有的矩阵非零元素占全部元素的百分比较大(例如近50%),但它们的分布很有规律,利用这一特点可以避免存放零元素或避免对这些零元素进行运算,这种矩阵仍可称为稀疏矩阵.
通常,有两类稀疏矩阵:
1)特殊矩阵
例如:三角矩阵,对角矩阵(它们的压缩存储处理相对地比较简单).
2)随机稀疏矩阵
随机矩阵中的非零元分布不规则,但无法给出确切的定义,它只是一个凭直觉来了解的概念.例如,图中的M是一个67的矩阵,42个元中只有8个非零元,称为稀疏矩阵.
0129000
000000-3000014m=[***********]-7001.2 稀疏矩阵的存储问题
若以常规方法,即以二维数组表示高阶的稀疏矩阵,则:
1)零值元素占的空间很大;
2)计算中进行了很多和零值的运算;
基于以上两点,解决问题的原则如下:
1)尽可能少存或不存零值元素;
* [收稿日期]2008-06-17
[作者简介]纪效霞(1984-),女,江苏镇江人,河海大学土木工程学院结构工程系2006级研究生,主要从事钢筋混凝土结构基
本理论与现代计算方法研究;陈柯(1983-),女,江苏淮安人,河海大学土木工程学院结构工程系2006级研究生,
主要从事细观混凝土的研究.
#77#
2)尽可能减少没有实际意义的运算;
3)运算方便;即:
能尽可能快地找到与下标值(i,j)对应的非零值元;
能尽可能快地找到同一行或同一列的非零值元.
2 稀疏矩阵的存储方案
2.1 CompressedSparseRowformat(CSR)
对于矩阵A
10020
34050
A= 60789
0010110
000012
存储为
AA:1 2 3 4 5 6 7 8 9 10 11 12
JR:1 4 1 2 4 1 3 4 5 3 4 5
JC:1 3 6 10 12 13
AA中按行顺序存储各非零元素,
JR中记录对应元素所在的列的列号,
JC中记录每行第一个元素在AA中的位置.
2.2 CompressedSparseColumnformat(CSC)
方法同1,AA中按列存储,JR记录行号,JC记录每列第一个元素在AA中的位置.
2.3 ModifiedSparseRowformat(MSR)
AA:1. 4. 7. 11. 12. * 2. 3. 5. 6. 8. 9. 10.
JA:7 8 10 13 14 14 4 1 4 1 4 5 3
假设矩阵为N阶矩阵.
AA中*号前的n个元素为矩阵的对角元,*号后为按行存储的非对角元,*号为dummy.
JA中前n个元素为相应行第一个元素在AA中的位置,而第n+1个元素则为AA中存储的非零元素个数+1.从n+2开始为AA中对应位置的元素所在的列号.
2.4 Skylineformat(profileformat)
由于skyline方式多用于有限元法等产生的非零对角元对称矩阵,在此只介绍非零对角元对称矩阵的情况.
10600
02070
A= 60389
07840
00905
AA:1 2 6 0 3 7 8 4 9 0 5
JA:1 2 5 8 1 1
AA中存储每行的从第一个非零元素开始到该行对角元素为止的所有元素,并按行顺序安装.
JA中存储每行对角元在A中的存储位置.
由于在有限元法中容易从网格数据中预先计算好每行的第一个非零元素的位置,所以几乎所有的有限元程序都用此法.
#78#
3 一些常用软件中的稀疏矩阵
以MATLAB中的稀疏矩阵为例.
在MATLAB中讲稀疏矩阵时,有两个不同的概念,一是指矩阵的0元素较多,该矩阵是一个具有稀疏特征的矩阵,二是指采用稀疏方式存储的矩阵[3].
MATLAB的矩阵有两种存储方式:完全存储方式和稀疏存储方式.
(1)完全存储方式
完全存储方式是将矩阵的全部元素按列存储.以前讲到的矩阵的存储方式都是按这个方式存储的,此存储方式对稀疏矩阵也适用.
(2)稀疏存储方式
稀疏存储方式仅存储矩阵所有的非零元素的值及其位置,即行号和列号.在MAT2LAB中,稀疏存储方式也是按列存储的.
(3)稀疏存储方式的产生
1)将完全存储方式转化为稀疏存储方式
函数A=sparse(S)将矩阵S转化为稀疏存储方式的矩阵A.当矩阵S是稀疏存储方式时,则函数调用相当于A=S.
sparse函数还有其他一些调用格式:
sparse(m,n):生成一个mn的所有元素都是0的稀疏矩阵.
sparse(u,v,S):u,v,S是3个等长的向量.S是要建立的稀疏矩阵的非0元素,u(i)、v(i)分别是S(i)的行和列下标,该函数建立一个max(u)行、max(v)列并以S为稀疏元素的稀疏矩阵.
此外,还有一些和稀疏矩阵操作有关的函数.例如:
[u,v,S]=find(A):返回矩阵A中非0元素的下标和元素.这里产生的u,v,S可作为sparse(u,v,S)的参数.
full(A):返回和稀疏存储矩阵A对应的完全存储方式矩阵.
2)产生稀疏存储矩阵
只把要建立的稀疏矩阵的非0元素及其所在行和列的位置表示出来后由MATLAB自己产生其稀疏存储,这需要使用spconvert函数.调用格式为:
B=spconvert(A).
其中A为一个m3或m4的矩阵,其每行表示一个非0元素,m是非0元素的个数,A每个元素的意义是:
(,i1) 第i个非0元素所在的行;
(,i2) 第i个非0元素所在的列;
(,i3) 第i个非0元素值的实部;
(,i4) 第i个非0元素值的虚部,若矩阵的全部元素都是实数,则无须第四列.该函数将A所描述的一个稀疏矩阵转化为一个稀疏存储矩阵.
参考文献B
[1]彭宣茂.有限元计算的前后图形处理[J].水利水电微机应用,1991(1).
[2]张德兴.有限元法新编教程[M].上海:同济大学出版社,1989:78-80.
[3]董长虹,赖志国,徐啸海.MATLAB图像处理与应用[M].北京:国防工业出版社,2004:65-68.
[4]姜弘道,陈和群.有限单元法的程序设计[M].北京:水利电力出版社,1989.
#79#