Yunrong Zhu

Michael Holst, Ryan Szypowski, Yunrong Zhu

In this article we study adaptive finite element methods (AFEM) with inexact solvers for a class of semilinear elliptic interface problems. We are particularly interested in nonlinear problems with discontinuous diffusion coefficients, such as the nonlinear Poisson-Boltzmann equation and its regularizations. The algorithm we study consists of the standard SOLVE-ESTIMATE-MARK-REFINE procedure common to many adaptive finite element algorithms, but where the SOLVE step involves only a full solve on the coarsest level, and the remaining levels involve only single Newton updates to the previous approximate solution. We summarize a recently developed AFEM convergence theory for inexact solvers, and present a sequence of numerical experiments that give evidence that the theory does in fact predict the contraction properties of AFEM with inexact solvers. The various routines used are all designed to maintain a linear-time computational complexity.

Michael Holst, James Andrew McCammon, Zeyun Yu et al.

We develop an efficient and reliable adaptive finite element method (AFEM) for the nonlinear Poisson-Boltzmann equation (PBE). We first examine the regularization technique of Chen, Holst, and Xu; this technique made possible the first a priori pointwise estimates and the first complete solution and approximation theory for the Poisson-Boltzmann equation. It also made possible the first provably convergent discretization of the PBE, and allowed for the development of a provably convergent AFEM for the PBE. However, in practice the regularization turns out to be numerically ill-conditioned. In this article, we examine a second regularization, and establish a number of basic results to ensure that the new approach produces the same mathematical advantages of the original regularization, without the ill-conditioning property. We then design an AFEM scheme based on the new regularized problem, and show that the resulting AFEM scheme is accurate and reliable, by proving a contraction result for the error. This result, which is one of the first results of this type for nonlinear elliptic problems, is based on using continuous and discrete a priori pointwise estimates to establish quasi-orthogonality. To provide a high-quality geometric model as input to the AFEM algorithm, we also describe a class of feature-preserving adaptive mesh generation algorithms designed specifically for constructing meshes of biomolecular structures, based on the intrinsic local structure tensor of the molecular surface. The stability advantages of the new regularization are demonstrated using an FETK-based implementation, through comparisons with the original regularization approach for a model problem. The convergence and accuracy of the overall AFEM algorithm is also illustrated by numerical approximation of electrostatic solvation energy for an insulin protein.

Long Chen, Michael Holst, Jinchao Xu et al.

The goal of this paper is to design optimal multilevel solvers for the finite element approximation of second order linear elliptic problems with piecewise constant coefficients on bisection grids. Local multigrid and BPX preconditioners are constructed based on local smoothing only at the newest vertices and their immediate neighbors. The analysis of eigenvalue distributions for these local multilevel preconditioned systems shows that there are only a fixed number of eigenvalues which are deteriorated by the large jump. The remaining eigenvalues are bounded uniformly with respect to the coefficients and the meshsize. Therefore, the resulting preconditioned conjugate gradient algorithm will converge with an asymptotic rate independent of the coefficients and logarithmically with respect to the meshsize. As a result, the overall computational complexity is nearly optimal.

Blanca Ayuso De Dios, Michael Holst, Yunrong Zhu et al.

We introduce and analyze two-level and multi-level preconditioners for a family of Interior Penalty (IP) discontinuous Galerkin (DG) discretizations of second order elliptic problems with large jumps in the diffusion coefficient. Our approach to IPDG-type methods is based on a splitting of the DG space into two components that are orthogonal in the energy inner product naturally induced by the methods. As a result, the methods and their analysis depend in a crucial way on the diffusion coefficient of the problem. The analysis of the proposed preconditioners is presented for both symmetric and non-symmetric IP schemes; dealing simultaneously with the jump in the diffusion coefficient and the non-nested character of the relevant discrete spaces presents extra difficulties in the analysis which precludes a simple extension of existing results. However, we are able to establish robustness (with respect to the diffusion coefficient) and nearly-optimality (up to a logarithmic term depending on the mesh size) for both two-level and BPX-type preconditioners. Following the analysis, we present a sequence of detailed numerical results which verify the theory and illustrate the performance of the methods. The paper includes an Appendix with a collection of proofs of several technical results required for the analysis.

Michael Holst, Sara Pollock, Yunrong Zhu

In this article we develop a convergence theory for goal-oriented adaptive finite element algorithms designed for a class of second-order semilinear elliptic equations. We briefly discuss the target problem class, and introduce several related approximate dual problems that are crucial to both the analysis as well as to the development of a practical numerical method. We then review some standard facts concerning conforming finite element discretization and error-estimate-driven adaptive finite element methods (AFEM). We include a brief summary of a priori estimates for this class of semilinear problems, and then describe some goal-oriented variations of the standard approach to AFEM (GOAFEM). Following the recent approach of Mommer-Stevenson and Holst-Pollock for increasingly general linear problems, we first establish a quasi-error contraction result for the primal problem. We then develop some additional estimates that make it possible to establish contraction of the combined primal-dual quasi-error, and subsequently show convergence with respect to the quantity of interest. Finally, a sequence of numerical experiments are then carefully examined. It is observed that the behavior of the implementation follows the predictions of the theory.

Andrew Gillette, Michael Holst, Yunrong Zhu

Arnold, Falk, and Winther [Bull. Amer. Math. Soc. 47 (2010), 281--354] showed that mixed variational problems, and their numerical approximation by mixed methods, could be most completely understood using the ideas and tools of Hilbert complexes. This led to the development of the Finite Element Exterior Calculus (FEEC) for a large class of linear elliptic problems. More recently, Holst and Stern [Found. Comp. Math. 12:3 (2012), 263--293 and 363--387] extended the FEEC framework to semi-linear problems, and to problems containing variational crimes, allowing for the analysis and numerical approximation of linear and nonlinear geometric elliptic partial differential equations on Riemannian manifolds of arbitrary spatial dimension, generalizing surface finite element approximation theory. In this article, we develop another distinct extension to the FEEC, namely to parabolic and hyperbolic evolution systems, allowing for the treatment of geometric and other evolution problems. Our approach is to combine the recent work on the FEEC for elliptic problems with a classical approach to solving evolution problems via semi-discrete finite element methods, by viewing solutions to the evolution problem as lying in time-parameterized Hilbert spaces (or Bochner spaces). Building on classical approaches by Thomee for parabolic problems and Geveci for hyperbolic problems, we establish a priori error estimates for Galerkin FEM approximation in the natural parametrized Hilbert space norms. In particular, we recover the results of Thomee and Geveci for two-dimensional domains and lowest-order mixed methods as special cases, effectively extending their results to arbitrary spatial dimension and to an entire family of mixed methods. We also show how the Holst and Stern framework allows for extensions of these results to certain semi-linear evolution problems.

Michael Holst, Ryan Szypowski, Yunrong Zhu

In this article we consider two-grid finite element methods for solving semilinear interface problems in d space dimensions, for d=2 or d=3. We first describe in some detail the target problem class with discontinuous diffusion coefficients, which includes problems containing sub-critical, critical, and supercritical nonlinearities. We then establish basic quasi-optimal a priori error estimate for Galerkin approximations. In the critical and subcritical cases, we follow our recent approach to controling the nonlinearity using only pointwise control of the continuous solution and a local Lipschitz property, rather than through pointwise control of the discrete solution; this eliminates the requirement that the discrete solution satisfy a discrete form of the maximum principle, hence eliminating the need for restrictive angle conditions in the underlying mesh. The supercritical case continues to require such mesh conditions in order to control the nonlinearity. We then design a two-grid algorithm consisting of a coarse grid solver for the original nonlinear problem, and a fine grid solver for a linearized problem. We analyze the quality of approximations generated by the algorithm, and show that the coarse grid may be taken to have much larger elements than the fine grid, and yet one can still obtain approximation quality that is asymptotically as good as solving the original nonlinear problem on the fine mesh. The algorithm we describe, and its analysis in this article, combines four sets of tools: the work of Xu and Zhou on two-grid algorithms for semilinear problems; the recent results for linear interface problems due to Li, Melenk, Wohlmuth, and Zou; recent work on the Poisson-Boltzmann equation; and recent work on a priori estimates for semilinear problems.

Randolph E. Bank, Michael Holst, Ryan Szypowski et al.

In this article we consider a priori error and pointwise estimates for finite element approximations of solutions to semilinear elliptic boundary value problems in d>=2 space dimensions, with nonlinearities satisfying critical growth conditions. It is well-understood how mesh geometry impacts finite element interpolant quality, and leads to the reasonable notion of shape regular simplex meshes. It is also well-known how to perform both mesh generation and simplex subdivision, in arbitrary space dimension, so as to guarantee the entire hierarchy of nested simplex meshes produced through subdivision continue to satisfy shape regularity. However, much more restrictive angle conditions are needed for basic a priori quasi-optimal error estimates, as well as for a priori pointwise estimates. These angle conditions, which are particularly difficult to satisfy in three dimensions in any type of unstructured or adaptive setting, are needed to gain pointwise control of the nonlinearity through discrete maximum principles. This represents a major gap in finite element approximation theory for nonlinear problems on unstructured meshes, and in particular for adaptive methods. In this article, we close this gap in the case of semilinear problems with critical or sub-critical nonlinear growth, by deriving a priori estimates directly, without requiring the discrete maximum principle, and hence eliminating the need for restrictive angle conditions. Our main result is a type of local Lipschitz property that relies only on the continuous maximum principle, together with the growth condition. We also show that under some additional smoothness assumptions, the a priori error estimate itself is enough to give pointwise control the discrete solution, without the need for restrictive angle conditions. Numerical experiments confirm our theoretical conclusions.

Blanca Ayuso De Dios, Michael Holst, Yunrong Zhu et al.

In this paper, we present a multigrid preconditioner for solving the linear system arising from the piecewise linear nonconforming Crouzeix-Raviart discretization of second order elliptic problems with jump coefficients. The preconditioner uses the standard conforming subspaces as coarse spaces. Numerical tests show both robustness with respect to the jump in the coefficient and near-optimality with respect to the number of degrees of freedom.

Yunrong Zhu

In this paper, we present a multigrid $V$-cycle preconditioner for the linear system arising from piecewise linear nonconforming Crouzeix-Raviart discretization of second order elliptic problems with jump coefficients. The preconditioner uses standard conforming subspaces as coarse spaces. We showed that the convergence rate of the multigrid $V$-cycle algorithm will deteriorate rapidly due to large jumps in coefficient. However, the preconditioned system has only a fixed number of small eigenvalues, which are deteriorated due to the large jump in coefficient, and the effective condition number is bounded logarithmically with respect to the mesh size. As a result, the multigrid $V$-cycle preconditioned conjugate gradient algorithm converges nearly uniformly. Numerical tests show both robustness with respect to jumps in the coefficient and the mesh size.

Sara Pollock, Yunrong Zhu

Comparison principles are developed for discrete quasilinear elliptic partial differential equations. We consider the analysis of a class of nonmonotone Leray-Lions problems featuring both nonlinear solution and gradient dependence in the principal coefficient, and a solution dependent lower-order term. Sufficient local and global conditions on the discretization are found for piecewise linear finite element solutions to satisfy a comparison principle, which implies uniqueness of the solution. For problems without a lower-order term, our analysis shows the meshsize is only required to be locally controlled, based on the variance of the computed solution over each element. We include a discussion of the simpler semilinear case where a linear algebra argument allows a sharper mesh condition for the lower order term.

Yunrong Zhu

In this paper, we develop the auxiliary space preconditioners for solving the linear system arising from the virtual element methods discretization on polytopal meshes for the second order elliptic equations. The preconditioners are constructed based on an auxiliary simplicial mesh. The condition numbers of the preconditioned systems are uniformly bounded, independent of the problem size and the jump in coefficients. Several numerical experiments are presented to demonstrate the performance of the preconditioners.

Sara Pollock, Yunrong Zhu

We consider a linear algebra approach to establishing a discrete comparison principle for a nonmonotone class of quasilinear elliptic partial differential equations. In the absence of a lower order term, we require local conditions on the mesh to establish the comparison principle and uniqueness of the piecewise linear finite element solution. We consider the assembled matrix corresponding to the linearized problem satisfied by the difference of two solutions to the nonlinear problem. Monotonicity of the assembled matrix establishes a maximum principle for the linear problem and a comparison principle for the nonlinear problem. The matrix analysis approach to the discrete comparison principle yields sharper constants and more relaxed mesh conditions than does the argument by contradiction used in previous work.

Sara Pollock, Yunrong Zhu

Uniqueness of the finite element solution for nonmonotone quasilinear problems of elliptic type is established in one and two dimensions. In each case, we prove a comparison theorem based on locally bounding the variation of the discrete so- lution over each element. The uniqueness follows from this result, and does not require a globally small meshsize.

Tzanio V. Kolev, Jinchao Xu, Yunrong Zhu

In this paper, we extend some of the multilevel convergence results obtained by Xu and Zhu in [Xu and Zhu, M3AS 2008], to the case of second order linear reaction-diffusion equations. Specifically, we consider the multilevel preconditioners for solving the linear systems arising from the linear finite element approximation of the problem, where both diffusion and reaction coefficients are piecewise-constant functions. We discuss in detail the influence of both the discontinuous reaction and diffusion coefficients to the performance of the classical BPX and multigrid V-cycle preconditioners.

Michael Holst, Gantumur Tsogtgerel, Yunrong Zhu

In this article we develop convergence theory for a general class of adaptive approximation algorithms for abstract nonlinear operator equations on Banach spaces, and use the theory to obtain convergence results for practical adaptive finite element methods (AFEM) applied to several classes of nonlinear elliptic equations. In the first part of the paper, we develop a weak-* convergence framework for nonlinear operators, whose Gateaux derivatives are locally Lipschitz and satisfy a local inf-sup condition. The framework can be viewed as extending the recent convergence results for linear problems of Morin, Siebert and Veeser to a general nonlinear setting. We formulate an abstract adaptive approximation algorithm for nonlinear operator equations in Banach spaces with local structure. The weak-* convergence framework is then applied to this class of abstract locally adaptive algorithms, giving a general convergence result. The convergence result is then applied to a standard AFEM algorithm in the case of several semilinear and quasi-linear scalar elliptic equations and elliptic systems, including: a semilinear problem with subcritical nonlinearity, the steady Navier-Stokes equations, and a quasilinear problem with nonlinear diffusion. This yields several new AFEM convergence results for these nonlinear problems. In the second part of the paper we develop a second abstract convergence framework based on strong contraction, extending the recent contraction results for linear problems of Cascon, Kreuzer, Nochetto, and Siebert and of Mekchay and Nochetto to abstract nonlinear problems. The contraction result is then applied to a standard AFEM algorithm for semilinear problems with sub- and super-critical nonlinearities and for the Hamiltonian constraint in general relativity.