Basic Algorithms

  • BPX preconditioner

Bramble-Pasciak-Xu (1990) introduced what is now known as the BPX-preconditioner. This method, originally described in Xu’s PhD thesis (1989), is one of the two most powerful multigrid approaches for solving large-scale 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 Hiptmair-Xu (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.

  • “AMS (HX preconditioner) is a perfect example of how fundamental mathematical research can lead to important software advances in high-performance computing” – DOE Panel 2008

HX-time            HX-sppedup


Compared with algorithms previously used by LLNL, the HX preconditioner:
  • Speeds up computational time on 512 processors by a factor of 24.
  • Speeds up the magnitude by more than order of 2 on 1,024 processors.
And, the HX preconditioner:
  • Takes less than 2 minutes to provide an accurate solution to a Maxwell equation with more than 35 million unknowns on 1,024 processes.

  • Complex Fluids

Lee-Xu (2006) presented an original approach to the numerical modeling of complex fluids. Their provably stable numerical scheme for non-Newtonian 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, Lee-Xu-Zhang (2010) developed numerical methods for non-Newtonian 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.

  • Xu was invited to be a co-editor (with Glowinski) for a special volume on numerical methods for non-Newtonian fluids in the prestigious Handbook of Numerical Analysis series.

u-0.5            t-0.5

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

drag            karman

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

  • An Optimal Preconditioner for the Biharmonic Problem

Zhang-Xu (2014) proposed the first mathematically provable $\mathcal{O}(N\log N)$ algorithm for linear systems arising from the direct finite element discretization of fourth-order problems on an unstructured grid of an arbitrary domain. This one-grid multilevel method presents a new approach to applying the divide-and-conquer strategy. It shows that some mixed-form discretizations of the fourth-order problems, which of themselves lead to non-desirable—i.e., either non-optimal 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 high-order problems. 


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