Some Research Projects
in Computational Mathematics
Jinchao Xu
Center for
Computational Mathematics and Applications
1 Introduction
Our research is mainly on the design, analysis, and applications of
numerical methods for partial differential equations. We are
interested in the study of basic discretization schemes (such as
finite element), grid adaptation and advanced iterative methods
(such as multigrid and domain decomposition). We are also interested
in applying these techniques to numerical simulations for practical
problems arising for example from complex fluids, electromagnetics,
material sciences, and fuel cells.
2 Multigrid
and Subspace Correction Methods
Collaborators: James Brannick, Ludmil
Zikatanov, and C-S. Zhang (PSU), L. Grasedyck (MPI, Leipzig), G.
Wittum (Heidelberg)
We are interested in the following basic problem: how to solve
Ax=b?
Example of Solvers:
- Gaussian elimination
- most commonly used method in practice
- black-box
- expensive
- Optimal solvers: multigrid methods
- Optimal operations
- difficult to use, problem-dependent, robust?
Our work addresses how multigrid methods can be made
- practical and user-friendly
- applicable to complicated PDEs
- robust w.r.t. various discretization and physical parameters
We study these issues using the framework of space decomposition and
subspace corrections for general iterative methods (including
multigrid and domain decomposition methods)
[11,14].
Over the years, we have
developed a number of basic algorithms such as BPX
(Bramble-Pasciak-Xu [1])
preconditioner and more recently the Hiptmair-Xu preconditioner for
H(curl) and H(div) systems [5]. We are
making major efforts in developing algebraic multigrid methods (AMG)
with various practical applications, as well as algorithms for
singular, indefinite and nearly singular
problems [12,7,6].
The multilevel and domain decomposition methods are the most
efficient methods for solving the linear systems which come from the
finite element discretization of partial differential equations.
Unfortunately, the convergence of these methods will deteriorate
rapidly when high contrast coefficients are present. Since 80's,
there are many attempts to design uniformly convergent multilevel
methods for such problems, but success has been achieved only in
special cases (for the low dimension problems, or restrictions on
the distributions of the subdomains, where the coefficients have
jumps). It is known that in the worst case, the convergence rate of
the multigrid methods is r @ 1-Ch, and the
condition number
of the preconditioned system is k(BA) @ Ch where h is
the meshsize of the finest grid.
Recently, by observing that there are only a few small eigenvalues
for the diagonal scaled discrete system, we were able to analyze the
eigenvalue distributions of the BPX, multigrid and domain
decomposition preconditioners in [13]. Our results
show that the preconditioned system, has only a fixed number of
small eigenvalues due the high contrast (jumps) in the PDE
coefficients, and all the other eigenvalues are uniformly bounded
with respect to the coefficients, and logarithmically with respect
to the meshsize. An important result that we proved is that the
asymptotic convergence rate of the corresponding preconditioned
conjugate gradient (CG) algorithm is 1-[2/(C|logh|+1)].
3 Adaptive
Mesh Refinement
Collaborators: L. Chen (UCI), P. Sun (UNLV), M.
Holst (UCSD), R. Nochetto (UMD) and Ludmil Zikatanov, Y. Zhu, C-S.
Zhang (PSU)
This project is focused on the construction of robust and accurate
adaptive algorithms for mathematical models of physical phenomena
that exhibit strong singularities.
We give mathematically characterization of optimal or nearly optimal
meshes for a general function which could be either isotropic or
anisotropic.
Roughly speaking, a nearly optimal mesh is a quasi-uniform
triangulation under some new metric defined by the Hessian matrix of
the object function. We also prove the error estimate is optimal for
strictly convex (or concave) functions.
Based on the interpolation error estimates, we introduce a new
concept Optimal Delaunay Triangulation (ODT) and present practical
algorithms to construct such nearly optimal meshes. By minimizing
the interpolation error globally or locally, we obtain some new
functionals for the moving mesh method and several new mesh
smoothing schemes.
A widely used electrostatics model in the biomolecular modeling
community, the nonlinear Poisson-Boltzmann equation, along with its
finite element approximation, are analyzed in the paper
[3].
A regularized Poisson-Boltzmann
equation is introduced as an auxiliary problem, making it possible
to study the original nonlinear equation with delta distribution
sources. A priori error estimates for the finite element
approximation is obtained for the regularized Poisson-Boltzmann
equation based on certain quasi-uniform grids in two and three
dimensions. Adaptive finite element approximation through local
refinement driven by a posteriori error estimate is shown to
converge.
In a recent paper [4], optimal
additive and multiplicative multilevel methods for solving H1
systems are designed and analyzed on adaptive grids obtained by
bisections. We have designed a novel decomposition of spaces based
on the geometric structure and a special smoothing for the newly
added nodes, thus obtaining an optimal multigrid algorithm for
locally refined grids.
In a forthcoming paper, we shall design and analyze adaptive
multigrid methods for the H(curl) and H(div) systems in three
dimensions. Our point of departure is the recent work on Hiptmair
and Xu of additive preconditioners [5]. The
analysis of multigrid for higher order Lagrange elements on the
H1 system is an essential part of this study.
4 Auxiliary
Space Maxwell Solver and H-X Preconditioner
Collaborators: R. Hiptmair (ETH), L. Zikatanov (Penn
State), R. Tuminaro (Sandia National Lab), P. Vassilevski and T. Kolev
(Lawrence Livermore National Lab), G. Wittum (University of
Heidelberg), Y. Zhu (PSU)
Develop optimal and yet practical solvers for large scale (H(curl)
and H(div)) systems of equations arising from, for example,
electro-magnetics, MHD, subsurface flows and fuel cells. Comparing
with the better-known Poisson equation (H(grad) system), the H(curl)
and H(div) are much more difficult to solve because the operators
curl and div have large kernels. Recently, Hiptmair and Xu developed
an innovative multilevel method that have been proved optimal and
also very easy to be applied in practical applications. It is now
the most efficient and most robust method for these types of
systems. But there are still a lot of open problems that need to be
studied for this newly developed algorithm, especially, when various
different systems are couple together. For example, in MHD
application, Maxwell equations are coupled with Navier-Stokes
equations.
Figure 1: 3d MHD Model Problem: our algorithm is 2 order of
magnitude
faster than the existing algorithms
LLNL's Hypre scalable solver library
(http://www.llnl.gov/CASC/linear_solvers/)
now includes our first provably scalable solver for the positive
semi-definite form of Maxwell equations on general unstructured
meshes.
Figure 2: Speedup by ASM solver
5 Multigrid
Methods for Lattice QCD
Collaborators: V. Nistor, J. Brannick, and L.
Zikatanov (PSU)
Lattice QCD calculations allow us to understand the results of
particle and nuclear physics experiments in terms of QCD, the theory
of quarks and gluons. The aim of the project is to develop numerical
methods for lattice QCD calculations. A main focus is to develop
multigrid solvers for the Dirac equation on a 4d hypercubic
space-time lattice.
This project is a close interdisciplianry collaboration between
leading particle physicists at Boston University, computational
mathematicians at CU Boulder, Lawrence Livermore National
Laboratory, and here at PSU, and Computer Scientists from Argonne
National Laboratory and University of Wuppertal, Germany.
6 Fuel Cell
Modeling and Simulations
Collaborators: P. Sun (UNLV), C. Liu, C. Wang,
G. Xue, L. Zikatanov (PSU)
Fuel cell is a clean energy conversion device which has potential to
substitute the internal combustion engine. A fuel cell has seven
components: gas channel, gas diffusion layer (GDL), catalyst layer
in both cathode and anode side, and proton exchange membrane. One
key issue in the Proton Exchange Membrane (PEM) fuel cell, is the
water management. Too much liquid water will block the open pores in
the porous media of the Gas Diffusion Layer (GDL) and cover the
surface of Catalyst Layer, too little water will dry out the
membrane. In both cases, the fuel cell cannot operate.
Correct understanding of the liquid water transport in the fuel cell
is essential to designing the fuel cell device. Mathematical
modeling and numerical simulations are now being used to study this
key issue.
A crucial part in the numerical simulations of fuel cell is the
convergence of the iterative method for the solution of this
nonlinear, coupled system. The convergence of such nonlinear
iteration for steady state simulation is very slow if one uses
commercial softwares like Star-CD or Fluent. We have recently
developed our own Fuel Cell Simulator (FCS), which is robust with
respect to all physical and chemical parameters and converges very
fast.
[10,9,2]
See Figure 6.
Figure 3: Convergence History of Fluent Simulation (Left) and
our
Fuel Cell Simulator (Right)
7 Non-Newtonian
Fluids Simulation
Collaborators: Y-J. Lee (Rutgers Univ), X. Hu
(Zhejiang Univ), J. Jia (Peking Univ), C-S. Zhang (PSU)
Fluids such as water and air are Newtonian. This means that a plot
of shear stress versus shear rate at a given temperature is a
straight line with a constant slope that is independent of the shear
rate. Any fluid that does not obey the Newtonian relationship
between the shear stress and shear rate is called non-Newtonian. The
subject of theology is devoted to the study of the behavior of such
fluids.
A non-Newtonian fluid is a fluid in which the viscosity changes with
the applied strain rate. As a result, non-Newtonian fluids may not
have a well-defined viscosity. Although the concept of viscosity is
commonly used to characterize a material, it can be inadequate to
describe the mechanical behavior of a substance. They are best
studied through several other rheological properties which relate
the relations between the stress and strain tensors under many
different flow conditions, such as oscillatory shear, or extensional
flow which are measured using different devices or rheometers.
Figure 4: von Karman vortex
simulation
For higly elastic flows, characterized by the high Weissenberg
number, the numerical simulations are notoriously difficult. For
example, Oldroyd-B model in Riccati form
We have developed proper numerical schemes [8]
that has been proven to be able to simulate such highly elastic
flows. Much of our efforts have been devoted toward the unresolved
challenge in non-Newtonian fluids simulations that has lasted for
three decades.
8 Surface
Water Waves
Collaborators: D. Henderson and M. Patterson
(PSU)
The Pritchard Lab contains a wave basin with a segmented,
programmable wave-maker system that is capable of generating both 2D
and 3D water waves. These wave motions are typically modeled by the
(inviscid) Euler equations assuming the flow to be irrotational.
Yet, both viscous and rotational effects have been observed in many
experiments. In particular, a remarkably stable 2D vortex has been
observed in 2D and weakly 3D experiments. The vortex forms near the
center of the basin, spanning its width,and then propagates slowly
to the wave-maker where it is extinguished.
Figure 5: The CCMA computing lab oversees the water wave tank.
We are currently using our grid adaptation and multigrid techniques
to develop a numerical wave basin" based on the Navier-Stokes
equations that will be used to predict wave motions as well as
resulting vortical motions.
9 Black
Hole Simulation
Collaborators: C. Sopuerta, P. Sun (UNLV), P.
Laguna
Numerical evolutions of black holes have been improved slowly but
steadily over the last few years and now first attempts are being
made to extract physical information from these evolutions. The most
notable one wants to predict the gravitational radiation emitted
during black hole coalescence.
Figure 6: 3d adaptive mesh for black hole simulation
In the case of numerical relativity, Einstein's equations constrain
our choices of these initial data. Unphysical gravitational
radiation present in the initial data will contribute to the
gravitational waves computed in an evolution. Therefore an important
question is how to control the gravitational wave content of
initial-data sets, and how to specify astrophysically relevant
initial data with the appropriate gravitational wave content, for
e.g. two black holes orbiting each other.
References
- [1]
- J. H. Bramble, J. E. Pasciak, and J. Xu. Parallel
multilevel preconditioners. Mathematics of Computation,
55(191):1-22, 1990.
- [2]
- J. Brannick, R. Falgout, J. Xu, G. Xue, and
L. Zikatanov. Algebraic multigrid methods in direct methanol fuel
cells. Preprint, 2007.
- [3]
- L. Chen, M. Holst, and J. Xu. The finite element
approximation of the nonlinear poisson-boltzmann equation. SIAM
Journal on Numerical Analysis, 45(6):2298-2320, 2007.
- [4]
- L. Chen, R. H. Nochetto, and J. Xu. Multilevel
methods on graded bisection grids I: H1 system. Preprint,
2007.
- [5]
- R. Hiptmair and J. Xu. Nodal auxiliary space
preconditioning in H(curl) and H(div) spaces. Research report no.
2006-09, ETH, Zurich, Switzerland, 2006.
- [6]
- Y. Lee, J. Wu, J. Xu, and L. Zikatanov. On
the convergence of iterative methods for semidefinite linear systems. SIAM
J. on Matrix Analysis, 2006. (to appear).
- [7]
- Y. Lee, J. Wu, J. Xu, and L. Zikatanov.
Robust subspace correction methods for nearly singular systems. (in
preparation), 2006.
- [8]
- Y.-J. Lee and J. Xu. New formulations, positivity preserving
discretizations and stability analysis for non-Newtonian flow models. Comput.
Methods Appl. Mech. Engrg., 195(9-12):1180-1206, 2006.
- [9]
- P. Sun, G. Xue, C. Y. Wang, and J. Xu. A
combined finite element-upwind finite volume method for three
dimensional simulations of liquid feed direct methanol fuel cells. Preprint,
2007.
- [10]
- P. Sun, G. Xue, C. Y. Wang, and J. Xu. A
domain decomposition method for two-phase mixture transport model in
the cathode of a polymer electrolyte fuel cell. To be submitted,
2007.
- [11]
- J. Xu. Iterative methods by space decomposition and subspace
correction. SIAM Review, 34:581-613, 1992.
- [12]
- J. Xu. A new class of iterative methods for nonselfadjoint
or indefinite problems. SIAM Journal on Numerical Analysis,
29:303-319, 1992.
- [13]
- J. Xu and Y. Zhu. Uniform convergent multigrid methods
for elliptic problems with strongly discontinuous coefficients. M3AS,
2007.
- [14]
- J. Xu and L. Zikatanov. The method of alternating
projections and the method of subspace corrections in Hilbert space. Journal
of The American Mathematical Society, 15:573-597, 2002.
File translated from
TEX
by
TTH,
version 3.79.
On 31 Dec 2007, 15:45.