### Publication

1. L. Chen, R.H. Nochetto, and J. Xu. Multilevel methods on graded bisection grids. Preprint. University of Maryland. 2007.
2. L. Chen and C-S. Zhang. A coarsening algorithm and multilevel methods on adaptive grids by newest vertex bisection. Submitted. 2007.
3. L. Chen and C-S. Zhang. AFEM.at.matlab: a MATLAB package of Adaptive Finite Element Methods. Technical Report. University of Maryland. 2006.
4. L. Chen. Short bisection implementation in MATLAB. Submitted to International Workshop on Computational Science and its Education, 2006.
5. L. Chen and M.J. Holst. Mesh adaptation based on Optimal Delaunay Triangulations. Preprint. University of California, San Diego. 2006.
6. L. Chen, M.J. Holst, and J. Xu. The Finite Element Approximation of the Nonlinear Poisson-Boltzmann Equation. Accepted by SIAM Journal on Numerical Analysis, 2006.
7. L. Chen,M.J. Holst, and J. Xu. Convergence and optimality of adaptive mixed finite element methods. Submitted to Mathematics of Computation, 2006.
8. J. Jiang, S. Shu, Y. Huang, and L. Chen. A New Adaptive Mesh Method for Two Dimensional Heat Conduction Equations with Three Temperatures. Chinese Journal of Computational Physics, 24(1), 19-28, 2007.
9. L. Chen and J. Xu. Stability and accuracy of adapted finite element methods for singularly perturbed problems. Submitted to Numerische Mathematik, 2005.
10. L. Chen, P. Sun, and J. Xu. Optimal anisotropic simplicial meshes for minimizing interpolation errors in Lp-norm. Mathematics of Computation, 76(257):179–204, 2007.
11. L. Chen and J. Xu. An optimal streamline diffusion finite element method for a singularly perturbed problem. In AMS Contemporary Mathematics Series: Recent Advances in Adaptive Computation, volume 383, pages 236–246, Hangzhou, 2005.
12. L. Chen. Superconvergence of tetrahedral linear finite elements. International Journal of Numerical Analysis and Modeling, 3(3):273–282, 2006.
13. L. Chen. New analysis of the sphere covering problems and optimal polytope approximation of convex bodies. Journal of Approximation Theory, 133(1):134–145, 2005.
14. L. Chen, P. Sun, and J. Xu. Multilevel homotopic adaptive finite element methods for convection dominated problems. In The Proceedings for 15th Conferences for Domain Decomposition Methods, Lecture Notes in Computational Science and Engineering 40, pages 459–468. Springer, 2004.
15. L. Chen. Mesh smoothing schemes based on optimal Delaunay triangulations. In 13th International Meshing Roundtable, pages 109–120, Williamsburg, VA, 2004. Sandia National Laboratories.
16. L. Chen and J. Xu. Optimal Delaunay triangulations. Journal of Computational Mathematics, 22(2):299–308, 2004.

### B4

. Lecture Notes: Subspace Correction and Multigrid Methods.

ABSTRACT:
This is a short introduction to the method of subspace correction [6] on solving algebraic equations. Many iterative methods including multigrid methods can be developed and analyzed in this framework. This notes will emphasis on the theoretical convergence analysis of iterative methods, especially multigrid methods. A new identity [10] for a successive subspace correction method is included to make the analysis of multigrid methods more straightforward. The presentation mainly follows Xu’s work [6, 8, 7, 9].

CONTENTS
1. Introduction 1
2. Basic linear iterative methods 6
3. Convergence analysis of basic iterative methods 8
4. Space decomposition 12
5. Interpolation spaces using multilevel subspaces 16
6. Subspace correction 22
7. PSC: BPX and Hierarchal preconditioner 24
8. SSC: X-Z identity 27
9. Multigrid method and its convergences 32
References 38
Appendix: Matrix Theory 39

### B3

. Lecture Notes: Isotropic Adaptivity through Local Refinement.

PERFACE: This is the lecture notes for the 2006 summer school. This part will mainly discuss related topics on adaptive finite element methods (AFEMs). It includes recent development of the convergence and optimality of AFEMs through local refinement, and asymptotically exact a posteriori error estimate based on superconvergence.

### B2

and Jinchao Xu. Topics on Adaptive Finite Element Methods.

CONTENT:

1 Convergence of Adaptive Finite Element Methods 2
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Residual type error estimator . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Convergence of an adaptive finite element method . . . . . . . . . . . . . . . . 19
1.5 Optimality of the adaptive finite element method . . . . . . . . . . . . . . . . 24

1 A Posteriori Error Estimator by Post-processing 2
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Linear finite element on patch symmetric grids . . . . . . . . . . . . . . . . . 6
1.3 Linear finite element on mildly structured grids . . . . . . . . . . . . . . . . . 11
1.4 Linear finite element on general unstructured grids . . . . . . . . . . . . . . . 18

### B1

Ph. D Thesis: Robust and Accurate Algorithms for Solving Anisotropic Singularities

This dissertation is focused on the construction of robust and accurate algorithms for mathematical models of physical phenomena that exhibit strong anisotropies, that is, when the quantities have very slow and smooth variations in some directions but have rapid variations in other directions.

Our first result is on the mathematically characterization of optimal or nearly optimal meshes for a general function which could be either isotropic or anisotropic. We give an interpolation error estimate for the continuous and piecewise linear nodal interpolation. 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.

We then apply our mesh adaptation algorithms to the convection dominated convection-diffusion problems which present anisotropic singularities such as boundary layers. We develop a robust and accurate adaptive finite element method for convection dominated problems by the homotopy of the diffusion parameter.

We give an error analysis of a one dimensional convection dominated convection-diffusion problem that is discretized by the standard finite element method on layer-adapted grids. We find that it is not uniform stable with respect to the perturbation of grid points. We then design a special streamline diffusion finite element method and prove the uniform stability and optimality of our new method.

We also discuss some related concepts and problems on the optimal Delaunay triangulations.

### P7

, R.H. Nochetto, and Jinchao Xu. Multilevel methods on bisection grids.

ABSTRACT: In this paper, optimal additive and multiplicative multilevel methods are designed and analyzed on adaptive grids obtained by bisections. The analysis relies on a novel decomposition of bisection grids for bridging the results from quasi-uniform grids with locally refined grids.

### P6

and Chensong Zhang. A coarsening algorithm and multilevel methods on adaptive grids by newest vertex bisection.

ABSTRACT:
In this paper, a new coarsening algorithm is proposed for the adaptive grids obtained by the newest vertex bisection method in two dimensions. One distinguish feature of our approach is that we do not maintain the refinement tree. A new hierarchical basis preconditioner for second order elliptic equations is developed based on the nested grids obtained by the coarsening algorithm. Numerical experiments shows that the proposed coarsening algorithm and preconditioner are very efficient and easy to implement.

### P5

and Chensong Zhang. AFEM@matlab: a MATLAB package of adaptive finite element methods.

ABSTRACT:
AFEM@matlab is a MATLAB package of adaptive finite element methods (AFEMs) for stationary and evolution partial differential equations in two spatial dimensions. It contains robust, efficient, and easy-following codes for the main building blocks of AFEMs. This will benefit not only the education of the methods but also future research and algorithmic development.

### P4

, Michael Holst, and Jinchao Xu. The Finite Element Approximation of the Nonlinear Poisson-Boltzmann Equation.

ABSTRACT: A widely used electrostatics model in the biomolecular modeling community, the nonlinear Poisson-Boltzmann equation, along with its finite element approximation, are analyzed in this paper. A regularized Poisson-Boltzmann equation is introduced as an auxiliary problem, making it possible to study the original nonlinear equation with delta function sources. {\it 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 {\it a posteriori} error estimate is shown to converge. The Poisson-Boltzmann equation does not appear to have been previously studied in detail theoretically, and it is hoped that this paper will help provide molecular modelers with a better foundation for their analytical and computational work with the Poisson-Boltzmann equation. Note that this article apparently gives the first rigorous convergence result for a numerical discretization technique for the nonlinear Poisson-Boltzmann equation with delta-function sources, and it also introduces the first provably convergent adaptive method for the equation. This last result is currently one of only a handful of existing convergence results of this type for nonlinear problems.

### P3

. Short bisection implementation in MATLAB .

ABSTRACT: A short MATLAB implementation of the local mesh refinement using newest bisection or longest bisection is presented in this paper. This short implementation is helpful for the teaching of adaptive finite element methods and programming in more advanced languages.

### P2

and Michael Holst. Mesh adaptation based on Optimal Delaunay Triangulations.

ABSTRACT: In this paper, a mesh adaptation scheme based on the concept of optimal Delaunay triangulations (ODTs) is developed. The mesh adaptation is obtained by minimizing the interpolation error in the weighted $L^1$ norm. A discrete Laplacian is used as a good preconditioner in the Newton's method to speed up the traditional local smoothing approach.

### P1

, Michael Holst, and Jinchao Xu. Convergence and Optimality of Adaptive Mixed Finite Element Methods.

ABSTRACT: The convergence and optimality of adaptive mixed finite element methods for second order elliptic partial differential equations is established in this paper. The main difficulty for the mixed finite element method is the lack of minimization principle and thus the failure of orthogonality. A quasi-orthogonality property is proved using the fact that the error is orthogonal to the divergence free subspace, while the part of the error containing divergence can be bounded by data oscillation.

### A6

Jun Jiang, Shi Shu, Yunqing Huang and . A New Adaptive Mesh Method for Two Dimensional Heat Conduction Equations with Three Temperatures. Chinese Journal of Computational Physics, 24(1), 19-28, 2007.

ABSTRACT: Two dimensional heat conduction equations with three temperature is an important model in the simulation of inertial confinement fusion (ICF), which approximately describes the process of radiant energy broadcasting in the quiescent medium and energy exchange of electrons with photons and irons. A symmetric finite volume method (SFVEM) and a new mesh adaptation approach based on the Hessian matrix are proposed for the the numerical simulation in this paper. It is shown that the energy conversation error of our new approach is much better than other adaptive mesh methods using only the gradient of the solution.

### A5

and Jinchao Xu. Stability and accuracy of adapted finite element methods for singularly perturbed problems. Technique Report, Department of Mathematics, The Pennsylvania State University, :, 2005.

ABSTRACT: The stability and accuracy of a standard finite element method (FEM) and a new streamline diffusion finite element method (SDFEM) are studied in this paper for a one dimensional singularly perturbed connvection-diffusion problem discretized on arbitrary grids. Both schemes are proven to produce stable and accurate approximations provided that the underlying grid is properly adapted to capture the singularity (often in the form of boundary layers) of the solution. Surprisingly the accuracy of the standard FEM is shown to depend crucially on the uniformity of the grid away from the singularity. In other words, the accuracy of the adapted approximation is very sensitive to the perturbation of grid points in the region where the solution is smooth but, in contrast, it is robust with respect to perturbation of properly adapted grid inside the boundary layer. Motivated by this discovery, a new SDFEM is developed based on a special choice of the stabilization bubble function. The new method is shown to have an optimal maximum norm stability and approximation property in the sense that $\|u-u_{N}\|_{\infty}\leq C\inf_{v_{N}\in V^{N}}\|u-v_{N}\|_{\infty},$ where $u_{N}$ is the SDFEM approximation in linear finite element space $V^{N}$ of the exact solution $u$. Finally several optimal convergence results for the standard FEM and the new SDFEM are obtained and an open question about the optimal choice of the monitor function for the moving grid method is answered.

### A4

, Pengtao Sun and Jinchao Xu. Optimal anisotropic simplicial meshes for minimizing interpolation errors in ${L}^p$-norm. Mathematics of Computation (In Press), :, 2006.

ABSTRACT: In this paper, we present a new optimal interpolation error estimate in $L^p$ norm ($1\leq p\leq \infty$) for finite element simplicial meshes in any spatial dimension. A sufficient condition for a mesh to be nearly optimal is that it is quasi-uniform under a new metric defined by a modified Hessian matrix of the function to be interpolated. We also give new functionals for the global moving mesh method and obtain optimal monitor functions from the view points of minimizing interpolation error in the $L^p$ norm. Some numerical examples are also given to support the theoretical estimates.

### A3

Superconvergence of tetrahedral linear finite elements. International Journal of Numerical Analysis and Modeling, 3:273--282, 2006.

ABSTRACT: In this paper, we show that the piecewise linear finite element solution $u_{h}$ and the linear interpolation $u_{I}$ have superclose gradient for tetrahedral meshes, where most elements are obtained by dividing approximate parallelepiped into six tetrahedra. We then analyze a post-processing gradient recovery scheme, showing that the global $L^2$ projection of $\nabla u_h$ is a superconvergent gradient approximation to $\nabla u$.

### A2

New Analysis of the Sphere Covering Problems and Optimal Polytope Approximation of Convex Bodies. Journal of Approximation Theory, 133:134-145, 2005.

ABSTRACT: In this paper, we show that both sphere covering problems and optimal polytope approximation of convex bodies are related to optimal Delaunay triangulations, which are the triangulations minimizing the interpolation error between function $x^2$ and its linear interpolant based on the underline triangulations. We then develop a new analysis based on the estimate of the interpolation error to get the Coxeter-Few-Rogers lower bound for the thickness in the sphere covering problem and a new estimate of the constant $del_n$ appeared in the optimal polytope approximation of convex bodies.

### A1

and Jinchao Xu. Optimal {Delaunay} triangulations. Journal of Computational Mathematics, 22(2):299-308, 2004.

ABSTRACT: The Delaunay triangulation, in both classic and more generalized sense, is studied in this paper for minimizing the linear interpolation error (measure in $L^p$-norm) for a given function. The classic Delaunay triangulation can then be characterized as an optimal triangulation that minimizes the interpolation error for the isotropic function $\|\mathbf x\|^2$ among all the triangulations with a given set of vertices. For a more general function, a function-dependent Delaunay triangulation is then defined to be an optimal triangulation that minimizes the interpolation error for this function and its construction can be obtained by a simple lifting and projection procedure.
The optimal Delaunay triangulation is the one that minimizes the interpolation error among all triangulations with the same number of vertices, i.e. the distribution of vertices are optimized in order to minimize the interpolation error. Such a function-dependent optimal Delaunay triangulation is proved to exist for any given convex continuous function. On an optimal Delaunay triangulation associated with $f$, it is proved that $\nabla f$ at the interior vertices can be exactly recovered by the function values on its neighboring vertices. Since the optimal Delaunay triangulation is difficult to obtain in practice, the concept of nearly optimal triangulation is introduced and two sufficient conditions are presented for a triangulation to be nearly optimal.

### C3

and Jinchao Xu. An Optimal Streamline Diffusion Finite Element Method for a Singularly Perturbed Problem. AMS Contemporary Mathematics Series: Recent Advances in Adaptive Computation, 383:236--246, 2005.

ABSTRACT: The stability and accuracy of a streamline diffusion finite element method (SDFEM) on arbitrary grids applied to a linear 1-d singularly perturbed problem are studied in this paper. With a special choice of the stabilization quadratic bubble function, the SDFEM is shown to have an optimal second order in the sense that $\|u-u_{h}\|_{\infty}\leq C\inf_{v_{h}\in V^{h}}\|u-v_{h}\|_{\infty},$ where $u_{h}$ is the SDFEM approximation of the exact solution $u$ and $V_{h}$ is the linear finite element space. With the quasi-optimal interpolation error estimate, quasi-optimal convergence results for the SDFEM are obtained. As a consequence, an open question about the optimal choice of the monitor function for a second order scheme in the moving mesh method is answered.

### C2

Mesh smoothing schemes based on optimal {Delaunay} triangulations. 13th International Meshing Roundtable, :109-120, 2004.

ABSTRACT: We present several mesh smoothing schemes based on the concept of optimal Delaunay triangulations. We define the optimal Delaunay triangulation (ODT) as the triangulation that minimizes the interpolation error among all triangulations with the same number of vertices. ODTs aim to equidistribute the edge length under a new metric related to the Hessian matrix of the approximated function. Therefore we define the interpolation error as the mesh quality and move each node to a new location, in its local patch, that reduces the interpolation error. With several formulas for the interpolation error, we derive a suitable set of mesh smoothers among which Laplacian smoothing is a special case. The computational cost of proposed new mesh smoothing schemes in the isotropic case is as low as Laplacian smoothing while the error-based mesh quality is provably improved. Our mesh smoothing schemes also work well in the anisotropic case.

This method is sucessfully applied to 3-D mesh generation by Pierre Alliez, David Cohen-Steiner, Mariette Yvinec and Mathieu Desbrun.

### C1

and Pengtao Sun and Jinchao Xu. Multilevel Homotopic Adaptive Finite Element Methods for Convection Dominated Problems. The Proceedings for 15th Conferences for Domain Decomposition Methods, Lecture Notes in Computational Science and Engineering 40:459--468, 2004.

ABSTRACT: A multilevel homotopic adaptive methods is presented in this paper for convection dominated problems. By the homotopy method with respect to the diffusion parameter, the grid are iteratively adapted to better approximate the solution. Some new theoretic results and practical techniques for the grid adaptation are presented. Numerical experiments show that a standard finite element scheme based on this properly adapted grid works in a robust and efficient manner.