计算机应用 ›› 2012, Vol. 32 ›› Issue (10): 2742-2744.DOI: 10.3724/SP.J.1087.2012.02742

• 先进计算 • 上一篇    下一篇

求解三对角线性方程组的迭代对角占优算法

李太全1,肖柏勋2   

  1. 1. 长江大学 物理科学与技术学院,湖北 荆州434002
    2. 长江大学 地球物理与石油资源学院,湖北 荆州 434002
  • 收稿日期:2012-04-18 修回日期:2012-05-28 发布日期:2012-10-23 出版日期:2012-10-01
  • 通讯作者: 李太全
  • 作者简介:李太全(1961-),男,湖北松滋人, 副教授,博士,主要研究方向: 计算电磁学;肖柏勋(1956-),男,湖北新洲人,教授,博士,主要研究方向:地质雷达。
  • 基金资助:
    国家自然科学基金;湖北省教育厅重点项目

Iterated parallel diagonal dominant algorithm for tridiagonal systems

LI Tai-quan1,XIAO Bo-xun2   

  1. 1. School of Physical Science and Technology, Yangtze University, Jingzhou Hubei 434002, China
    2. School of Geophysice and Oil Resource, Yangtze University, Jingzhou Hubei 434002, China
  • Received:2012-04-18 Revised:2012-05-28 Online:2012-10-23 Published:2012-10-01
  • Contact: LI Tai-quan

摘要: 针对并行求解三对角线性方程组的对角占优(PDD)算法,在系数矩阵为弱对角占优时,近似处理引入误差较大的问题,提出了一种PDD算法的迭代方案。该方案在解的修正值计算中采用迭代方法,计算精度得到了提高;通过对算法的误差分析,导出了算法在给定误差下迭代次数的估算式;数值实验说明了算法的有效性。通过对迭代与非迭代的PDD算法的复杂性分析,迭代算法的计算复杂性增加很小,但通信复杂性随迭代次数成倍增加。

关键词: 对角占优算法, 迭代, 三对角线性方程组, 分布式存储, 并行计算

Abstract: In parallel solving weak diagonal dominant tridiagonal systems, the approximate error of the Parallel Diagonal Dominant (PDD) algorithm cannot be ignored. An iterated PDD algorithm was presented. In the algorithm, the solution of the correction value was calculated by iterative method, and the computational accuracy was obviously improved. Through error analysis on the algorithm, an estimation formula of iteration number was derived for a given error tolerance. And the numerical experiment shows the validity. Based on the complexity analysis of the iterative and non-iterative PDD algorithm, the increase of iterative algorithm computational complexity is very small, but the communication complexity increases exponentially with the iteration number.

Key words: Parallel Diagonal Dominant (PDD) algorithm, iteration, tridiagonal systems, distributed memory, parallel computing

中图分类号: