Methods » Iterative: Parallel numerical solution of Partial Differential Equations (PDE's)

Iterative methods are usually used to solve:

1. Problems involving nonlinear systems of equations.
2. Problems resulting from the discretization of coupled partial differential equations, and
3. Time-dependent problems involving more than one spatial variable.

The formulation and use of iterative methods require specialized knowledge and experience. Three of the main stumbling blocks to the efficient use of iterative methods are the following:

• Uncertainty as to which iterative method should be used and how to implement a given method.
• Uncertainty about how to select iteration parameters which are required by certain methods (e.g. the relaxation factor ω for the Successive Overrelaxation (SOR) method), and
• Uncertainty about when the iterative process should be terminated.

Because of the diversity of problems to be solved and because of the large number of iterative procedures available, the complete removal of these uncertainties is not possible. The choice of an effective iterative method depends heavily on the details of the problem and on the particular architecture of the computer to be used. Thus, no general rules governing the selection of the best solution method can be given.

Many physical phenomena are studied basically by simulation. This approach constructs a model which simulates the behavior of the physical phenomenon. The mathematical equations which describe the model usually consist of Partial Differential Equations. It is generally impossible to obtain closed-form analytical solutions for these equations due to the irregularity of problem domains and because coefficients are usually spatially varying. Consequently, the numerical solution of PDE's plays an important role in understanding and simulating a wide variety of physical phenomena. Although, there exist a vast amount of research activity concerned with the numerical solution of PDE's, it is still one of the most challenging areas of Scientific Computing due to the versatile and often complicated structure of PDE's and because of the large amount of variables that need to be computed for two or higher dimensional problems. The numerical solution of the PDE's involves two tasks:

1. Choosing a discretization scheme to transform the PDE of interest into a discrete problem that approximates it, and
2. Selecting a solution method for the discretized problem.

The discretization procedure uses Finite Difference (FDM) or Finite Element Methods (FEM) resulting in a large, sparse system of linear algebraic equations. For such problems the number of unknowns may vary from a few hundred to a few million, thus being the most time consuming part of the whole approach.

Systems of linear algebraic equation can be solved by direct or iterative methods [1], [2], [3], [4], [13], [14], [15], [16], [17]. For systems of moderate size, the use of direct methods is often advantageous. Iterative methods are used primarily for solving large and complex problems for which, because of storage and arithmetic requirements, it would not be feasible or it would be less efficient to solve by a direct method.

Objective

To develop software for the numerical solution of Partial Differential Equations (PDE's) for parallel machines. Currently we are interested in solving the Saddle Point Problem by using SOR-like methods. In fact, our future target will be the development of a parallel algorithm for the aforementioned problem for GPUS with CUDA.

Current Research

Since the late 40's the introduction of high speed computing machines has made the field of numerical solutions of PDE's grow very rapidly. The progress in computer technology and numerical algorithms has helped us to solve many complex PDE's; however, there are still many PDE's that cannot be adequately solved using today's most powerful computers. The examples include computational aerodynamics and hydrodynamics, weather forecasting, plasma simulation, structure analysis and turbulence modeling. How to solve them efficiently is one of the most challenging goals for the next generation of computers. In order to get high throughput performance, the algorithms and architectures of tomorrow's computer must emphasize parallelism.

Our current research interests are focused on Parallel Computational Fluid Dynamic problems. In particular, we study iterative methods for solving the Navier-Stokes and Euler equations on distributed memory MIMD machines and on GPUs. We have focused on the classical iterative methods (SOR-like) because they can be used either as smoothers in multigrid methods or as preconditioners in Krylov subspace methods.

Back to top