Basic Algorithms

BPX preconditioner
BramblePasciakXu
(1990) introduced what is now known as the BPXpreconditioner. This
method, originally described in Xu’s PhD thesis (1989), is one of the
two most powerful multigrid approaches for solving largescale
algebraic systems that arise from the discretization of models in
science and engineering described by partial differential equations.
The method has been widely used by researchers and practitioners since
1990.


HX Preconditioner
Xu
(1996) is a pioneering work on the auxiliary space method, a
technique that uses a more structured space to construct an efficient
subspace correction method for less structured problems. A
generalization of this idea when used in concert with the BPX
preconditioner led to the optimal preconditioner of HiptmairXu
(2007) for Maxwell equations, and it was recently identified by the
U.S. Department of Energy as one of the top
ten breakthroughs in computational science in recent years.
Researchers from Sandia, Los Alamos, and Lawrence Livermore National
Labs use this algorithm for modeling fusion with magnetohydrodynamic
equations. Moreover, this approach will also be instrumental in
developing optimal iterative methods in structural mechanics,
electrodynamics, and modeling of complex flows.





Complex Fluids
LeeXu (2006) presented an original approach to
the numerical modeling of complex fluids.
Their provably stable numerical scheme for nonNewtonian
flows to simulate rheological
phenomena leads to
numerical techniques that preserve the positive
definiteness of the conformation tensor for any
range of Weissenberg numbers. This
represents a significant advance toward the
solution of the famous High Weissenberg Number Problem.
In addition, LeeXuZhang
(2010) developed numerical methods for
nonNewtonian fluids that guarantee the
discrete system has a unique solution and there
exists an iterative algorithm that converges
uniformly with respect to the Weissenberg number
and Reynolds number.

NonNewtonian
flow passing through a cylinder. Left: velocity
and pressure at t=0.5; Right: stress at t=0.5.

Left: Drag
coefficent (different Weissenberg number);
Right: History of drag coefficient.


An Optimal Preconditioner for the Biharmonic Problem
ZhangXu (2012) proposed the first mathematically
provable O(N log N) algorithm for linear systems
arising from the direct finite element
discretization of fourthorder problems on an
unstructured grid of an arbitrary domain.
This onegrid multilevel method presents a new
approach to applying the divideandconquer
strategy. It shows that some mixedform
discretizations of the fourthorder problems,
which of themselves lead to nondesirable—i.e., either
nonoptimal or nonconvergent—approximations of
the original solution, can provide optimal
preconditioners for direct finite element
discretizations. It is rigorously shown
that the preconditioners can be reduced to the
solution of a fixed number of discrete Poisson
equations. This approach will also be
instrumental in the development of optimal
iterative methods in highorder problems.

Eigenvalue
distribution of a preconditioned system: Only a
few “bad” eigenvalues are evident, which is
favorable for the PCG method.
