A Modified Discrete-Time Jacobi Waveform Relaxation Iteration

Yong Liu, Shulin Wu

.

DOI: 10.4236/am.2011.24064                

Abstract

In this paper, we investigate an accelerated version of the discrete-time Jacobi waveform relaxation iteration method. Based on the well known Chebyshev polynomial theory, we show that significant speed up can be achieved by taking linear combinations of earlier iterates. The convergence and convergence speed of the new iterative method are presented and it is shown that the convergence speed of the new iterative method is sharper than that of the Jacobi method but blunter than that of the optimal SOR method. Moreover, at every iteration the new iterative method needs almost equal computation work and memory storage with the Jacobi method, and more important it can completely exploit the particular advantages of the Jacobi method in the sense of parallelism. We validate our theoretical conclusions with numerical experiments.

Keywords

Discrete-Time Waveform Relaxation, Convergence, Parallel Computation, Chebyshev Polynomial, Jacobi Iteration, Optimal SOR

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	C. Lubich and A. Ostermann, “Multi-grid Dynamic Itera?tion for Parabolic Equations,” BIT Numerical Mathematics, Vol. 27, No. 2, 1987, pp. 216-234. doi:10.1007/BF01934186
[2]	E. Lelarasmee, A. E. Ruehli and A. L. Sangiovanni-Vincentelli, “The Waveform Relaxation Methods for Time-do?main Analysis of Large Scale Integrated Circuits,” IEEE Transactions on Computer-Aided Design of Inte?grated Circuits and Systems, Vol. 1, No. 3, 1982, pp. 131-145. doi:10.1109/TCAD.1982.1270004
[3]	U. Miekkala and O. Nevanlinna, “Convergence of Dy-namic Iteration Methods for Initial Value Problems,” SIAM Journal on Scientific and Statistical Computing, Vol. 8, No. 4, 1987, pp. 459-482. doi:10.1137/0908046
[4]	U. Miekkala and O. Nevanlinna, “Sets of Convergence and Stability Regions,” BIT Numerical Mathematics, Vol. 27, No.4, 1987, pp. 554-584. doi:10.1007/BF01937277
[5]	U. Miekkala, “Dynamic Iteration Methods Applied to linear DAE Systems,” Journal of Computational and Ap?plied Mathematics, Vol. 25, No. 2, 1989, pp. 133-151. doi:10.1016/0377-0427(89)90044-7
[6]	O. Nevanlinna, “Remarks on Picard-Lindel?f Iteration, Part I,” BIT Numerical Mathematic, Vol. 29, No. 2, 1989, pp. 328-346.
[7]	O. Nevanlinna, “Remarks on Picard-Lindel?f Iteration, Part II,” BIT Numerical Mathematic, Vol. 29, No. 3, 1989, pp. 535-562. doi:10.1007/BF02219239
[8]	O. Nevanlinna, “Linear Acceleration of Picard-Lindel?f Iteration,” Numerische Mathematik, Vol. 57, No. 1, 1990, pp. 147-156. doi:10.1007/BF01386404
[9]	S. Vandewalle, “Parallel Multigrid Waveform Relaxation for Parablic Problems,” B. G. Teubner, Stuttgart, 1993.
[10]	J. Janssen and S. Vandewalle, “Multigrid Waveform Relaxa?tion of Spatial Finite Element Meshes: The Conti?nuous-Time Case,” SIAM Journal on Numerical Analysis, Vol. 33, No. 2, 1996, pp. 456-474. doi:10.1137/0733024
[11]	J. Y. Pan and Z. Z. Bai, “On the Convergence of Wave?form Relaxation Methods for Linear Initial Value Prob?lems,” Journal of Computational Mathematics, Vol. 22, No. 5, 2004, pp. 681-698.
[12]	J. Sand and K. Burrage, “A Jacobi Waveform Relaxation Method f or ODEs,” SIAM Journal on Scientific Computing, Vol. 20, No. 2, 1998, pp. 534-552. doi:10.1137/S1064827596306562
[13]	J. Wang and Z. Z. Bai, “Convergence Analysis of Two-stage Waveform Relaxation Method for the Initial Value Problems,” Journal of Applied Mathematics and Compu?ting, Vol. 172, No. 2, 2006, pp. 797-808. doi:10.1016/j.amc.2004.11.031
[14]	A. Bellen, Z. Jackiewicz and M. Zennaro, “Contractivity of Waveform Relaxation Runge-Kutta Iterations and Re?lated Limit Methods for Dissipative Systems in the Maxi?mum Norm,” SIAM Journal on Numerical Analysis, Vol. 31, No. 2, 1994, pp. 499-523. doi:10.1137/0731027
[15]	L. Galeone and R. Garrappa, “Convergence Analysis of Time-Point Relaxation Iterates for Linear Systems of Diffe?rential Equations,” Journal of Computational and Ap?plied Mathematics, Vol. 80, No. 2, 1997, pp. 183-195. doi:10.1016/S0377-0427(97)00004-6
[16]	R. Garrappa, “An Analysis of Convergence for Two-stage Waveform Relaxation Methods,” Journal of Computa?tional and Applied Mathematics, Vol. 169, No. 2, 2004, pp. 377-392. doi:10.1016/j.cam.2003.12.031
[17]	J. Janssen and S. Vandewalle, “Multigrid Waveform Relaxa?tion on Spatial Finite Element Meshes: The Dis?crete-Time Case,” SIAM Journal on Scientific Computing, Vol. 17, No. 1, 1996, pp. 133-155. doi:10.1137/0917011
[18]	K. Burrage, Z. Jackiewicz and B. Welfert, “Block-Toeplitz Preconditioning for Static and Dynamic Linear Sys?tems,” Linear Algebra and its Applications, Vol. 279, No. 1-3, 1998, pp. 51-74. doi:10.1016/S0024-3795(98)00007-X
[19]	J. M. Bahi, K. Rhofir and J. C. Miellou, “Parallel Solu?tion of Linear DAEs by Multisplitting Waveform Relaxa?tion Methods,” Linear Algebra and Its Applications, Vol. 332-334, 2001, pp. 181-196. doi:10.1016/S0024-3795(00)00199-3
[20]	C. W. Gear, “Massive Parallelism Across Space in ODEs,” Applied Numerical Mathematics, Vol. 11, No. 1-3, 1993, pp. 27-43. doi:10.1016/0168-9274(93)90038-S
[21]	R. S. Varga, “Matrix Iterative Analysis,” Springer Verlag, Berlin, New York, 2000. doi:10.1007/978-3-642-05156-2
[22]	Z. Z. Bai, “Parallel Matrix Multisplitting Block Relaxa?tion Iteration Methods,” Mathematica Numerica Sinica, Vol. 17, No. 3, 1995, pp. 238-252.
[23]	D. W. Young, “Iterative Solution of Large Linear Sys- tems,” Academic Press, New York, 1971.
[24]	J. C. Mason and D. C. Handscomb, “Chebyshev Polynomials,” Chapman & Hall/CRC, Florida, 2003.
[25]	J. Janssen and S. Vandewalle, “On SOR Waveform Relaxation Methods,” SIAM Journal on Numerical Analy?sis, Vol. 34, No. 6, 1997, pp. 2456-2481. doi:10.1137/S0036142995294292