下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 稀疏矩阵线性方程求解-命题1

稀疏矩阵线性方程求解-命题1.doc

稀疏矩阵线性方程求解-命题1

dspduoduo
2018-09-06 0人阅读 举报 0 0 暂无简介

简介:本文档为《稀疏矩阵线性方程求解-命题1doc》,可适用于工程科技领域

稀疏矩阵线性方程求解求解线性方程是科学计算和工程应用中常见的操作该问题可以表述为Ax=b其中A为非奇异矩阵x为未知数矢量b为已知矢量求解目标在于确定x的数值。同时在实际应用中矩阵A经常是稀疏的即绝大部分矩阵元素均为。在针对该类型矩阵的计算中通常可以只存储和处理非零元素因此运算复杂度能够大幅度降低。一般来说如果非零元素个数少到可以利用这一特征来加速矩阵运算时即可将该矩阵视为稀疏矩阵。年度的CUDA编程竞赛指定题目之一就是使用GPU加速稀疏矩阵与矢量的乘积运算。考虑到稀疏矩阵的广泛应用同时相对于普通矩阵(也因此称为稠密矩阵)稀疏矩阵运算的GPU操作具有一定困难、已经成为学术界和工程界研究的热点此次CUDA编程竞赛题目之一指定为求解基于稀疏矩阵的线性方程。稀疏矩阵线性方程求解已经过多年的研究具备非常深厚的理论和工程基础主要的参考文献包括为、和。求解算法可以分为两类直接法(directmethod)和迭代法(iterativemethod)在Internet上都有开源软件包可以下载。直接法由高斯消元法发展而来对于一般矩阵可以使用LU分解即A=LU其中L为下三角矩阵(对角线以上元素为)U为上三角矩阵(对角线以下元素为)。分解之后原来的方程组可以表述为Ax=LUx=b如果引入一个新矢量y=Ux那么y的数值可以通过求解Ly=b获得。这里由于L为三角阵求解过程相对简单得多。确定y的数值后x的值可以相似方式求解y=Ux获得。对于对称正定矩阵还可以使用Cholesky分解即先把Ax=b中的矩阵A分解为下三角矩阵L及其转置LT的乘积(A=LLT)此后的求解还可以进一步简化。直接法的基本处理方法和最新结果在参考文献中有详细的介绍。目前最好的直接法软件包之一是TimothyDavis教授开发的KLU(http:wwwciseufleduresearchsparseklu)。迭代法的理论基础相对复杂并且具有多种不同的具体算法但其基本形式均为从一个猜测解出发把方程变形为x(k)=Bx(k−)c的形式(上标表示迭代次数)通过多次迭代逐渐收敛。各种迭代算法的性能瓶颈都是稀疏矩阵和向量乘积的计算。参考文献是迭代法的系统介绍包含了对理论基础和具体算法的分析。参考文献给出常用算法的模板解释简洁而清晰而且可以免费下载。IML软件包(http:mathnistgoviml)是参考文献的C实现。一般来说迭代法的求解速度高于直接法。但是如果使用直接法时LU分解过程能够被很多后续计算重复使用则后续的三角阵求解可以非常快速实现此时直接法在性能上具有优势。典型例子是模拟电路瞬态仿真这时需要多次以NewtonRaphson方法求解非线性方程每一次求解均会在工作点附近展开为线性方程而且所有线性方程的LU分解方式都是固定的因此目前求解该类问题最好的方法是直接法。稀疏矩阵的LU分解在GPU上的实现是很困难的主要难点在于现有算法的数据依赖性导致可利用的并行性不足。此外矩阵元素的排列顺序对计算过程中间结果矩阵的非零元素个数有很大影响同时L和U中非零元素的分布与原来矩阵可能很不相同。为了简化问题参赛者可以使用Matlab或者现有软件包对矩阵进行LU分解从中获取L和U中非零元素的分布然后在GPU上实现计算L和U中非零元素的具体数值以及两次三角阵求解(即Ly=b和y=Ux)。参赛选手可以自行选择一种直接法或者迭代法的算法获知一系列算法的组合在GPU上实现只要在最后的设计文档指出具体使用的算法即可。现在使用GPU实现直接法方面的工作几乎没有因此从研究角度存在着大量创新的机会。按照下表所示我们选择了五个来自实际工程应用的大型稀疏矩阵作为测试程序性能的基准请参赛选手从下表列出的地址下载。这五个矩阵均来自于TimothyDavis教授的稀疏矩阵库(http:http:wwwciseufleduresearchsparsematrices)大家也可以直接从该网站上下载更多的矩阵调试自己的程序。在最后的评阅中评委会使用这五个矩阵和其它五个不公开的矩阵进行性能评价。矩阵行数列数非零元素个数应用背景下载链接c,,,非线性优化http:wwwciseufleduresearchsparseMMSchenkIBMNActargzbcsstk,,,建筑结构刚性矩阵http:wwwciseufleduresearchsparseMMHBbcsstktargzrajat,,,电路仿真http:wwwciseufleduresearchsparseMMRajatrajattargzcrystk,,,晶体自由振动有限元分析http:wwwciseufleduresearchsparseMMBoeingcrystktargzASICks,,,,电路仿真http:wwwciseufleduresearchsparseMMSandiaASICkstargz矩阵文件以“MatrixMarket”格式(以mm为文件后缀)存储具体内容用以下例子说明。假定有矩阵内容如下:对应以上矩阵的文件内容如下:MatrixMarketmatrixcoordinaterealgeneral==================================================ThisASCIIfilerepresentsasparseMxNmatrixwithLnonzerosinthefollowingMatrixMarketformat:|MatrixMarketmatrixcoordinaterealgeneral|<headerline||<|comments||ormorecommentlines||<|MNL|<rows,columns,entries|IJA(I,J)|<|IJA(I,J)|||IJA(I,J)||Llines||||ILJLA(IL,JL)|<Indicesarebased,ieA(,)isthefirstelement====================================================eeeeeeeeMatrixMarket格式只存储非零元素以“”开始的一行上所有内容为注释可以忽略。非注释的第一行包含三个整数以空格或制表符(tab)隔开分别表示矩阵的行数、列数和非零元素个数。上面的例子中注释后第一行是“”表示这是五行五列矩阵一共包含个非零元素。接下来每一行用三个数来表示一个非零元素前两个整数表示该非零元素的行号和列号第三个浮点数表示该非零元素的数值。所有行号和列号均从开始标记(即没有第行或第列)。本例中第一个非零元素在第一行第一列其数值为e。以上是矩阵在硬盘上的存储格式参赛选手应该自行编写程序将文件读如内存并存放在自己选择的稀疏矩阵数据结构中。在参考文献中有对各种稀疏矩阵数据结构的介绍。注意我们提供的矩阵文件并未包含Ax=b的b矢量参赛选手可以首先任意选择x矢量的数值然后计算b矢量之后使用b矢量倒过来尝试求解x从而验证是否能够正确得到选定的x矢量。TimothyADavis,“DirectMethodsforSparseLinearSystems,”SIAM,ISBN:YousefSaad,“IterativeMethodsforSparseLinearSystems,”ndEdition,SIAM,ISBN:(该书第一版可以在http:wwwuserscsumnedu~saadbookshtml下载)RBarrett,MBerry,TFChan,JDemmel,JDonato,JDongarra,VEijkhout,RPozo,CRomine,andHVanderVorst,“TemplatesfortheSolutionofLinearSystems:BuildingBlocksforIterativeMethods,”ndEdition,SIAM,ISBN:(该书可以在http:netlibcsutkedulinalghtmltemplatesTemplateshtml下载)unknown

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/3

稀疏矩阵线性方程求解-命题1

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利