TW 2000_3

Jef Hendrickx
Generalized S-matrices and their use by finite difference approximations for differential equations and solving symmetric band Toeplitz systems

Advisors: Hugo Van de Vel, Marc Van Barel

Abstract

When discretising the Helmholtz equation on a rectangle with Dirichlet boundary conditions by means of finite difference methods, a linear system of equations arises whose corresponding matrix can be described by means of the discrete sine transform matrix and the matricial Kronecker product. This leads to the definition of a class of matrices, called S-matrices by Mertens. For different types of differential equations or different types of boundary conditions, this class of matrices appears to be too restricted. This motivates the definition and algebraic study of generalized S-matrices in this thesis. For certain types of elliptic partial differential equations (including the Helmholtz equation) on a rectangle we obtain for different types of boundary conditions and by use of different types of grid ('traditional', 'staggered', or 'mixed') different classes of generalized S-matrices which can always be described by some discrete sine or cosine transform matrix. This is interesting for numerical purposes, since then we can use the fast Fourier transform when solving a system with such a matrix. We call the numerical method in his general form the Kronecker product method.

In literature the two most important direct methods for solving the Helmholtz equation are matrix decomposition (or Fourier analysis) and cyclic reduction. It is shown that the matrix decomposition method is a special case of the Kronecker product method. Moreover, we can combine the Kronecker product method and cyclic reduction into a new method, the KPCR-method, which is faster than the two methods used independently. This method is similar but more general than the FACR-method, which is a combination of matrix decomposition and cyclic reduction.

In some applications we must solve a system of equations where the matrix differs from a generalized S-matrix in only a few elements. In that case we can reduce the linear system into two systems with a generalized S-matrix and two smaller systems. We discuss two typical examples: the Helmholtz equation on a rectangle with Robbins boundary conditions on all sides, and, outside the domain of partial differential equations, symmetric band Toeplitz systems. In these two cases we can use displacement theory to solve the smaller systems.