More Web Proxy on the site http://driver.im/

research-article

Multigrid Methods for Implicit Runge--Kutta and Boundary Value Method Discretizations of Parabolic PDEs

Authors:

Stefan VandewalleAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 27, Issue 1

Pages 67 - 92

https://doi.org/10.1137/030601144

Published: 01 January 2005 Publication History

Abstract

Advanced time discretization schemes for stiff systems of ordinary differential equations (ODEs), such as implicit Runge--Kutta and boundary value methods, have many appealing properties. However, the resulting systems of equations can be quite large and expensive to solve. Many techniques, exploiting the structure of these systems, have been developed for general ODEs. For spatial discretizations of time-dependent partial differential equations (PDEs) these techniques are in general not sufficient and also the structure arising from spatial discretization has to be taken into consideration. We show here that for time-dependent parabolic problems, this can be done by multigrid methods, as in the stationary elliptic case. The key to this approach is the use of a smoother that updates several unknowns at a spatial grid point simultaneously. The overall cost is essentially proportional to the cost of integrating a scalar ODE for each grid point. Combination of the multigrid principle with both time stepping and waveform relaxation techniques is described, together with a convergence analysis. Numerical results are presented for the isotropic heat equation and a general diffusion equation with variable coefficients.

References

[1]

Pierluigi Amodio, Francesca Mazzia, A boundary value approach to the numerical solution of initial value problems by multistep methods, J. Differ. Equations Appl., 1 (1995), 353–367

[2]

D. Bertaccini, A circulant preconditioner for the systems of LMF‐based ODE codes, SIAM J. Sci. Comput., 22 (2000), 767–786

Digital Library

[3]

Daniele Bertaccini, Michael Ng, Block

{ω}

‐circulant preconditioners for the systems of differential equations, Calcolo, 40 (2003), 71–90

[4]

L. Brugnano, D. Trigiante, Solving differential problems by multistep initial and boundary value methods, Stability and Control: Theory, Methods and Applications, Vol. 6, Gordon and Breach Science Publishers, 1998xvi+418

[5]

Kevin Burrage, Parallel and sequential methods for ordinary differential equations, Numerical Mathematics and Scientific Computation, The Clarendon Press Oxford University Press, 1995xvi+446, Oxford Science Publications

Digital Library

[6]

J. Butcher, Numerical methods for ordinary differential equations, John Wiley & Sons Ltd., 2003xiv+425

[7]

Raymond Chan, Michael Ng, Xiao‐Qing Jin, Strang‐type preconditioners for systems of LMF‐based ODE codes, IMA J. Numer. Anal., 21 (2001), 451–462

[8]

E. Hairer, S. Nørsett, G. Wanner, Solving ordinary differential equations. I, Springer Series in Computational Mathematics, Vol. 8, Springer‐Verlag, 1993xvi+528, Nonstiff problems

[9]

E. Hairer, G. Wanner, Solving ordinary differential equations. II, Springer Series in Computational Mathematics, Vol. 14, Springer‐Verlag, 1996xvi+614, Stiff and differential‐algebraic problems

[10]

G. Horton, S. Vandewalle, A space‐time multigrid method for parabolic partial differential equations, SIAM J. Sci. Comput., 16 (1995), 848–864

Digital Library

[11]

F. Iavernaro, F. Mazzia, Solving ordinary differential equations by generalized Adams methods: properties and implementation techniques, Appl. Numer. Math., 28 (1998), 107–126, Eighth Conference on the Numerical Treatment of Differential Equations (Alexisbad, 1997)

Digital Library

[12]

F. Iavernaro, F. Mazzia, Block‐boundary value methods for the solution of ordinary differential equations, SIAM J. Sci. Comput., 21 (1999), 323–339

Digital Library

[13]

F. Iavernaro, D. Trigiante, Preconditioning and conditioning of systems arising from boundary value methods, Nonlinear Dyn. Syst. Theory, 1 (2001), 59–79

[14]

Jan Janssen, Stefan Vandewalle, Multigrid waveform relaxation of spatial finite element meshes: the continuous‐time case, SIAM J. Numer. Anal., 33 (1996), 456–474

Digital Library

[15]

Jan Janssen, Stefan Vandewalle, Multigrid waveform relaxation on spatial finite element meshes: the discrete‐time case, SIAM J. Sci. Comput., 17 (1996), 133–155, Special issue on iterative methods in numerical linear algebra (Breckenridge, CO, 1994)

Digital Library

[16]

J. D. Lambert, Computational Methods in Ordinary Differential Equations, John Wiley & Sons, London, New York, Sydney, 1973.

[17]

E. Lelarasmee, A. Ruehli, and A. Sangiovanni‐Vincentelli, The waveform relaxation method for time‐domain analysis of large‐scale integrated circuits, IEEE CAD for IC Systems, 1 (1982), pp. 131–145.

[18]

Ch. Lubich, On the stability of linear multistep methods for Volterra convolution equations, IMA J. Numer. Anal., 3 (1983), 439–465

[19]

Ch. Lubich, A. Ostermann, Multigrid dynamic iteration for parabolic equations, BIT, 27 (1987), 216–234

Digital Library

[20]

Andrew Lumsdaine, Deyun Wu, Spectra and pseudospectra of waveform relaxation operators, SIAM J. Sci. Comput., 18 (1997), 286–304, Dedicated to C. William Gear on the occasion of his 60th birthday

Digital Library

[21]

Ulla Miekkala, Olavi Nevanlinna, Convergence of dynamic iteration methods for initial value problem, SIAM J. Sci. Statist. Comput., 8 (1987), 459–482

Digital Library

[22]

Ulla Miekkala, Olavi Nevanlinna, Sets of convergence and stability regions, BIT, 27 (1987), 554–584

Digital Library

[23]

C. Oosterlee, The convergence of parallel multiblock multigrid methods, Appl. Numer. Math., 19 (1995), 115–128, Massively parallel computing and applications (Amsterdam, 1993–1994)

Digital Library

[24]

C. Oosterlee, P. Wesseling, On the robustness of a multiple semi‐coarsened grid method, Z. Angew. Math. Mech., 75 (1995), 251–257

[25]

Joel Saltz, Vijay Naik, Towards developing robust algorithms for solving partial differential equations on MIMD machines, Parallel Comput., 6 (1988), 19–44

[26]

U. Trottenberg, C. Oosterlee, A. Schüller, Multigrid, Academic Press Inc., 2001xvi+631, With contributions by A. Brandt, P. Oswald and K. Stüben

[27]

Jan van Lent, Stefan Vandewalle, Multigrid waveform relaxation for anisotropic partial differential equations, Numer. Algorithms, 31 (2002), 361–380, Numerical methods for ordinary differential equations (Auckland, 2001)

[28]

Stefan Vandewalle, Parallel multigrid waveform relaxation for parabolic problems, Teubner Skripten zur Numerik. [Teubner Scripts on Numerical Mathematics], B. G. Teubner, 1993, 253–0

[29]

T. Washio, C. Oosterlee, Flexible multiple semicoarsening for three‐dimensional singularly perturbed problems, SIAM J. Sci. Comput., 19 (1998), 1646–1666

Digital Library

[30]

Pieter Wesseling, An introduction to multigrid methods, Pure and Applied Mathematics (New York), John Wiley & Sons Ltd., 1992viii+284

[31]

Jacob White, Alberto Sangiovanni‐Vincentelli, Relaxation techniques for the simulation of VLSI circuits, The Kluwer International Series in Engineering and Computer Science. VLSI, Computer Architecture and Digital Signal Processing, Kluwer Academic Publishers, 1987xii+203

Digital Library

[32]

J. White, A. Sangiovanni‐Vincentelli, F. Odeh, and A. Ruehli, Waveform relaxation: Theory and practice, Trans. Soc. for Comput. Simulation, 2 (1985), pp. 95–133.

[33]

Roman Wienands, Cornelis Oosterlee, On three‐grid Fourier analysis for multigrid, SIAM J. Sci. Comput., 23 (2001), 651–671, Copper Mountain Conference (2000)

Digital Library

[34]

Roman Wienands, Cornelis Oosterlee, Takumi Washio, Fourier analysis of

GMRES (m)

preconditioned by multigrid, SIAM J. Sci. Comput., 22 (2000), 582–603

Digital Library

[35]

David Womble, A time‐stepping algorithm for parallel computers, SIAM J. Sci. Statist. Comput., 11 (1990), 824–837

Digital Library

Cited By

Chen H(2022)A splitting preconditioner for the iterative solution of implicit Runge-Kutta and boundary value methodsBIT10.1007/s10543-014-0467-354:3(607-621)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s10543-014-0467-3
Chen HHuang Q(2020)Preconditioned iterative method for boundary value method discretizations of a parabolic optimal control problemCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-019-0353-057:1Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1007/s10092-019-0353-0
Liu WSun JWu B(2016)Galerkin-Chebyshev spectral method and block boundary value methods for two-dimensional semilinear parabolic equationsNumerical Algorithms10.1007/s11075-015-0002-x71:2(437-455)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s11075-015-0002-x
Show More Cited By

Index Terms

Multigrid Methods for Implicit Runge--Kutta and Boundary Value Method Discretizations of Parabolic PDEs
1. Applied computing
  1. Physical sciences and engineering
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Ordinary differential equations
      2. Partial differential equations
    2. Numerical analysis
      1. Numerical differentiation

Index terms have been assigned to the content through auto-classification.

Recommendations

Strong stability of singly-diagonally-implicit Runge--Kutta methods

This paper deals with the numerical solution of initial value problems, for systems of ordinary differential equations, by Runge-Kutta methods (RKMs) with special nonlinear stability properties indicated by the terms total-variation-diminishing (TVD), ...
Solving nonlocal initial-boundary value problems for linear and nonlinear parabolic and hyperbolic partial differential equations by the Adomian decomposition method

In this paper, we present a new approach to solve nonlocal initial-boundary value problems for linear and nonlinear parabolic and hyperbolic partial differential equations subject to initial and nonlocal boundary conditions of integral type. We first ...
Inexact Simplified Newton Iterations for Implicit Runge-Kutta Methods

We consider possibly stiff and implicit systems of ordinary differential equations (ODEs). The major difficulty and computational bottleneck in the implementation of fully implicit Runge--Kutta (IRK) methods resides in the numerical solution of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 27, Issue 1

2005

367 pages

ISSN:1064-8275

Issue’s Table of Contents

Copyright © 2005 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2005

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen H(2022)A splitting preconditioner for the iterative solution of implicit Runge-Kutta and boundary value methodsBIT10.1007/s10543-014-0467-354:3(607-621)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s10543-014-0467-3
Chen HHuang Q(2020)Preconditioned iterative method for boundary value method discretizations of a parabolic optimal control problemCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-019-0353-057:1Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1007/s10092-019-0353-0
Liu WSun JWu B(2016)Galerkin-Chebyshev spectral method and block boundary value methods for two-dimensional semilinear parabolic equationsNumerical Algorithms10.1007/s11075-015-0002-x71:2(437-455)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s11075-015-0002-x
(2015)High-order difference potentials methods for 1D elliptic type modelsApplied Numerical Mathematics10.1016/j.apnum.2014.02.00593:C(69-86)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.apnum.2014.02.005
Li WWu SGan S(2009)Delay-dependent stability of symmetric schemes in Boundary Value Methods for DDEsApplied Mathematics and Computation10.5555/2640103.2640521215:7(2445-2455)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.5555/2640103.2640521

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents