PSU logo

Brief Description
Over the last few decades, developing efficient iterative methods for solving discretized partial differential equations (PDEs) has been a topic of intensive research.  Though these efforts have yielded many mathematically optimal solvers, such as the multigrid method, the unfortunate reality is that multigrid methods have not been used much in practical applications. This marked gap between theory and practice is mainly due to the fragility of traditional multigrid methodology and the complexity of its implementation. This paper aims to develop theories and techniques that will narrow this gap. Specifically, its aim is to develop mathematically optimal solvers that are robust and easy to use for a variety of problems in practice.  One central mathematical technique for reaching this goal is a general framework called the Fast Auxiliary Space Preconditioning (FASP) method. FASP methodology represents a class of methods that
  1. transform a complicated system into a sequence of simpler systems by using auxiliary spaces;
  2. produces an efficient and robust preconditioner (to be used with Krylov space methods such as CG and GMRes) in terms of efficient solvers for these simpler systems.
By carefully making use of the special features of each problem, the FASP method can be efficiently applied to a large class of commonly used partial differential equations including equations of Poisson, diffusion-convection-reaction, linear elasticity, Stokes, Brinkman, Navier–Stokes, complex fluids models, and magnetohydrodynamics.

Fast Poisson Solver: Algebraic Multigrid (AMG) Method
It is not difficult to notice the importance of the role a flexible and powerful Poisson solver in this project. We are building an in-house algebraic-type linear system solvers.

AMG method:
One main drawback of the geometric multigrid methods above is that they depends on grid hierarchy and problem dependent. As there has been an increasing demand of efficient black-box solvers, and the increasing geometrical complexity limits the utilization of geometrical multigrid methods, the development of algebraic multigrid (AMG) algorithms is one of the most active fields in numerical analysis nowadays. There is no method known able to deal with all practical problems and the development is expected to continue for the next years, while the efficiency and robustness will be two important issues to be considered.

AMG method is a hierarchical and matrix-based approach which allows an efficient solution to the large sparse unstructured linear systems of equations. Since A. Brandt’s first multigrid-like approach in early 1980s, which could be directly applied to algebraic equations of certain types without any pre-defined hierarchy, there have been several ways to realize concrete AMG algorithms.

For an AMG algorithm, the key step is establishing inter-grid operators. By choosing the inter-grid operators and using the Galerkin approach, a subspace of the current level vector space can be approximated decently. The point is that such a subspace should be linked to the performance of relaxation process.

There have been several ways to distinguish the “slow-to-reduce” error and to establish the inter-grid operators. For certain matrices with specific properties, the performance of the relaxation process can be predicted with respect to the entries of the matrix. Therefore, the inter-grid operators can be given depending on the matrix directly. For example, the famous Ruge-Stuben algorithm is such an example that works well for M-matrices.


AMG method in FASP package
We have implemented three different AMG methods in our FASP package
  1. Classical AMG (C-AMG)
  2. Smoothed Aggregation AMG (SA-AMG)
  3. Unsmoothed Aggregation AMG (UA-AMG)
Here are some preliminary test results:

Test Results for 2D Poisson in a unit square discretized by standard 5-point stencil

 Iter.
 Setup
 Solve
 Total
 Grid Cplx.
 Oper. Cplx.
C-AMG
 5
 4.40
 2.87
 7.27
 1.67
 2.20
SA-AMG
 9
 3.08
 3.57
 6.65
 1.16
 1.43
UA-AMG
 14
 0.78
 5.53
 6.31
 1.14
 1.20

Notation:
Note:

AMG method on GPU
One of our ongoing work is parallel AMG method on GPU. In general, a good parallel AMG method that suits GPU architecture:
We have implemented UA-AMG method on GPU based on NVIDIA CUDA environment since UA-AMG suits the above requirements. Here are some preliminary test results:
Test Results for 2D Poisson in a unit square discretized by standard 5-point stencil
Size
 Iter
 Setup
 Solve
 Total
 Grid. Cplx.
 Oper. Cplx.
1 Million
 19
 0.13
 0.47
 0.60
 1.32
 1.31
4 Million
 19
 0.62
 2.01
 2.63
 1.32
 1.31

Notation:
Note:

FASP package
Here is more about our FASP package.