Quadtree-based Grids and Multigrid Methods

Csaba Gaspar Szechenyi Istvan College, Dept. of Mathematics P.O.Box 701, H-9007 Györ, Hungary

Abstract

When discretizing a partial differential equation describing some physical phenomenon, one has always to face a dilemma arising between the spatial resolution of the discretisation and the speed of the model. In order to have a sufficiently exact solution, the spatial discretisation has to be sufficiently fine in general. On the other hand, this introduces more and more unknown parameters, which makes the model slower, and also increases the memory requirements. The nature of a lot of problems, however, requires high spatial resolution only on a more or less small part of the domain considered: on other parts of the domain the resolution may remain coarser. For instance, there is often a need for fine discretisation in the vicinity of the boundary only, while in the middle of the domain, coarser discretisation is allowed.

To overcome this difficulty, a number of methods have been constructed such as the classical finite element method (which requires, however, a mesh generation procedure as an extra task); the use of curvilinear coordinates (which transforms the original problem to another one that may, however, be more complicated) or the boundary integral equation method (which reduces the spatial dimension of the problem but makes the discretised problem more inconvenient from numerical point of view).

We present another approach which seems to be a good compromise in a certain sense. This method uses a classical finite difference (or finite volume) approach, but is based on a non-equidistant, non-uniform cell system as a computational grid. The cell system is generated by the so-called quadtree algorithm, which is a systematic, recursively defined subdivision on an initial square controlled by a finite set of points. The algorithm results in a rectangular cell system with variable cell size, so that the spatial resolution of the resulting grid follows the spatial density distribution of the controlling points. Thus, the structure of the grid can be easily controlled, and the grid can be made fine only on the parts of great interest e.g. along the boundary (in this case the method can be considered as a special boundary-type method). The computational cost of the grid generation is remarkably low: at the same time, the grid remains rectangular, which makes the discrete schemes simple. We present also several possible constructions of schemes. Furthermore we show that a multigrid technique can be constructed which fits the quadtree context in a natural way. The method has been succesfully applied to various flow problems. It is also shown that the presented approach (i.e. quadtree+multigrid) seems to be surprisingly general in the sense that it can be applied to a wide range of different problems.