解线性互补问题的并行交替迭代算法

doi:10.12288/szjs.2011.3.183

数值计算与计算机应用 ›› 2011, Vol. 32 ›› Issue (3): 183-195.DOI: 10.12288/szjs.2011.3.183

解线性互补问题的并行交替迭代算法

段班祥¹, 朱小平¹, 张爱萍²

1. 广东科学技术职业学院计算机工程技术学院, 广东珠海 519090;
2. 合肥工业大学理学院, 合肥 230009

收稿日期:2010-05-25 出版日期:2011-09-15 发布日期:2011-09-03
基金资助:
广东省自然科学基金资助项目(8151064007000004).

PDF ( 307 ) 引用被引次数 ( 4 )

段班祥, 朱小平, 张爱萍. 解线性互补问题的并行交替迭代算法[J]. 数值计算与计算机应用, 2011, 32(3): 183-195.

Duan Banxiang, Zhu Xiaoping, Zhang Aiping. PARALLEL ALTERNATING ITERATIVE ALGORITHM FOR LINEAR COMPLEMENTARITY PROBLEM[J]. Journal of Numerical Methods and Computer Applications, 2011, 32(3): 183-195.

PARALLEL ALTERNATING ITERATIVE ALGORITHM FOR LINEAR COMPLEMENTARITY PROBLEM

Duan Banxiang¹, Zhu Xiaoping¹, Zhang Aiping²

1. College of Computer Engineering and Technology, Guangdong Vocational Institute of Science and Technology, Zhuhai 519090, Guangdong, China;
2. School of Sciences, Heifei University of Technology, Hefei 230009, China

Received:2010-05-25 Online:2011-09-15 Published:2011-09-03

运用交替迭代算法与并行计算, 提出了求解线性互补问题的并行交替迭代算法.当矩阵的多重分裂分别为第一类弱正则多重分裂、第二类弱正则多重分裂以及P-正则多重分裂时证明了算法的全局收敛性.该算法具有计算量小、计算速度快、并行计算等特点,因而特别适于求解大规模问题.数值结果表明, 该算法是十分有效的.

关键词： 线性互补问题, 交替迭代, 多重分裂, 并行计算

By combining Alternating Iterative Algorithm and Parallel Multi-splitting, the authors first set up Parallel Alternating Iterative Algorithm for solving the linear complementarity problem. It is shown that when the multisplittings of matrix are weak nonnegative of the first type or the second type, both models lead to convergent schemes. And then, when the multisplittings are P-regular, they establish the global convergence theory of the algorithm. The algorithm has less computational complexity and quicker velocity and is especially suitable for parallel computation of large-scale problem. The numerical experiments show the efficiency of the algorithm.

Key words: linear complementarity problem, alternating iterative: multi-splitting, parallel computation

MR(2010)主题分类:

90C33

分享此文:

[1] O'Leary D P and White R E. Multi-splittings of matrix and parallel solution of linear systems[J]. SIAM J. Algebraic Discrete Methods, 1985, 6: 630-640.

[2] Frommer A and Mayer G. Convergence of Relaxed Parallel Multisplitting Methods[J]. Linear Algebra and Its Applications, 1989, 119: 141-152.

[3] Wang D. On the convergence of the parallel multisplitting AOR algorithm[J]. Linear Algebra and Its Applications, 1991, 154/156: 473-486.

[4] Nabben R. A note on comparison theorems for splittings and multisplittings of Hermitian positive definitematrices[J]. Linear Algebra and Its Applications, 1996, 233: 67-80.

[5] Elsner L. Comparisons of weak regular splittings and multisplitting methods[J]. Numerische Mathematik, 1989, 56: 283-289.

[6] Climent J J, Perea C, Tortosa L. Convergence theorems for parallel alternating iterative methods[J]. Applied Mathematics and Computation, 2004, 148: 497-517.

[7] 陈景良, 陈向晖. 特殊矩阵[M]. 北京: 清华大学出版社, 2001.

[8] Frommer A and Szyld D B. H-splittings and two stage iterative methods[J]. Numer Math, 1992, 63: 345-356.

[9] Bai Z Z and Huang T Z. Accelerated overrelaxation methods for solving linear complementarity problem[J]. J.UEST China, 1994, 23: 428-432.

[10] Woznicki Z I. Nonnegative splitting theory[J]. Japan Journal on Industrial and Applied Mathematics, 1994, 11: 289-342.

[11] Cottle R W , Pang J S and Stone R E. The Linear Complementarity Problem[M]. Academic Press, San Diedo, 1992.

[12] Frommer A, Szyld D B. Weighted max norms, splittings, and overlapping additive Schwarz iterations[J]. Numerische Mathematik, 1999, 49: 259-278.

[1]	杜玉龙, 徐凯文, 赵昆磊, 袁礼. 基于PHG平台的非结构四面体网格欧拉方程间断有限元并行求解器[J]. 数值计算与计算机应用, 2021, 42(2): 155-168.
[2]	邓维山, 徐进. 一种泊松-玻尔兹曼方程稳定算法的高效有限元并行实现[J]. 数值计算与计算机应用, 2018, 39(2): 91-110.
[3]	吴长茂, 杨超, 尹亮, 刘芳芳, 孙乔, 李力刚. 基于CPU-MIC异构众核环境的行星流体动力学数值模拟[J]. 数值计算与计算机应用, 2017, 38(3): 197-214.
[4]	宋梦召, 冯仰德, 聂宁明, 王武. 基于空位跃迁的KMC并行实现[J]. 数值计算与计算机应用, 2017, 38(2): 130-142.
[5]	刘辉, 冷伟, 崔涛. 并行自适应有限元计算中的负载平衡研究[J]. 数值计算与计算机应用, 2015, 36(3): 166-184.
[6]	刘辉, 崔涛, 冷伟. hp自适应有限元计算中一种新的自适应策略[J]. 数值计算与计算机应用, 2015, 36(2): 100-112.
[7]	席钧, 曹建文. 美式期权定价的分数阶偏微分方程组及其数值离散方法[J]. 数值计算与计算机应用, 2014, 35(3): 229-240.
[8]	吴立飞, 杨晓忠, 张帆. 非线性Leland方程的一种并行本性差分方法[J]. 数值计算与计算机应用, 2014, 35(1): 69-80.
[9]	王顺绪, 戴华. 二次特征值问题的并行Jacobi-Davidson方法及其应用[J]. 数值计算与计算机应用, 2008, 29(4): 313-320.
[10]	姜金荣,迟学斌,陆忠华,刘洪利. 在MM5中实现IKAWA参数自适应选择[J]. 数值计算与计算机应用, 2007, 28(3): 215-220.
[11]	李永刚,欧阳洁,肖曼玉. 基于时间分解求解时间依赖问题的并行算法研究[J]. 数值计算与计算机应用, 2007, 28(1): 27-37.
[12]	余胜生,文元桥,周敬利. 隧道算法的分布式并行计算模型[J]. 数值计算与计算机应用, 2006, 27(4): 299-306.
[13]	曹建文,刘洋,孙家昶,姚继锋,潘峰. 大规模油藏数值模拟软件并行计算技术及在Beowulf系统上的应用进展[J]. 数值计算与计算机应用, 2006, 27(2): 86-95.
[14]	吕桂霞,马富明. 二维热传导方程有限差分区域分解算法[J]. 数值计算与计算机应用, 2006, 27(2): 96-105.
[15]	盛志强,刘兴平,崔霞. 对抛物方程使用新显格式的区域分解算法[J]. 数值计算与计算机应用, 2005, 26(4): 249-261.

阅读次数

全文

摘要

解线性互补问题的并行交替迭代算法

PARALLEL ALTERNATING ITERATIVE ALGORITHM FOR LINEAR COMPLEMENTARITY PROBLEM

扫码分享