Abstract
We implement an exponential integrator for large and sparse systems of ODEs, generated by FE (Finite Element) discretization with mass-lumping of advection-diffusion equations. The relevant exponential-like matrix function is approximated by polynomial interpolation, at a sequence of real Leja points related to the spectrum of the FE matrix (ReLPM, Real Leja Points Method). Application to 2D and 3D advection-dispersion models shows speed-ups of one order of magnitude with respect to a classical variable step-size Crank-Nicolson solver.
Work supported by the research project CPDA028291 “Efficient approximation methods for nonlocal discrete transforms” of the University of Padova, and by the subproject “Approximation of matrix functions in the numerical solution of differential equations” (co-ordinator M. Vianello, University of Padova) of the MIUR PRIN 2003 project “Dynamical systems on matrix manifolds: numerical methods and applications” (co-ordinator L. Lopez, University of Bari). Thanks also to the numerical analysis group at the Dept. of Math. Methods and Models for Appl. Sciences of the University of Padova, for having provided FE matrices for our numerical tests, and for the use of their computing resources.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Hundsdorfer, W., Verwer, J.G.: Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations. Springer series in Computational Mathematics, vol. 33. Springer, Berlin (2003)
Wood, W.L.: Introduction to numerical methods for water resources. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York (1993)
Fetter, C.W.: Applied Hydrogeology. Prentice-Hall, Englewood Cliffs (2000)
Thomée, V.: Galerkin finite element methods for parabolic problems. Springer, Berlin (1997)
Schaefer, M.J.: A polynomial based iterative method for linear parabolic equations. J. Comput. Appl. Math. 29, 35–50 (1990)
Gallopoulos, E., Saad, Y.: Efficient solution of parabolic equations by Krylov subspace methods. SIAM J. Sci. Statist. Comput. 13, 1236–1264 (1992)
Hochbruck, M., Lubich, C., Selhofer, H.: Exponential integrators for large systems of differential equations. SIAM J. Sci. Comput. 19, 1552–1574 (1998)
Vanselow, R.: Error estimates of a FEM with lumping for parabolic PDEs. Computing 68, 131–141 (2002)
Caliari, M., Vianello, M., Bergamaschi, L.: Interpolating discrete advectiondiffusion propagators at Leja sequences. Preprint, to appear in J. Comput. Appl. Math. (2003)
Hochbruck, M., Lubich, C.: On Krylov subspace approximations to the matrix exponential. SIAM J. Numer. Anal. 34, 1911–1925 (1997)
Saad, Y.: Analysis of some Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 29, 209–228 (1992)
Sidje, R.B.: Expokit. A Software Package for Computing Matrix Exponentials. ACM Trans. Math. Software 24, 130–156 (1998)
Pini, G., Gambolati, G.: Arnoldi and Crank-Nicolson methods for integration in time of the transport equation. Int. J. Numer. Meth. Fluids 35, 25–38 (2001)
Moret, I., Novati, P.: RD rational approximation of the matrix exponential. Preprint, to appear in BIT (2003)
Bergamaschi, L., Vianello, M.: Efficient computation of the exponential operator for large, sparse, symmetric matrices. Numer. Linear Algebra Appl. 7, 27–45 (2000)
Bergamaschi, L., Caliari, M., Vianello, M.: Efficient approximation of the exponential operator for discrete 2D advection-diffusion problems. Numer. Linear Algebra Appl. 10, 271–289 (2003)
Moret, I., Novati, P.: The computation of functions of matrices by truncated Faber series. Numer. Funct. Anal. Optim. 22, 697–719 (2001)
Moret, I., Novati, P.: An interpolatory approximation of the matrix exponential based on Faber polynomials. J. Comput. Appl. Math. 131, 361–380 (2001)
Novati, P.: A polynomial method based on Fejér points for the computation of functions of unsymmetric matrices. Appl. Numer. Math. 44, 201–224 (2003)
Reichel, L.: Newton interpolation at Leja points. BIT 30, 332–346 (1990)
Baglama, J., Calvetti, D., Reichel, L.: Fast Leja points. Electron. Trans. Numer. Anal. 7, 124–140 (1998)
Walsh, J.L.: Interpolation and approximation by rational functions in the complex domain. Amer. Math. Soc. Colloq. Publ, vol. XX. AMS, Providence (1935)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bergamaschi, L., Caliari, M., Vianello, M. (2004). The ReLPM Exponential Integrator for FE Discretizations of Advection-Diffusion Equations. In: Bubak, M., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds) Computational Science - ICCS 2004. ICCS 2004. Lecture Notes in Computer Science, vol 3039. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25944-2_57
Download citation
DOI: https://doi.org/10.1007/978-3-540-25944-2_57
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22129-6
Online ISBN: 978-3-540-25944-2
eBook Packages: Springer Book Archive