计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  在线办公 | 
计算数学  2011, Vol. 33 Issue (2): 113-124    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索  |  Next Articles  
Parareal 算法的均方稳定性分析
吴树林1, 王志勇2, 黄乘明3
1. 四川理工学院理学院, 四川自贡 643000;
2. 电子科技大学应用数学学院, 成都 610054;
3. 华中科技大学数学与统计学院, 武汉 430074
ANALYSIS OF MEAN-SQUARE STABILITY OF THE PARAREAL ALGORITHM
Wu Shulin1, Wang Zhiyong2, Huang Chengming3
1. School of Science, Sichuan University of Science and Engineering, Zigong 643000, Sichuan, China;
2. School of Applied Mathematics, University of Electronic Science and Technology of China, Chengdu 610054, China;
3. School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan 430074, China
 全文: PDF (2373 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 

Parareal 算法是一种非常有效的实时并行计算方法. 与传统的并行计算方法相比,该算法的显著特点是它的时间并行性 | 先将整个计算时间划分成若干个子区间,然后在每个子区间内同时进行计算. Parareal算法收敛速度快, 并行效率高, 且易于编程实现, 从 2001 年由 Lions,Maday 和 Turinici等人首次提出至今, 在短短的几年间得到了广泛的研究和应用. 最近, Parareal 算法在随机微分方程数值解中的应用也得到了一些学者的关注. 本文中, 我们研究 Parareal算法在随机微分方程数值解中的均方稳定性, 分析保持算法稳定的充分性条件. 通过分析, 我们得到了如下结论: a)Parareal 算法在有限时间区间内是超线性收敛的; b)在无限时间区间内, 该算法是线性收敛的. 最后, 通过数值试验, 我们验证了本文中的理论结果.

服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词Parareal 算法   并行计算   稳定性   超线性收敛   线性收敛     
Abstract

Parareal algorithm is a very efficient parallel in time computation methods. Compared with traditional parallel methods, this algorithm has the advantages of faster convergence, higher parallel performance and easy coding. This algorithm was first proposed by Lions, Maday and Turinici in 2001 and has attracted many researchers over the past few years. Recently, the application and theoretical analysis of this algorithm for stochastic computation have been investigated by some researchers. In this paper, we analyze the Mean-square stability of the Parareal algorithm in stochastic computation. The sufficient conditions under which the Parareal algorithm is stable are obtained and it is shown that: a) the algorithm converges superlinearly on any bounded time interval and b) the convergence speed is only linear on unbounded time intervals. Finally, numerical results are given to validate our theoretical conclusions.

Key wordsParareal algorithm   parallel computation   stability   superlinear convergence   linear convergence   
收稿日期: 2009-06-20;
基金资助:

本工作得到四川理工学院人才引进项目资助(项目编号:2010XJKRL005)以及国家自然科学基金资助(项目编号:10971077, 60973015).

引用本文:   
. Parareal 算法的均方稳定性分析[J]. 计算数学, 2011, 33(2): 113-124.
. ANALYSIS OF MEAN-SQUARE STABILITY OF THE PARAREAL ALGORITHM[J]. Mathematica Numerica Sinica, 2011, 33(2): 113-124.
 
[1] Bal G. On the convergence and the stability of the parareal algorithm to solve partial differential equations [J]. In Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng., 2003, 40: 426-432.
[2] Bal G and Maday Y. A “parareal” time discretization for non-linear pde’s with application to the pricing of an American put. In Recent Developments in Domain Decomposition Methods[J]. Lect. Notes Comput. Sci. Eng., 2002, 23: 189-202.
[3] Bal G. Parallelization in time of (stochastic) ordinary differential equations[J]. Submitted (a PDF file is available at http://www.columbia.edu/ gb2030).
[4] Cortial J and Farhat C. A time-parallel implicit method for accelerating the solution of non-linear structural dynamics problems[J]. Internat. J. Numer. Methods Engrg., 2008, 77: 451-470.
[5] Engblom S. Parallel in time simulation of multiscale stochastic chemical kinetics[J]. 2008, to appear in the IT technical report series (a PDF file is available at http://user.it.uu.se/stefane/ssa parareal.pdf.
[6] Engblom S. Time-parallel Simulation of Stochastic Chemical Kinetics[J]. Numerical Analysis and Applied Mathematics: International Conference on Numerical Analysis and Applied Mathematics. AIP Conference Proceedings, 2008, 1048: 174-177.
[7] Farhat C and Chandesris M. Time-decomposed parallel time-integrators: Theory and feasibility studies for fluid, structure, and fluid-structure applications[J]. Internat. J. Numer. Methods Engrg., 2003, 58: 1397-1434.
[8] Farhat C, Cortial J, Dastillung C. and Bavestrello H. Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses[J]. Internat. J. Numer. Methods Engrg., 2006, 67: 697-724.
[9] Gander M J and Petcu M. Analysis of a Krylov Subspace Enhanced Parareal Algorithm[J]. ESAIM Proc., 2008, in press.
[10] Gander M J, Vandewalle S. Analysis of the parareal time-parallel time-integration method[J]. SIAM J. Sci. Comput., 2007, 29: 556-578.
[11] Higham D J. Mean-square and asymptotic stability of the stochastic theta method[J]. SIAM J. Numer. Anal., 2001, 38: 753-769.
[12] Koskodan R and Allen E. Extrapolation of the Stochastic Theta Numerical Method for Stochastic Differential Equations[J]. Stochastic Analysis and Applications, 2006, 24: 475-487.
[13] Lions J L, Maday Y and Turinici G. A “parareal” in time discretization of PDE’s[J]. C. R. Acad. Sci. Paris S′er. I Math., 2001, 332: 661-668.
[14] SubberWand Sarkar A. Performance of A Parallel Time Integrator For Noisy Nonlinear System[J]. Journal of Probabilistic Engineering Mechanics, 2008, to appear.
[15] Staff G A and R?nquist E M. Stability of the parareal algorithm[J]. In Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng., 2003, 40: 449-56.
[16] Wu S L, Shi B C and Huang C M. Parareal-Richardson Algorithm for Solving Nonlinear ODEs and PDEs[J]. Communication in Computational Physics, 2009, 6: 883-902.
[17] Wu S L, Shi B C and Huang C M. Convergence and Stability analysis of the Parareal-Richardson Algorithm[J]. Manuscript.
[1] 胡劲松, 胡兵, 徐友才. 耗散对称正则长波方程的有限差分逼近[J]. 计算数学, 2011, 33(2): 177-184.
[2] 谭英贤, 甘四清, 王小捷. 随机延迟微分方程平衡方法的均方收敛性与稳定性[J]. 计算数学, 2011, 33(1): 25-36.
[3] 苏凯, 王锦红, 张宏伟, 王晚生. 显式和对角隐式Rung-Kutta方法求解中立型泛函微分方程的非线性稳定性[J]. 计算数学, 2011, 32(1): 8-22.
[4] 陈丙振, 游雄. 求解初值问题的 RKNd 方法[J]. 计算数学, 2010, 32(4): 399-412.
[5] 张铁, 冯男, 史大涛. 求解椭圆边值问题惩罚形式的间断有限元方法[J]. 计算数学, 2010, 32(3): 275-284.
[6] 胡鹏, 黄乘明. 非线性延迟积分微分方程线性多步法的渐近稳定性[J]. 计算数学, 2010, 31(2): 116-122.
[7] 张在斌, 孙志忠. 一类非线性延迟抛物偏微分方程的Crank-Nicolson型差分格式[J]. 计算数学, 2010, 31(2): 131-140.
[8] 余越昕. 非线性中立型延迟积分微分方程一般线性方法的稳定性分析[J]. 计算数学, 2010, 32(2): 125-134.
[9] 胡鹏, 黄乘明. 线性随机延迟积分微分方程Euler-Maruyama方法的稳定性[J]. 计算数学, 2010, 32(1): 105-112.
[10] 余越昕, 文立平. 非线性中立型延迟积分微分方程线性Θ-方法的渐近稳定性[J]. 计算数学, 2009, 30(4): 241-246.
[11] 吴宏伟. 关于广义KPP方程的数值解[J]. 计算数学, 2009, 31(2): 137-150.
[12] 刘青霞, 刘发旺. 修正交替方向法求解具有分数阶导数的二维非连续渗流问题[J]. 计算数学, 2009, 31(2): 179-194.
[13] 王顺绪, 戴华. 二次特征值问题的并行Jacobi-Davidson方法及其应用[J]. 计算数学, 2008, 29(4): 313-320.
[14] 吴宏伟. 二维半线性反应扩散方程的交替方向隐格式[J]. 计算数学, 2008, 30(4): 349-360.
[15] 孙建强, 秦孟兆, 戴桂冬. 解扩散方程的指数时间差分方法[J]. 计算数学, 2008, 29(4): 261-266.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10