一种求解鞍点问题的预处理并行算法

姜晓林; 吕全义; 谢公南

doi:10.3879/j.issn.1000-0887.2014.09.007

一种求解鞍点问题的预处理并行算法

doi: 10.3879/j.issn.1000-0887.2014.09.007

¹西北工业大学应用数学系, 西安 710129;²西北工业大学机电学院;工程仿真与宇航计算技术联合实验室, 西安 710072

基金项目: 陕西省自然科学基金(2009JM1008);国家自然科学基金（11202164）

详细信息

作者简介:
姜晓林(1989—)，男，山东人，硕士生(E-mail: jiangxiaolin1234@126.com)；吕全义(1963—)，女，沈阳人，副教授(通讯作者. E-mail: luquan@nwpu.edu.cn).

中图分类号: O246
计量
- 文章访问数: 1544
- HTML全文浏览量: 209
- PDF下载量: 788
- 被引次数: 0
出版历程
- 收稿日期: 2014-04-25
- 修回日期: 2014-06-30
- 刊出日期: 2014-09-15

A Preconditioned Parallel Method for Solving Saddle Point Problems

¹Department of Applied Mathematics, Northwestern Polytechnical University,Xi’an 710129, P.R.China;²Engineering Simulation and Aerospace Computing; School of Mechanical Engineering,Northwestern Polytechnical University, Xi’an 710072, P.R.China

Funds: The National Natural Science Foundation of China（11202164）

摘要

摘要: 研究了一种求解鞍点问题的并行预处理变形共轭梯度算法.通过应用迭代法进行预处理后，再采用变形共轭梯度求解的模式.首先构造系数矩阵近似逆的多项式表达式，以此作为预处理矩阵的逆矩阵，对方程组进行预处理；然后采用变形共轭梯度法并行求解预处理后的线性方程组.为减少运算量，采用迭代方式并行计算多项式与向量的乘法运算.通过调整迭代次数，即调整多项式次数，检验各种次数的多项式进行预处理后的求解方程的效果.数值试验结果表明，该算法明显优于未预处理的变形共轭梯度法，且当预处理迭代次数取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.
- saddle point problem /
- parallel algorithm /
- modified conjugate gradient method /
- precondition method

HTML全文

参考文献(8)

[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.