201312033443_赵美_一种血液流体力学稀疏线性系统的并行算法.doc

研 究 生 课 程 论 文 (2013 -2014学年) 一种血液流体力学稀疏线形系统的并行算法 提交日期：2014年 4月29日 研究生签名：赵美 学号 201221030320 学院 软件学院 课程编号 Q0835002 课程名称 算法设计与分析 学位类别 工程硕士 任课教师 汤德佑 教师评语： 成绩评定： 分 任课教师签名： 年 月 日 一种动脉血液流体力学稀疏线性系统的并行算法 13级软件赵美-201321033443 一 问题描述 随着现代科学技术的不断发展，对主动脉脉管疾病如动脉粥样硬化、动脉夹层等疾病的 Navier Stokes（纳维叶－斯托克斯）方程是流体力学中描述粘性牛顿流体的方程，是目前为止尚未被完全解决的方程，目前只有大约一百多个特解被解出来，是最复杂的方程之一P为静压力，Re(UL/(为雷诺数，(为计算区域。N(u)为非线性平流顶，N(u)采用他的斜对称形式： N(u)=-1/2[(u(()u+( ( (u u)] 求解不可压Navier Stokes方程的关键在于近似多个线性算子，以及求解压力泊松方程。使用计算力学领域的有限元方法，得到质量矩阵和刚度矩阵： 质量矩阵： 刚度矩阵： 通过配置节点近似计算f(x)，构造方程的右端向量fh (x),其中质量矩阵提供了计算积分所需的系数。于是，单元矩阵系统可以写为 Akk 将单位矩阵累加，即可得到整体矩阵。这样可以得到整体矩阵： Av=F 这样就把问题转化为线性系统的求解。由于在求解过程中使用了局部基函数A矩阵是一个块对角矩阵，如下图： 本文介绍一个新的解决线性系统Av=F的综合稀疏线性求解器并行域分解求解器--DDPS。DDPS与Spike相似，但是他没有系数矩阵A的带状结构的假设。对于一个一般稀疏线性系统Ax = f,我们将A分裂为P个组。A = [A1,A2, ...,Ap]T A=D+R,其中D是P阶对角方阵，包含A所有的对角元素。R=A-D.,然后对Aii进行三角分解. Aii = ?Li ?Ui., DDPS算法如下所示,我们假定AX=F已经经过METIS排序. 1-5步是预处理过程.之后我们用预条件子处理Krylov子空间.Krylov子空间方法: 1 矩阵向量乘法2内积3预条件子操作. Pz = y. 算法的实例演示 现在我们使用一个算例来演示DDPS的整个步骤: 上图是一个9*9的稀疏线性系统,可以看到他的系数矩阵A与结果矩阵b.红色的部分是从系数矩阵A中可以提取到的块对角矩阵A = [A1,A2, ...,Ap]T. 得到块对角矩阵后,可以求得块对角对角矩阵的逆矩阵.对于块对角矩阵有: 求出它的逆矩阵后,分别用逆矩阵左乘系数矩阵及结果矩阵,原线性系统变化为: 经过这样的预处理,可以发现,以上线性系统的蓝色部分变成了一个缩小了的线性系统,然后我们解这个缩小后的Reduce线性系统,就可以得到x1,x2,x5,x9的值. 到这里,稀疏线性系统被部分的转化为了稠密线性系统,效率大大提高! 得到稠密线性系统的解后,将解回带到稀疏矩阵中,求其他解. 整个过程效率大大提高. 三,并行算法设计 识别对角块。 每个对角块的大小是不一样的，为此特别设计了一个自动识别对角块的小的算法来识别矩阵中的每个对角块。 A Q B C G D E F R M U P O P V 采用向下探测的方式来确定本对角块是否向下延伸。从A-〉C计算引入C将矩阵扩大一阶得到的非零单元是否大于等于为零的单元。如C点引入非零单元B点以及一个零单元，正好相等，矩阵可以向下推进一阶。而M点引入R一个非零单元与五个零单元，不符合推进条件，则M点作为一个新块对角矩阵的第一个顶点，确定前一个矩阵大小为三阶。计算后得到如下对角分块 A Q B C G D E F R M U P O P V 2 数据的存储和传递格式 对于对角矩阵A = [A1,A2, ...,Ap]T.，由于它是密度大的矩阵，就采用A1，A2….Ap原样依次存入一维数组，并使用另外一个数组存储各个对角块的大小。如上图的存储为A={ A,0,Q,B,C,G,D,E,F,M,0,0,U,P,O,P,0,V} B={3,3}的格式。 对于稀疏系数矩阵，因为零元素占比巨大，采用压缩存储方法，存储格式为[行，列，值]，即只存储与传递每个非零元素的位置和值。 3对角块并行求逆矩阵 对对角块求逆矩阵时，采用将对角块均匀分配的并行算法。即：先统计对角块的个数