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.




  • Finite Element Method for High-order PDEs


Wang-Xu (2007, 2011) gives the only canonical and universal construction of a class of convergent finite element spaces for any order of elliptic and parabolic equations in any spatial dimension. This method allows the use of piecewise polynomials of the lowest-order degree for constructing convergent, stable, and practical finite element discretization methods for higher order partial differential equations, including those that occur in magnetohydrodynamics modeled in plasma physics and shell and those that in occur in plate models in structural mechanics.

MorleyWangXuElements

Recently, Xu-Zhang (2012) applied order reduction on the solver level and developed a robust and efficient preconditioner for biharmonic problems on unstructured grids using the auxiliary space method framework.  The new preconditioner is formed by smoothers and Poisson solvers.  If the domain is convex, the condition number is bounded by a constant. If the domain is nonconvex, there are just a few bad eigenvalues (no more than the number of concave corner points of the domain), such that the preconditoned Krylov method will still be efficient.



  • 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 (2012) proposed the first mathematically provable 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. 


Biharmonic

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