Solution of the unsymmetric structured systems of certain numerical integrators. The block circulant approach.
by
Daniele Bertaccini
University of Firenze, Dipartimento di Matematica ``Ulisse Dini'', viale Morgagni 67/A, 50134 Firenze, Italy.

The solution of the large and sparse system of equations, arising at each integration step, is one of the crucial parts in a numerical integrator based on implicit formulae.

In 1998, we have set a new family of block circulant preconditioners for those linear systems.

Here, the linear systems arising in the application of fully implicit Linear Multistep Formulae (LMFs), e.g. as Boundary Value Methods (BVMs), or that can be reduced to those with some transformation, will be considered. BVMs are a class of numerical methods based on LMFs solving initial and boundary value problems for ordinary and partial differential equations. The matrices of the linear systems of the above methods are often sparse and structured. Indeed, they have blocks which are small rank perturbations of band Toeplitz matrices.

The underlying block preconditioner is based on the circulant approximation of those (small rank perturbation of) Toeplitz matrices. To this end, we have introduced some new type of circulant approximation for Toeplitz matrices: the P-circulant matrices, or P-circulants and the MS-circulants. The T. Chan's optimal and the Strang's circulant were also considered.

In this talk, we will compare the properties and the effectiveness of several circulant approximations for the block preconditioners as above.

Date received: January 20, 2000