Circulant preconditioning for Boundary Value Methods
by
Pierluigi Amodio
Dipartimento di Matematica, Università di Bari

Circulant matrices are very attractive because of their several properties. Among the others, we recall the chance to explicitly calculate the eigenvalues and the closure with respect to any arithmetic operation (sum, product, inverse, transpose). However, the most important property is perhaps that they are diagonalized by the Fourier matrix. This means that the solution of a linear system involving a circulant matrix is obtained by means of two Fast Fourier Transform and the solution of a diagonal system containing the eigenvalues of the matrix. For this reason circulant matrices are often used as preconditioners, especially of Toeplitz matrices.

In this research we analyze the solution of linear systems arising from the application of block Boundary Value Methods (block BVMs) to initial value ODEs. BVMs, introduced in the last few years as a generalization of linear multistep methods (LMMs), show quite interesting properties which make them an efficient alternative approach to LMMs and Runge-Kutta methods.

The matrices containing the coefficients of the BVMs differ from Toeplitz band matrices for their elements on the first and last rows. The idea is to approximate them with suitable circulant matrices. This has been realized in recent papers by considering each element of the circulant matrix as a function of the corresponding element of the matrix associated to BVMs.

Here, we start by studying the properties of a polynomial associated to any circulant matrix. Then, by modifying opportunely the roots of this polynomial, we derive circulant matrices that are always nonsingular and well conditioned and result to be good approxiamtions for the matrix of BVMs.

Date received: February 1, 2000