分享到:
数学 最近更新
实践美学:数学教学的另一种视角
重力教学论文:八年级物理重力教学方法浅论
论文:中考物理力学有效复习策略
论文:结合中考物理试题特征浅谈力学复习策略
中学物理教学资源挖掘和利用研究的实践与探索
初中数学分层教学论文:数学课堂中实施分层教学的做法
初中物理教学资源的挖掘和利用
中学物理教学过程中激发学生的学习兴趣
中学物理教学激发和培养学习兴趣
论现代农业示范区的规范建设与综合生产能力提升
数学教学过程中要培养学生的情感态度
帮助学生获得数学活动经验浅探
学生几何直观能力的培养
数学教学中的“思”与“问
基于变频器的单相电动机调速装置
毕业论文_暖贴行业的新兴与发展
汞离子对豌豆根尖细胞染色体行为的影响
初中数学教学中如何指导学生“会学”
美国高中物理教材习题设置的启示
议物理教学中科学素质的培养
当前求解三对角线性方程组两类并行算法的特点

 一、概述
  三对角线性方程组的求解是许多科学和工程计算中最重要也是最基本的问题之一。在核物理、流体力学、油藏工程、石油地震数据处理及数值天气预报等许多领域的大规模科学工程和数值处理中都会遇到三对角系统的求解问题。很多三对角线性方程组的算法可以直接推广到求解块三对角及带状线性方程组。由于在理论和实际应用上的重要性,近20年来三对角方程组的并行算法研究十分活跃。
  大规模科学计算需要高性能的并行计算机。随着软硬件技术的发展,高性能的并行计算机日新月异。现今,SMP可构成每秒几十亿次运算的系统,PVP和COW可构成每秒几百亿次运算的系统,而MPP和DSM可构成每秒万亿次运算或更高的系统。
  高性能并行计算机只是给大型科学计算提供了计算工具。如何发挥并行计算机的潜在性能和对三对角系统进行有效求解,其关键在于抓住并行计算的特点进行并行算法的研究和程序的设计与实现。另外,对处理机个数较多的并行计算系统,在设计并行算法时必须解决算法的可扩展性,并对可扩展性进行研究和分析。
  二、问题的提出
  设三对角线性方程组为
               AX=Y                                                    (1)
      式中:A∈Rn×n非奇异,αij=0,           。X=(x1,x2,…xn)T Y=(y1,y2,…yn)T。
  此系统在许多算法中被提出,因此研究其高性能并行算法是很有理论和实际意义的。
  三、并行求解三对角系统的直接解法
  关于三对角线性方程组的直接求解已经有大量并行算法,其中Wang的分裂法是最早针对实际硬件环境,基于分治策略提出的并行算法。它不仅通信结构简单,容易推广到一般带状线性方程组的并行求解,而且为相继出现的许多其它并行算法提供了可行的局部分解策略。
  近20年来求解三对角方程组的并行算法都是基于分治策略,即通过将三对角方程组分解成P个小规模问题,求解这P个小规模问题,再将这些解结合起来得到原三对角方程组的解。一般求解三对角方程组的分治方法的计算过程可分为3个阶段:一是消去,每台处理机对子系统消元;二是求解缩减系统(需要通信);三是回代,将缩减系统的解回代到每个子系统,求出最终结果。具体可分为以下几类:
  (一)递推耦合算法(Recursive Doubling)
  由Stone于1975年提出,算法巧妙地把LU分解方法的时序性很强的递推计算转化为递推倍增并行计算。D.J.Evans对此方法做了大量研究。P.Dubois和G.Rodrigue的研究表明Stone算法是不稳定的。
  (二)循环约化方法(Cyclic Reduction)
  循环约化方法由Hockey和G.Golub在1965年提出,其基本思想是每次迭代将偶数编号方程中的奇变量消去,只剩下偶变量,问题转变成求解仅由偶变量组成的规模减半的新三对角方程组。求解该新方程组,得到所有的偶变量后,再回代求解所有的奇变量。即约化和回代过程。由于其基本的算术操作可以向量化,适合于向量机。此方法有大量学者进行研究,提出了许多改进的方法。例如,Heller针对最后几步的短向量操作提出了不完全循环约化方法;R.Reulter结合IBM3090VF向量机的特点提出了局部循环约化法;P.Amodio针对分布式系统的特点改进了循环约化方法;最近针对此方法又提出对三对角方程组进行更大约化步的交替迭代策略。
  (三)基于矩阵乘分解算法
  将系数矩阵A分解成A=FT,方程Ax=b化为Fy=b和Tx=y两个方程组的并行求解。这种算法又可以分为两类:
  1.重叠分解。如Wang的分裂法及其改进算法就属于这一类。P.Amodio在1993年对这类算法进行了很好的总结,用本地LU、本地LUD和本地循环约化法求解,并在1995年提出基于矩阵乘分解的并行QR算法。H.Michielse和A.Van der Vorst改变Wang算法的消元次序,提出了通信量减少的算法。李晓梅等将H.Michielse和A.Van der Vorst算法中的通信模式从单向串行改为双向并行,提出DPP算法,是目前最好的三对角方程组分布式算法之一。2000年骆志刚等中依据DPP算法,利用计算与通信重叠技术,减少处理机空闲时间取得了更好的并行效果。此类算法要求解P-1阶缩减系统。
  2.不重叠分解。例如Lawrie & Sameh算法、Johsoon算法、Baron算法、Chawla在1991年提出的WZ分解算法以及Mattor在1995年提出的算法都属于这一类。此类算法要求解2P-2阶缩减系统。
  (四)基于矩阵和分解算法
  将系数矩阵分解成A=Ao+△A,这类算法的共同特点是利用Sherman & Morrison公式将和的逆化为子矩阵逆的和。按矩阵分解方法,这种算法又可分为两类:
  1.重叠分解。这类算法首先由Mehrmann在1990年提出,通过选择好的分解在计算过程中保持原方程组系数矩阵的结构特性,具有好的数值稳定性,需要求解P-1阶缩减系统。

随机推荐
实践美学:数学教学的另一种视角
论初中数学教学目的中的隐性目标
感受数学美,激发学生学习数学的兴趣
“等”对“不等”的启示
浅谈中国形貌属性数学归纳法
实践多媒体应用 优化数学课教学
数学教学中的“思”与“问
数学课堂学生自主学习实践与思考
营构“双主式”数学课堂
初中数学课堂教学语言

设为首页 | 关于我们 | 广告联系 | 友情链接 | 版权申明

Copyright 2009-2014 All Right Reserved [粤ICP备05100058号-11]