Preconditioners based on trigonometric transforms

Participants

  • Kurt Otto (coordinator), Dept. of Scientific Computing, Uppsala Univ.
  • Sverker Holmgren, Dept. of Scientific Computing, Uppsala Univ.
  • Elisabeth Larsson, Dept. of Scientific Computing, Uppsala Univ.
  • Eva Mossberg, Dept. of Scientific Computing, Uppsala Univ.

Research

The state of the art for solving linear systems of equations arising from discretizations of PDEs is to employ some Krylov subspace method. In order to achieve an acceptable rate of convergence and, more importantly, a short total execution time, it is crucial to construct effective, parallelizable preconditioners.

We have designed preconditioners [1] based on the fast Fourier transform, which have been expediently used for second-order accurate discretizations of first-order systems of PDEs [4]. The solution procedures are highly parallelizable, and have already from the beginning been implemented on a variety of parallel computer architectures. Moreover, the convergence properties have been thoroughly analyzed [3,2,5]. The preconditioning technique has been generalized to several fast trigonometric transforms [6,#], which resulted in favorable convergence properties for high-order discretizations of a scalar first-order PDE [7] and for a second-order discretization of the Helmholtz equation [10]. It has also been successfully applied to discretizations of waveguide problems in underwater acoustics [11,13,14] and electromagnetics [12].

Publications

Refereed

  1. Iterative solution methods and preconditioners for block-tridiagonal systems of equations. Sverker Holmgren and Kurt Otto. In SIAM Journal on Matrix Analysis and Applications, volume 13, pp 863-886, 1992. (DOI).
  2. Semicirculant preconditioners for first-order partial differential equations. Sverker Holmgren and Kurt Otto. In SIAM Journal on Scientific Computing, volume 15, pp 385-407, 1994. (DOI).
  3. Analysis of preconditioners for hyperbolic partial differential equations. Kurt Otto. In SIAM Journal on Numerical Analysis, volume 33, pp 2131-2165, 1996. (DOI).
  4. Semicirculant solvers and boundary corrections for first-order partial differential equations. Sverker Holmgren and Kurt Otto. In SIAM Journal on Scientific Computing, volume 17, pp 613-630, 1996. (DOI).
  5. Analysis of semi-Toeplitz preconditioners for first-order PDEs. Lina Hemmingsson and Kurt Otto. In SIAM Journal on Scientific Computing, volume 17, pp 47-64, 1996. (DOI).
  6. A framework for polynomial preconditioners based on fast transforms I: Theory. Sverker Holmgren and Kurt Otto. In BIT Numerical Mathematics, volume 38, pp 544-559, 1998. (DOI).
  7. A framework for polynomial preconditioners based on fast transforms II: PDE applications. Sverker Holmgren and Kurt Otto. In BIT Numerical Mathematics, volume 38, pp 721-736, 1998. (DOI).
  8. Object-Oriented Construction of Parallel PDE Solvers. Michael Thuné, Eva Mossberg, Peter Olsson, Jarmo Rantakokko, Krister Åhlander, and Kurt Otto. In Modern Software Tools for Scientific Computing, pp 203-226, Birkhäuser, Boston, MA, 1997.
  9. Object-oriented software tools for the construction of preconditioners. Eva Mossberg, Kurt Otto, and Michael Thuné. In Scientific Programming, volume 6, pp 285-295, 1997. (External link).
  10. Iterative solution of the Helmholtz equation by a second-order method. Kurt Otto and Elisabeth Larsson. In SIAM Journal on Matrix Analysis and Applications, volume 21, pp 209-229, 1999. (DOI).
  11. Iterative solution of the Helmholtz equation by a fourth-order method. Kurt Otto. In suppl, volume 40:1 of Bollettino di Geofisica Teorica ed Applicata, pp 104-105, OGS, Trieste, Italy, 1999.
  12. A domain decomposition method for the Helmholtz equation in a multilayer domain. Elisabeth Larsson. In SIAM Journal on Scientific Computing, volume 20, pp 1713-1731, 1999. (DOI).
  13. Helmholtz and parabolic equation solutions to a benchmark problem in ocean acoustics. Elisabeth Larsson and Leif Abrahamsson. In Journal of Acoustical Society of America, volume 113, pp 2446-2454, 2003. (DOI).
  14. Parallel solution of the Helmholtz equation in a multilayer domain. Elisabeth Larsson and Sverker Holmgren. In BIT Numerical Mathematics, volume 43, pp 387-411, 2003. (DOI).

Doctoral theses