A Preconditioned Parallel Method for Solving Saddle Point Problems

JIANG Xiao-lin; Lü Quan-yi; XIE Gong-nan

doi:10.3879/j.issn.1000-0887.2014.09.007

Volume 35 Issue 9

Turn off MathJax

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 2014 > 35(9): 1011-1019

JIANG Xiao-lin, Lü Quan-yi, XIE Gong-nan. A Preconditioned Parallel Method for Solving Saddle Point Problems[J]. Applied Mathematics and Mechanics, 2014, 35(9): 1011-1019. doi: 10.3879/j.issn.1000-0887.2014.09.007

Citation:

PDF( 407 KB)

A Preconditioned Parallel Method for Solving Saddle Point Problems

doi: 10.3879/j.issn.1000-0887.2014.09.007

¹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）

Received Date: 2014-04-25
Rev Recd Date: 2014-06-30
Publish Date: 2014-09-15

Abstract

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

FullText(HTML)

References(8)

References

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