Uppsala University Department of Information Technology

Technical Report 2004-042

Boundary Summation Equations

Per Sundqvist

September 2004


A new solution method for systems of partial difference equations is presented. It can be seen as a discrete counterpart of boundary integral equations, but with sums instead of integrals. The number of unknowns in systems of linear difference equations with constant coefficients defined on uniform d-dimensional grids are reduced so that one dimension is eliminated.

The reduction is obtained using fundamental solutions of difference operators, yielding a reduced system that is dense. The storage of the reduced system requires O(N) memory positions, where N is the length of the original vector of unknowns. The application of the matrix utilizes fast Fourier transform as its most complex operation, and requires hence O(Nlog N) arithmetic operations.

Numerical experiments are performed, exploring the behavior of GMRES when applied to reduced systems originating from discretizations of partial differential equations. Model problems are chosen to include scalar equations as well as systems, with various boundary conditions, and on differently shaped domains. The new solution method performs well for an upwind discretization of an inviscid flow-problem.

A proof of grid independent convergence is given for a simpler iterative method applied to a specific discretization of a first order differential equation. The numerical experiments indicate that this property carries over to many other problems in the same class.

Available as PDF (479 kB, no cover)

Download BibTeX entry.

Uppsala Universitet