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 secondorder accurate discretizations of firstorder 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 highorder discretizations of a scalar firstorder PDE [7] and for a secondorder 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

Iterative solution methods and preconditioners for blocktridiagonal systems of equations. In SIAM Journal on Matrix Analysis and Applications, volume 13, pp 863886, 1992. (DOI).

Semicirculant preconditioners for firstorder partial differential equations. In SIAM Journal on Scientific Computing, volume 15, pp 385407, 1994. (DOI).

Analysis of preconditioners for hyperbolic partial differential equations. In SIAM Journal on Numerical Analysis, volume 33, pp 21312165, 1996. (DOI).

Semicirculant solvers and boundary corrections for firstorder partial differential equations. In SIAM Journal on Scientific Computing, volume 17, pp 613630, 1996. (DOI).

Analysis of semiToeplitz preconditioners for firstorder PDEs. In SIAM Journal on Scientific Computing, volume 17, pp 4764, 1996. (DOI).

A framework for polynomial preconditioners based on fast transforms I: Theory. In BIT Numerical Mathematics, volume 38, pp 544559, 1998. (DOI).

A framework for polynomial preconditioners based on fast transforms II: PDE applications. In BIT Numerical Mathematics, volume 38, pp 721736, 1998. (DOI).

ObjectOriented Construction of Parallel PDE Solvers. In Modern Software Tools for Scientific Computing, pp 203226, Birkhäuser, Boston, MA, 1997.

Objectoriented software tools for the construction of preconditioners. In Scientific Programming, volume 6, pp 285295, 1997. (External link).

Iterative solution of the Helmholtz equation by a secondorder method. In SIAM Journal on Matrix Analysis and Applications, volume 21, pp 209229, 1999. (DOI).

Iterative solution of the Helmholtz equation by a fourthorder method. In suppl, volume 40:1 of Bollettino di Geofisica Teorica ed Applicata, pp 104105, OGS, Trieste, Italy, 1999.

A domain decomposition method for the Helmholtz equation in a multilayer domain. In SIAM Journal on Scientific Computing, volume 20, pp 17131731, 1999. (DOI).

Helmholtz and parabolic equation solutions to a benchmark problem in ocean acoustics. In Journal of the Acoustical Society of America, volume 113, pp 24462454, 2003. (DOI).

Parallel solution of the Helmholtz equation in a multilayer domain. In BIT Numerical Mathematics, volume 43, pp 387411, 2003. (DOI).
Doctoral theses
 Construction and Analysis of Preconditioners for Firstorder PDE. Ph.D. thesis, Comprehensive summaries of Uppsala dissertations from the Faculty of Science nr 439, Acta Universitatis Upsaliensis, Uppsala, 1993.
 Domain Decomposition and Preconditioned Iterative Methods for the Helmholtz Equation. Ph.D. thesis, Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology nr 523, Acta Universitatis Upsaliensis, Uppsala, 2000.