Sara Pollock

Claire Evans, Sara Pollock, Leo G. Rebholz et al.

This paper provides the first proof that Anderson acceleration (AA) improves the convergence rate of general fixed point iterations. AA has been used for decades to speed up nonlinear solvers in many applications, however a rigorous mathematical justification of the improved convergence rate has remained lacking. The key ideas of the analysis presented here are relating the difference of consecutive iterates to residuals based on performing the inner-optimization in a Hilbert space setting, and explicitly defining the gain in the optimization stage to be the ratio of improvement over a step of the unaccelerated fixed point iteration. The main result we prove is that AA improves the convergence rate of a fixed point iteration to first order by a factor of the gain at each step. In addition to improving the convergence rate, our results indicate that AA increases the radius of convergence. Lastly, our estimate shows that while the linear convergence rate is improved, additional quadratic terms arise in the estimate, which shows why AA does not typically improve convergence in quadratically converging fixed point iterations. Results of several numerical tests are given which illustrate the theory.

Sara Pollock, Leo G. Rebholz, Mengying Xiao

We propose, analyze and test Anderson-accelerated Picard iterations for solving the incompressible Navier-Stokes equations (NSE). Anderson acceleration has recently gained interest as a strategy to accelerate linear and nonlinear iterations, based on including an optimization step in each iteration. We extend the Anderson-acceleration theory to the steady NSE setting and prove that the acceleration improves the convergence rate of the Picard iteration based on the success of the underlying optimization problem. The convergence is demonstrated in several numerical tests, with particularly marked improvement in the higher Reynolds number regime. Our tests show it can be an enabling technology in the sense that it can provide convergence when both usual Picard and Newton iterations fail.

Michael Holst, Sara Pollock

In this article we develop convergence theory for a class of goal-oriented adaptive finite element algorithms for second order nonsymmetric linear elliptic equations. In particular, we establish contraction results for a method of this type for Dirichlet problems involving the elliptic operator L u = div (A grad u) - (b,grad u) - cu, with A Lipschitz, almost-everywhere symmetric positive definite, with b divergence-free, and with c >= 0. We first describe the problem class and review some standard facts concerning conforming finite element discretization and error-estimate-driven adaptive finite element methods (AFEM). We then describe a goal-oriented variation of standard AFEM (GOAFEM). Following the recent work of Mommer and Stevenson for symmetric problems, we establish contraction of GOAFEM and convergence in the sense of the goal function. Our analysis approach is signficantly different from that of Mommer and Stevenson, combining the recent contraction frameworks developed by Cascon, Kreuzer, Nochetto and Siebert; by Nochetto, Siebert and Veeser; and by Holst, Tsogtgerel and Zhu. We include numerical results demonstrating performance of our method with standard goal-oriented strategies on a convection problem.

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.

Eric T. Chung, Sara Pollock, Sai-Mang Pun

In this research, we develop an online enrichment framework for goal-oriented adaptivity within the generalized multiscale finite element method for flow problems in heterogeneous media. The method for approximating the quantity of interest involves construction of residual-based primal and dual basis functions used to enrich the multiscale space at each stage of the adaptive algorithm. Three different online enrichment strategies based on the primal-dual online basis construction are proposed: standard, primal-dual combined and primal-dual product based. Numerical experiments are performed to illustrate the efficiency of the proposed methods for high-contrast heterogeneous problems.

Sara Pollock

An adaptive regularization strategy for stabilizing Newton-like iterations on a coarse mesh is developed in the context of adaptive finite element methods for nonlinear PDE. Existence, uniqueness and approximation properties are known for finite element solutions of quasilinear problems assuming the initial mesh is fine enough. Here, an adaptive method is started on a coarse mesh where the finite element discretization and quadrature error produce a sequence of approximate problems with indefinite and ill-conditioned Jacobians. The methods of Tikhonov regularization and pseudo-transient continuation are related and used to define a regularized iteration using a positive semidefinite penalty term. The regularization matrix is adapted with the mesh refinements and its scaling is adapted with the iterations to find an approximate sequence of coarse mesh solutions leading to an efficient approximation of the PDE solution. Local q-linear convergence is shown for the error and the residual in the asymptotic regime and numerical examples of a model problem illustrate distinct phases of the solution process and support the convergence theory.

Sara Pollock

A method is developed within an adaptive framework to solve quasilinear diffusion problems with internal and possibly boundary layers starting from a coarse mesh. The solution process is assumed to start on a mesh where the problem is badly resolved, and approximation properties of the exact problem and its corresponding finite element solution do not hold. A sequence of stabilized and inexact partial solves allow the mesh to be refined to capture internal layers while an approximate solution is built eventually leading to an accurate approximation of both the problem and its solution. The innovations in the current work include a closed form definition for the numerical dissipation and inexact scaling parameters on each mesh refinement, as well as a convergence result for the residual of the discrete problem. Numerical experiments demonstrate the method on a range of problems featuring steep internal layers and high solution dependent frequencies of the diffusion coefficients.

Sara Pollock

A method is developed for solving quasilinear convection diffusion problems starting on a coarse mesh where the data and solution-dependent coefficients are unresolved, the problem is unstable and approximation properties do not hold. The Newton-like iterations of the solver are based on the framework of regularized pseudo-transient continuation where the proposed time integrator is a variation on the Newmark strategy, designed to introduce controllable numerical dissipation and to reduce the fluctuation between the iterates in the coarse mesh regime where the data is rough and the linearized problems are badly conditioned and possibly indefinite. An algorithm and updated marking strategy is presented to produce a stable sequence of iterates as boundary and internal layers in the data are captured by adaptive mesh partitioning. The method is suitable for use in an adaptive framework making use of local error indicators to determine mesh refinement and targeted regularization. Derivation and q-linear local convergence of the method is established, and numerical examples demonstrate the theory including the predicted rate of convergence of the iterations.

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.

Sara Pollock

This work unifies pseudo-time and inexact regularization techniques for nonmonotone classes of partial differential equations, into a regularized pseudo-time framework. Convergence of the residual at the predicted rate is investigated through the idea of controlling the linearization error, and regularization parameters are defined following this analysis, then assembled in an adaptive algorithm. The main innovations of this paper include the introduction of a Picard-like regularization term scaled by its cancellation effect on the linearization error to stabilize the Newton-like iteration; an updated analysis of the regularization parameters in terms of minimizing an appropriate quantity; and, strategies to accelerate the algorithm into the asymptotic regime. Numerical experiments demonstrate the method on an anisotropic diffusion problem where the Jacobian is not continuously differentiable, and a model problem with steep gradients and a thin diffusion layer.

Peter Cowal, Nicholas F. Marshall, Sara Pollock

In this paper, we construct families of polynomials defined by recurrence relations related to mean-zero random walks. We show these families of polynomials can be used to approximate $z^n$ by a polynomial of degree $\sim \sqrt{n}$ in associated radially convex domains in the complex plane. Moreover, we show that the constructed families of polynomials have a useful rapid growth property and a connection to Faber polynomials. Applications to iterative linear algebra are presented, including the development of arbitrary-order dynamic momentum power iteration methods suitable for classes of non-symmetric matrices.

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.

Michelle Baker, Sara Pollock

In this paper, we apply acceleration to the inverse-free preconditioned Krylov subspace method introduced by Golub and Ye, which solves the symmetric generalized eigenvalue problem for the algebraically smallest eigenvalue. As the method is an improvement on steepest descent, we consider acceleration based on Nesterov accelerated steepest descent and Polyak's heavy-ball method. We extend acceleration to the block version of the Krylov subspace method and prove convergence for a more generalized choice of subspace. We present numerical results demonstrating the effect of fixed and safeguarded-adaptive choice of the momentum parameter, which show convergence in fewer outer iterations compared with LOBPCG with the same subspace size and generally fewer iterations than the base method when solving for multiple clustered eigenvalues with small dimension size. We also provide an explanation for the acceleration seen from implementing Polyak's heavy-ball method, including justifying the given parameter range.

Alexander M. Davies, Sara Pollock, Miriam E. Dennis et al.

An adaptive direct collocation method is developed for solving optimal control problems constrained by parabolic partial differential equations. The partial differential equation is first reformulated in a variational setting, where the spatial domain is discretized using the hp-Galerkin finite element method. To address nonlinearities in the variational form, a Kirchhoff-like integral transformation is applied to linearize the dynamics. In the temporal dimension, an orthogonal collocation scheme, the hp-flipped Legendre-Gauss-Radau method, is employed to fully discretize the problem, yielding a large, sparse nonlinear programming problem. Upon solving the nonlinear programming problem, solution accuracy is assessed through an implicit residual estimation procedure. This approach evaluates the local error by solving auxiliary residual problems over selected subdomains, providing a novel means of error estimation within an orthogonal collocation framework for optimal control. Based on the computed error estimate, the mesh is adaptively refined or coarsened to meet a prescribed error tolerance. Mesh refinement is guided by the estimated regularity of the solution which is determined via the decay rate of the coefficients of a Legendre polynomial expansion. In overcollocated regions, a mesh reduction strategy is adapted from orthogonal collocation methods for application within the finite element framework. Numerical examples demonstrate that the proposed method can reduce the error by up to five orders of magnitude in both spatial and temporal dimensions.

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.

Eric T. Chung, Wing Tat Leung, Sara Pollock

In this paper we develop two goal-oriented adaptive strategies for a posteriori error estimation within the generalized multiscale finite element framework. In this methodology, one seeks to determine the number of multiscale basis functions adaptively for each coarse region to efficiently reduce the error in the goal functional. Our first error estimator uses a residual based strategy where local indicators on each coarse neighborhood are the product of local indicators for the primal and dual problems, respectively. In the second approach, viewed as the multiscale extension of the dual weighted residual method (DWR), the error indicators are computed as the pairing of the local H^{-1} residual of the primal problem weighed by a projection into the primal space of the H_0^1 dual solution from an enriched space, over each coarse neighborhood. In both of these strategies, the goal-oriented indicators are then used in place of a standard residual-based indicator to mark coarse neighborhoods of the mesh for further enrichment in the form of additional multiscale basis functions. The method is demonstrated on high-contrast problems with heterogeneous multiscale coefficients, and is seen to outperform the standard residual based strategy with respect to efficient reduction of error in the goal function.