Fast Fourier Transform Solvers and Preconditioners for Quadratic Spline Collocation

Authors: Christara, C.C.1; Ng, K.S.2

Source: Bit Numerical Mathematics, Volume 42, Number 4, 2002 , pp. 702-739(38)

Publisher: Springer

Buy & download fulltext article:


Price: $47.00 plus tax (Refund Policy)


Quadratic Spline Collocation (QSC) methods of optimal order of convergence have been recently developed for the solution of elliptic Partial Differential Equations (PDEs). In this paper, linear solvers based on Fast Fourier Transforms (FFT)are developed for the solution of the QSC equations. The complexity of the FFT solvers is O(N2 log N), where N is the gridsize in one dimension. These direct solvers can handle PDEs with coefficients in one variable or constant, and Dirichlet, Neumann, alternating Dirichlet-Neumann or periodic boundary conditions, along at least one direction of a rectangular domain. General variable coefficient PDEs are handled by preconditioned iterative solvers. The preconditioner is the QSC matrix arising from a constant coefficient PDE. The convergence analysis of the preconditioner is presented. It is shown that, under certain conditions, the convergence rate is independent of the gridsize. The preconditioner is solved by FFT techniques, and integrated with one-step or acceleration methods, giving rise to asymptotically almost optimal linear solvers, with complexity O(N2 log N). Numerical experiments verify the effectiveness of the solvers and preconditioners, even on problems more general than the analysis assumes. The development and analysis of FFT solvers and preconditioners is extended to QSC equations corresponding to systems of elliptic PDEs.

Keywords: Spline collocation; eigenvalue problem; elliptic boundary value problem; fast Fourier transform; iterative solver; scaled Laplace preconditioner; system of PDEs

Document Type: Research Article

Affiliations: 1: Department of Computer Science, University of Toronto, Toronto, Ontario M5S 3G4, Canada. email: 2: Department of Computer Science, University of Toronto, Toronto, Ontario M5S 3G4, Canada. email:

Publication date: January 1, 2002

Related content


Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page