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
 transform a complicated system into a sequence of
simpler systems by using auxiliary spaces;
 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, diffusionconvectionreaction, 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 inhouse
algebraictype 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 blackbox
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
matrixbased approach which allows an efficient solution to the
large sparse unstructured linear systems of equations. Since A.
Brandt’s first multigridlike approach in early 1980s, which
could be directly applied to algebraic equations of certain
types without any predefined hierarchy, there have been several
ways to realize concrete AMG algorithms.
For an AMG algorithm, the key step
is establishing intergrid operators. By choosing the intergrid
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 “slowtoreduce” error and to establish the
intergrid 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 intergrid operators can be given depending on the matrix
directly. For example, the famous RugeStuben algorithm is such
an example that works well for Mmatrices.
AMG method in FASP package
We have implemented three
different AMG methods in our FASP package
 Classical AMG (CAMG)
 Smoothed Aggregation AMG (SAAMG)
 Unsmoothed Aggregation AMG (UAAMG)
Here are some preliminary test results:
Test Results
for 2D Poisson in a unit square discretized by standard 5point
stencil

Iter.

Setup

Solve

Total

Grid Cplx.

Oper. Cplx.

CAMG

5

4.40

2.87

7.27

1.67

2.20

SAAMG

9

3.08

3.57

6.65

1.16

1.43

UAAMG

14

0.78

5.53

6.31

1.14

1.20

Notation:
 Iter.: number of iterations
 Setup: setup time in sceonds
 Solve: solve time in sceonds
 Total: total CPU time in sceonds
 Grid. Cplx.: grid complexity
 Oper. Cplx. operator complexity
Note:
 Relative residual less than 1.0e6
 Intel Core 2 Duo 2.4 GHz, 8GB Ram, gcc4.4, O3
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:
 regular sparsity pattern on each level
 low complexity
 low setup cost
 finegrain parallelism
 take advantage of hierarchical GPU memory
structure
We have implemented UAAMG method on GPU based on NVIDIA CUDA
environment since UAAMG suits the above requirements. Here are
some preliminary test results:
Test Results
for 2D Poisson in a unit square discretized by standard 5point
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:
 Size: size of the problem
 Iter.: number of iterations
 Setup: setup time in sceonds
 Solve: solve time in sceonds
 Total: total CPU time in sceonds
 Grid. Cplx.: grid complexity
 Oper. Cplx. operator complexity
Note:
 Relative residual less than 1.0e6
 Double Precision
 NVIDIA Tesla C2070, nvcc, CUDA release 4.0, V0.2.1221
FASP package
Here is more about our
FASP package.