A Preconditioned Parallel Method for Solving Saddle Point Problems
-
摘要: 研究了一种求解鞍点问题的并行预处理变形共轭梯度算法.通过应用迭代法进行预处理后,再采用变形共轭梯度求解的模式.首先构造系数矩阵近似逆的多项式表达式,以此作为预处理矩阵的逆矩阵,对方程组进行预处理;然后采用变形共轭梯度法并行求解预处理后的线性方程组.为减少运算量,采用迭代方式并行计算多项式与向量的乘法运算.通过调整迭代次数,即调整多项式次数,检验各种次数的多项式进行预处理后的求解方程的效果.数值试验结果表明,该算法明显优于未预处理的变形共轭梯度法,且当预处理迭代次数取4时效果最好.Abstract: A parallel algorithm with preconditioned modified conjugate gradient method for solving saddle point problems was studied. It is a model that by using iterative method for preconditioning and applying modified conjugate gradient method for solving the problems. Firstly the approximate inverse of the coefficient matrix’s polynomial expressions is constructed and become the inverse matrix of the preconditioned matrix, secondly the modified conjugate gradient method is used for parallel solving the preconditioned linear equations. In order to reduce the amount of calculation, we have to parallel compute the polynomials and vector multiplication by using iterative method. By adjusting the number of iterations and polynomials to exam the effect of preconditioning. The results show that our algorithm is superior to the modified conjugate gradient method and it has the best effect when the number of iterations is four.
-
[1] Elman H C, Golub G H. Inexact and preconditioned Uzawa algorithm for saddle point problems[J].SIAM Journal on Numerical Analysis,1994,31(6): 1645-1661. [2] Benzi M, Gander M J, Golub G H. Optimization of the Hermitian and skew-Hermitian splitting iteration for saddle-point problems[J].BIT Numerical Mathematics,2003,43(5): 881-900. [3] 李晓梅, 吴建平. 数值并行算法与软件[M]. 北京: 科学出版社, 2007.(LI Xiao-mei, WU Jian-ping.Numerical Parallel Algorithm and Software[M]. Beijing: Science Press, 2007.(in Chinese)) [4] 张凯院, 徐仲. 数值代数[M]. 第二版修订本. 北京: 科学出版社, 2010.(ZHANG Kai-yuan, XU Zhong.Numerical Algebra[M]. revised 2nd ed. Beijing: Science Press, 2010.(in Chinese)) [5] 胡家赣. 解线性代数方程组的迭代解法[M]. 北京: 科学出版社, 1999: 173-201.(HU Jia-gan.Iterative Solution of Linear Algebraic Equations[M]. Beijing: Science Press, 1999: 173-201.(in Chinese)) [6] 陈国良, 安虹, 陈俊, 郑启龙, 单九龙. 并行算法实践[M]. 北京: 高等教育出版社, 2004.(CHEN Guo-liang, AN Hong, CHEN Jun, ZHENG Qi-long, SHAN Jiu-long.The Parallel Algorithm[M]. Beijing: Higher Education Press, 2004.(in Chinese)) [7] 侯俊霞, 吕全义, 曹方颖 , 谢公南. 一种求解大型Lyapunov矩阵方程的预处理并行算法[J]. 应用数学和力学, 2013,34(5): 454-461.(HOU Jun-xia, L Quan-yi, CAO Fang-ying, XIE Gong-nan. A preconditioned parallel method for solving large Lyapunov matrix equation[J].Applied Mathematics and Mechanics,2013,34(5): 454-461.(in Chinese)) [8] BAI Zhong-Zhi, Golub G H, PAN Jian-yu. Preconditioned Hermitian and skew-Hermian splitting methods for non-Hermitian positive semidefinite linear systems[J].Numerische Mathematik,2004,98(1): 1-32.
点击查看大图
计量
- 文章访问数: 1205
- HTML全文浏览量: 115
- PDF下载量: 784
- 被引次数: 0