ALBERT

Description: Pointwise error estimates for the first-order div least-squares (LS) finite element method for second-order elliptic partial differential equations are presented. Direct flux approximation is considered as an important advantage of the LS method. However, there are no known pointwise error estimates for the direct flux approximation. In this paper, we provide optimal pointwise estimates which show local dependence of the error at a point and weak dependence of the global norm. As an elementary consequence of these estimates, we provide an asymptotic error expansion inequality. The inequality has applications to superconvergence and a posteriori estimates.

Description: The first-order and higher-order derivatives of a function can be viewed as the solutions of Volterra integral equations of the first kind. In this paper we propose a fast multiscale solver for the numerical solution of the Tikhonov regularization of the Volterra equations. In association with the special form of the kernels, the matrices resulting from the discretization by multiscale bases are sparse. Moreover, they can be truncated using proper strategies with only a minor loss of accuracy. In the best case, the number of nonzero entries of the truncated matrices is linear with respect to the dimensions of the matrices. The accuracy of the solution from the solver is analysed theoretically and verified by numerical experiments.

Description: The finite element method with $\mathscr {Q}_p$ elements is applied to a singularly perturbed convection–diffusion problem on an L-shaped domain. As an effect of corner singularities the exact solution is not $H^2$ -regular. Therefore, we combine a layer-adapted Shishkin mesh with a special grading adapted to the corner singularity. On such meshes we prove error estimates and estimates for the closeness error which explicitly show the influence of the grading parameter $\mu$ . Hence, $\mu$ can be chosen such that optimal error bounds are obtained. Thereby, it turns out that in the problem studied the influence of the corner singularity becomes small if the perturbation parameter $\varepsilon$ decreases. Moreover, we conduct numerical experiments that verify the theoretical results.

Description: Pták's method of nondiscrete induction is based on the idea that in the analysis of iterative processes one should aim at rates of convergence as functions rather than just numbers, because functions may give convergence estimates that are tight throughout the iteration rather than just asymptotically. In this paper we motivate and prove a theorem on nondiscrete induction, originally due to Potra and Pták, and we apply it to the Newton iterations for computing the matrix polar decomposition and the matrix square root. Our goal is to illustrate the application of the method of nondiscrete induction in the finite-dimensional numerical linear algebra context. We show the sharpness of the resulting convergence estimate analytically for the polar decomposition iteration and on some examples for the square root iteration. We also discuss some of the method's limitations and possible extensions.

Description: We consider the numerical solution, by a Petrov–Galerkin finite-element method, of a singularly perturbed reaction–diffusion differential equation posed on the unit square. In Lin & Stynes (2012, A balanced finite element method for singularly perturbed reaction-diffusion problems. SIAM J. Numer. Anal. , 50 , 2729–2743), it is argued that the natural energy norm, associated with a standard Galerkin approach, is not an appropriate setting for analysing such problems, and there they propose a method for which the natural norm is ‘balanced’. In the style of a first-order system least squares method, we extend the approach of Lin & Stynes (2012, A balanced finite element method for singularly perturbed reaction-diffusion problems. SIAM J. Numer. Anal. , 50 , 2729–2743) by introducing a constraint which simplifies the associated finite-element space and the method's analysis. We prove robust convergence in a balanced norm on a piecewise-uniform (Shishkin) mesh, and present supporting numerical results. Finally, we demonstrate how the resulting linear systems are solved optimally using multigrid methods.

Description: The construction of tensor-product surface patches with a family of Pythagorean-hodograph (PH) isoparametric curves is investigated. The simplest nontrivial instances, interpolating four prescribed patch boundary curves, involve degree $(5,4)$ tensor-product surface patches $\bf{x}(u,v)$ whose $v=\hbox {constant}$ isoparametric curves are all spatial PH quintics. It is shown that the construction can be reduced to solving a novel type of quadratic quaternion equation, in which the quaternion unknown and its conjugate exhibit left and right coefficients, while the quadratic term has a coefficient interposed between them. A closed-form solution for this type of equation is derived, and conditions for the existence of solutions are identified. The surfaces incorporate three residual scalar freedoms which can be exploited to improve the interior shape of the patch. The implementation of the method is illustrated through a selection of computed examples.

Description: Interior eigenvalues of bounded scattering objects can be rigorously characterized from multi-static and multi-frequency far field data, that is, from the behaviour of scattered waves far away from the object. This characterization, the so-called inside–outside duality, holds for various types of penetrable and impenetrable scatterers and is based on the behaviour of a particular eigenvalue of the far field operator. It naturally leads to a numerical algorithm for computing interior eigenvalues of a scatterer that does not require shape or physical properties of the scatterer as input. Since the nonlinear inverse problem to compute such interior eigenvalues from far field data is ill-posed, we propose a regularizing algorithm that is shown to converge as the noise level of the far field data tends to zero. We illustrate feasibility and accuracy of our algorithm by numerical experiments where we compute interior transmission eigenvalues and Robin eigenvalues of the Laplacian in three-dimensional domains from scattering data of these domains due to plane incident waves.

Description: We derive optimal-order a posteriori error estimates for fully discrete approximations of initial and boundary value problems for linear parabolic equations. For the discretization in time we apply the fractional-step $\vartheta $ -scheme, and for the discretization in space the finite element method with finite element spaces that are allowed to change with time. The first optimal-order a posteriori error estimates for the norms of $L^\infty (0,T;L^2(\varOmega ))$ and $L^2(0,T;H^1(\varOmega ))$ are derived by applying the reconstruction technique.

Description: In this paper, we propose a fast and accurate numerical method based on Fourier transforms to solve Kolmogorov forward equations of symmetric scalar Lévy processes. The method is based on the accurate numerical formulas for Fourier transforms proposed by Ooura. These formulas are combined with nonuniform fast Fourier transforms (FFT) and fractional FFT to speed up the numerical computations. Moreover, we propose a formula for numerical indefinite integration on equispaced grids as a component of the method. The proposed integration formula is based on the sinc-Gauss sampling formula, which is a function approximation formula. This integration formula is also combined with the FFT. Therefore, all steps of the proposed method are executed using the FFT and its variants. The proposed method allows us to be free from some special treatments for a nonsmooth initial condition and numerical time integration. The numerical solutions obtained by the proposed method appear to be exponentially convergent on the interval if the corresponding exact solutions do not have sharp cusps. Furthermore, the real computational times are approximately consistent with the theoretical estimates.

Description: In this paper, we consider the heat equation coupled with Darcy's law with a nonlinear source term describing heat production due to an exothermic chemical reaction. The existence and uniqueness of a solution are established. Next, a spectral discretization of the problem is presented and thoroughly analysed. Finally, we present some numerical experiments which confirm the interest of the discretization.

Description: The convergence of the so-called quadratic method for computing eigenvalue enclosures of general self-adjoint operators is examined. Explicit asymptotic bounds for convergence to isolated eigenvalues are found. These bounds turn out to improve significantly upon those determined in previous investigations. The theory is illustrated by means of several numerical experiments performed on particularly simple benchmark models of one-dimensional Schrödinger operators.

Description: We consider an elliptic optimal control problem where the objective functional contains evaluations of the state at a finite number of points. In particular, we use a fidelity term that encourages the state to take certain values at these points, which means that our problem is related to ones with state constraints at points. The analysis and numerical analysis differs from when the fidelity is in the $L^2$ -norm because we need the state space to embed into the space of continuous functions. In this paper, we discretize the problem using two different piecewise linear finite element methods. For each discretization we use two different approaches to prove a priori $L^2$ -error estimates for the control. We discuss the differences between these methods and approaches, and present numerical results that agree with our analytical results.

Description: A numerical scheme for the approximation of large vibration deformations of inextensible elastic curves is devised. Its unconditional stability and convergence under a regularity assumption on the velocities are demonstrated and numerical experiments are provided.

Description: We present a new scaleable algorithm for approximating the $H_{\infty }$ norm, an important robust stability measure for linear dynamical systems with input and output. Our spectral-value-set-based method uses a novel hybrid expansion–contraction scheme that, under reasonable assumptions, is guaranteed to converge to a stationary point of the optimization problem defining the $H_{\infty }$ norm, and, in practice, typically returns local or global maximizers. We prove that the hybrid expansion–contraction method has a quadratic rate of convergence that is also confirmed in practice. In comprehensive numerical experiments, we show that our new method is not only robust but exceptionally fast, successfully completing a large-scale test set 25 times faster than an earlier method by Guglielmi, Gürbüzbalaban & Overton (2013, SIAM J. Matrix Anal. Appl. , 34 , 709–737), which occasionally breaks down far from a stationary point of the underlying optimization problem.

Description: The first part of this paper enfolds a medius analysis for mixed finite element methods (FEMs) and proves a best-approximation result in $L^2$ for the stress variable independent of the error of the Lagrange multiplier under stability, compatibility and efficiency conditions. The second part applies the general result to the FEM of Arnold and Winther for linear elasticity: the stress error in $L^2$ is controlled by the $L^2$ best-approximation error of the true stress by any discrete function plus data oscillations. The analysis is valid without any extra regularity assumptions on the exact solution and also covers coarse meshes and Neumann boundary conditions. Further applications include Raviart–Thomas finite elements for the Poisson and the Stokes problems. The result has consequences for nonlinear approximation classes related to adaptive mixed FEMs.

Description: We propose a numerical method to approximate the solution of a nonlocal diffusion problem on a general setting of metric measure spaces. These spaces include, but are not limited to, fractals, manifolds and Euclidean domains. We obtain error estimates in $L^\infty (L^p)$ for $p=1,\infty $ under the sole assumption of the initial datum being in $L^p$ . An improved bound for the error in $L^\infty (L^1)$ is obtained when the initial datum is in $L^2$ . We also derive some qualitative properties of the solutions like stability, comparison principles and study the asymptotic behaviour as $t\to \infty $ . We finally present two examples on fractals: the Sierpinski gasket and the Sierpinski carpet, which illustrate on the effect of nonlocal diffusion for piece-wise constant initial datum.

Description: This paper presents a Riemannian trust region algorithm for unconstrained optimization problems with locally Lipschitz objective functions defined on complete Riemannian manifolds. To this end we define a function $\Phi :TM\rightarrow \mathbb {R}$ on the tangent bundle $TM$ , and at the $k$ th iteration, using the restricted function $\Phi |_{T_{x_k}M}$ , where $T_{x_k}M$ is the tangent space at $x_k$ , a local model function $Q_k$ that carries both first- and second-order information for the locally Lipschitz objective function $f:M\rightarrow \mathbb {R}$ on a Riemannian manifold $M$ , is defined and minimized over a trust region. We establish the global convergence of the proposed algorithm. Moreover, using the Riemannian $\varepsilon $ -subdifferential, a suitable model function is defined. Numerical experiments illustrate our results.

Description: Variational inequalities play an important role in many applications and are an active research area. Optimal a priori error estimates in the natural energy norm do exist, but only very few results are known for different norms. Here, we consider as prototype a simple Signorini problem, and provide new optimal order a priori error estimates for the trace and the flux on the Signorini boundary. The a priori analysis is based on a continuous and a discrete Steklov–Poincaré operator, as well as on Aubin–Nitsche-type duality arguments. Numerical results illustrate the convergence rates of the finite-element approach.

Description: We show for adaptive triangulations in two dimensions, which are generated by the newest vertex bisection, an optimal grading estimate. Roughly speaking, we construct from the piecewise constant mesh-size function a regularized one with the following two properties. First, the two functions are equivalent, and second, the regularized mesh-size function differs at most by a factor of 2 on neighbouring elements. In combination with Bank & Yserentant (2014, Numer. Math. 126 , 361–381), this optimal grading estimate enables us to show that the $L_2$ -orthogonal projections onto the space of continuous Lagrange finite elements up to order 12 is $H^1$ -stable. We extend these results to a modified red–green refinement.

Description: There exist at least three first-order finite volume element methods with totally different dual meshes and conforming or nonconforming $P_1$ finite element trial functions and the question arises of whether they are comparable. The fact that the underlying norms are very different does not prevent the proof that the errors are equivalent on any mesh in some norm. This equivalence is independent of the regularity of the exact solution and holds for any coarse or fine mesh with or without local mesh refining, but up to equivalence constants and additional explicit data-oscillation terms of higher order. The equivalence constants depend on the minimal angle of the shape-regular triangulation and the penalization parameter of the discontinuous Galerkin scheme. This also implies quasi-optimality in the sense that the error is bounded by the best approximation of the flux by piecewise constants. An a posteriori error analysis for the discontinuous Galerkin finite volume element scheme is also discussed. The analysis is exemplified for a boundary value model problem for some second-order elliptic partial differential equation in two dimensions.

Description: We show the existence and uniqueness of a solution for the nonlocal vector-valued Allen–Cahn variational inequality in a formulation involving Lagrange multipliers for local and nonlocal constraints. Furthermore, we propose and analyse a primal–dual active set (PDAS) method for local and nonlocal vector-valued Allen–Cahn variational inequalities. The local convergence behaviour of the PDAS algorithm is studied by interpreting the approach as a semismooth Newton method and numerical simulations are presented demonstrating its efficiency.

Description: In this paper, we will present a generalized convolution quadrature for solving linear parabolic and hyperbolic evolution equations. The original convolution quadrature method by Lubich works very nicely for equidistant time steps while the generalization of the method and its analysis to nonuniform time stepping is by no means obvious. We will introduce the generalized convolution quadrature allowing for variable time steps and develop a theory for its error analysis. This method opens the door for further development towards adaptive time stepping for evolution equations. As the main application of our new theory, we will consider the wave equation in exterior domains which is formulated as a retarded boundary integral equation.

Description: We address the error control of Galerkin discretization (in space) of linear second-order hyperbolic problems. More specifically, we derive a posteriori error bounds in the L ( L 2 ) norm for finite element methods for the linear wave equation, under minimal regularity assumptions. The theory is developed for both the space-discrete case and for an implicit fully discrete scheme. The derivation of these bounds relies crucially on carefully constructed space and time reconstructions of the discrete numerical solutions, in conjunction with a technique introduced by Baker (1976, Error estimates for finite element methods for second-order hyperbolic equations. SIAM J. Numer. Anal. , 13 , 564–576) in the context of a priori error analysis of Galerkin discretization of the wave problem in weaker-than-energy spatial norms.

Description: The surface finite element method can be used to approximate curvatures on embedded hypersurfaces and to discretize geometric partial differential equations. In this paper, we present a definition of discrete Ricci curvature on polyhedral hypersurfaces of arbitrary dimension based on the discretization of a weak formulation with isoparametric finite elements. We prove that for a piecewise quadratic approximation of a two- or three-dimensional hypersurface R n +1 , this definition approximates the Ricci curvature of with a linear order of convergence in the L 2 ( ) norm. By using a smoothing scheme in the case of a piecewise linear approximation of , we still get a convergence of order 2/3 in the L 2 ( ) norm and of order 1/3 in the W 1, 2 ( ) norm.

Description: We give general conditions which guarantee that the sequence generated by a descent algorithm converges to an equilibrium point. The convergence result is based on the Lojasiewicz gradient inequality; optimal convergence rates are also derived, as well as a stability result. We show how our results apply to a large variety of standard time discretizations of gradient-like flows. Schemes with variable time step are considered and optimal conditions on the maximal step size are derived. Applications to time and space discretizations of the Allen–Cahn equation, the sine–Gordon equation and a damped wave equation are given.

Description: This paper presents quadratic finite-volume methods for elliptic and parabolic problems on quadrilateral meshes that use Barlow points (optimal stress points) for dual partitions. Introducing Barlow points into the finite-volume formulations results in better approximation properties at the cost of loss of symmetry. The novel ‘symmetrization’ technique adopted in this paper allows us to derive optimal-order error estimates in the H 1 - and L 2 -norms for elliptic problems and in the L ( H 1 )- and L ( L 2 )-norms for parabolic problems. Superconvergence of the difference between the gradients of the finite-volume solution and the interpolant can also be derived. Numerical results confirm the proved error estimates.

Description: A linear parabolic differential equation on a moving surface is discretized in space by evolving-surface finite elements and in time by backward difference formulas (BDFs). Using results from Dahlquist's G-stability theory and Nevanlinna & Odeh's multiplier technique together with properties of the spatial semidiscretization, stability of the full discretization is proved for BDF methods up to order 5 and optimal-order convergence is shown. Numerical experiments illustrate the behaviour of the fully discrete method.

Description: In this article, we develop the a priori and a posteriori error analysis of hp -version interior penalty discontinuous Galerkin finite element methods for strongly monotone quasi-Newtonian fluid flows in a bounded Lipschitz domain R d , d = 2, 3. In the latter case, computable upper and lower bounds on the error are derived in terms of a natural energy norm, which are explicit in the local mesh size and local polynomial degree of the approximating finite element method. A series of numerical experiments illustrate the performance of the proposed a posteriori error indicators within an automatic hp -adaptive refinement algorithm.

Description: In recent years, it has become increasingly clear that the critical issue in gradient methods is the choice of the step length, whereas using gradient as the search direction may lead to very effective algorithms, whose surprising behaviour has only been partially explained, mostly in terms of the spectrum of the Hessian matrix. On the other hand, the convergence of the classical Cauchy steepest descent (SD) method has been analysed extensively and related to the spectral properties of the Hessian matrix, but the connection with the spectrum of the Hessian has not been exploited much to modify the method in order to improve its behaviour. In this work, we show how, for convex quadratic problems, moving from some theoretical properties of the SD method, second-order information provided by the step length can be exploited to dramatically improve the usually poor practical behaviour of this method. This allows us to achieve computational results comparable with those of the Barzilai and Borwein algorithm, with the further advantage of monotonic behaviour.

Description: In recent years, there has been an enormous interest in developing methods for the approximation of manifold-valued functions. In this paper, we focus on the manifold of symmetric positive-definite (SPD) matrices. We investigate the use of SPD-matrix means to adapt linear positive approximation methods to SPD-matrix-valued functions. Specifically, we adapt corner-cutting subdivision schemes and Bernstein operators. We present the concept of admissible matrix means and study the adapted approximation schemes based on them. Two important cases of admissible matrix means are treated in detail: the exp–log and the geometric matrix means. We derive special properties of the approximation schemes based on these means. The geometric mean is found to be superior in the sense of preserving more properties of the data, such as monotonicity and convexity. Furthermore, we give error bounds for the approximation of univariate SPD-matrix-valued functions by the adapted operators.

Description: We present a mass-preserving scheme for the stochastic nonlinear Schrödinger equation with multiplicative noise of Stratonovich type. It is a splitting scheme and we present an explicit formula for solving the sub-step related to the nonlinear part. The scheme is unconditionally stable in the L 2 norm. For the linear stochastic Schrödinger equation, we prove that the scheme has a strong convergence rate in time equal to 1, which is not common for stochastic partial differential equations with noise depending on space and time.

Description: A numerical scheme for the approximation of the elastic flow of inextensible curves is devised and convergence of approximations to exact solutions of the nonlinear time-dependent partial differential equation is proved. The nonlinear, pointwise constraint of local length preservation is linearized about a previous solution in each time step which leads to a sequence of linear saddle-point problems. The spatial discretization is based on piecewise Bézier curves and the resulting semiimplicit scheme is unconditionally stable and convergent.

Description: We study the coercivity properties and the norm dependence on the wave-number k of certain regularized combined field boundary integral operators that we recently introduced for the solution of two- and three-dimensional acoustic scattering problems with Neumann boundary conditions. We show that in the case of circular and spherical boundaries, our regularized combined field boundary integral operators are L 2 coercive for large enough values of the coupling parameter, and that the norms of these operators are bounded by constant multiples of the coupling parameter. We establish that the norms of the regularized combined field boundary integral operators grow modestly with the wave-number k for smooth boundaries and we provide numerical evidence that these operators are L 2 coercive for two-dimensional starlike boundaries. We present and analyse a fully discrete collocation (Nyström) method for the solution of two-dimensional acoustic scattering problems with Neumann boundary conditions based on regularized combined field integral equations. In particular, for analytic boundaries and boundary data, we establish pointwise superalgebraic convergence rates of the discrete solutions.

Description: The classical theory of Gaussian quadrature assumes a positive weight function. We will show that in some cases Gaussian rules can be constructed with respect to an oscillatory weight, yielding methods with complex quadrature nodes and positive weights. These rules are well suited to highly oscillatory integrals because they attain optimal asymptotic order. We show that, for the Fourier oscillator, this approach yields the numerical method of steepest descent, a method with optimal asymptotic order that has previously been proposed for this class of integrals. However, the approach readily extends to more general kernels, such as Bessel functions that appear as the kernel of the Hankel transform.

Description: We consider anisotropic Allen–Cahn equations with interfacial energy induced by an anisotropic surface energy density . Assuming that is positive, positively homogeneous of degree 1, strictly convex in tangential directions to the unit sphere and sufficiently smooth, we show the stability of various time discretizations. In particular, we consider a fully implicit and a linearized time discretization of the interfacial energy combined with implicit and semiimplicit time discretizations of the double-well potential. In the semiimplicit variant, concave terms are taken explicitly. The arising discrete spatial problems are solved by globally convergent truncated nonsmooth Newton multigrid methods. Numerical experiments show the accuracy of the different discretizations. We also illustrate that pinch-off under anisotropic mean curvature flow is no longer invariant under rotation of the initial configuration for a fixed orientation of the anisotropy.

Description: In this paper, we define a new finite element method for numerically approximating the solution of a partial differential equation in a bulk region coupled with a surface partial differential equation posed on the boundary of the bulk domain. The key idea is to take a polyhedral approximation of the bulk region consisting of a union of simplices, and to use piecewise polynomial boundary faces as an approximation of the surface. Two finite element spaces are defined, one in the bulk region and one on the surface, by taking the set of all continuous functions which are also piecewise polynomial on each bulk simplex or boundary face. We study this method in the context of a model elliptic problem; in particular, we look at well-posedness of the system using a variational formulation, derive perturbation estimates arising from domain approximation and apply these to find the optimal-order error estimates. A numerical experiment is described which demonstrates the order of convergence.

Description: As a model of more general contour integration problems we consider the numerical calculation of high-order derivatives of holomorphic functions using Cauchy's integral formula. Bornemann (2011, Accuracy and stability of computing high-order derivatives of analytic functions by Cauchy integrals. Found. Comput. Math. , 11 , 1–63) showed that the condition number of the Cauchy integral strongly depends on the chosen contour and solved the problem of minimizing the condition number for circular contours. In this paper, we minimize the condition number within the class of grid paths of step size h using Provan's algorithm for finding a shortest enclosing walk in weighted graphs embedded in the plane. Numerical examples show that optimal grid paths yield small condition numbers even in those cases where circular contours are known to be of limited use, such as for functions with branch-cut singularities.

Description: Anisotropic meshes are important for efficiently resolving incompressible flow problems that include boundary layer or corner singularity phenomena. Unfortunately, the stability of standard inf–sup stable mixed approximation methods is prone to degeneracy whenever the mesh aspect ratio becomes large. As an alternative, a stabilized mixed approximation method is considered here. Specifically, a robust a priori error estimate for the local jump stabilized Q 1 – P 0 approximation introduced by Kechkar & Silvester (1992, Analysis of locally stabilized mixed finite element methods for the Stokes problem. Math. Comp. , 58 , 1–10) is established for anisotropic meshes. Our numerical results demonstrate that the stabilized Q 1 – P 0 method is competitive with the nonconforming, nonparametric, rotated approximation method introduced by Rannacher & Turek (1992, Simple nonconforming quadrilateral Stokes element. Numer. Meth. Partial Differential Equations , 8 , 97–111).

Description: This work is about the numerical solution of the time-domain Maxwell's equations in dispersive propagation media by a discontinuous Galerkin time-domain method. The Debye model is used to describe the dispersive behaviour of the media. The resulting system of differential equations is solved using a centred-flux discontinuous Galerkin formulation for the discretization in space and a second-order leapfrog scheme for the integration in time. The numerical treatment of the dispersive model relies on an auxiliary differential equation approach similar to that which is adopted in the finite difference time-domain method. Stability estimates are derived through energy considerations and convergence is proved for both the semidiscrete and the fully discrete schemes.

Description: The parabolic singularly perturbed problem u xx ( x , t ) – x α u t ( x , t ) = f ( x , t ) is considered on the rectangular domain = (0,1) x (0, T ] with Dirichlet initial and boundary conditions. Here, is a small positive parameter and α is a positive constant. This problem is degenerate since the coefficient x α of u t vanishes along the side x = 0 of . Bounds on the derivatives of u are used to design a nonuniform mesh and a finite difference method on this mesh is constructed to solve the problem numerically. As the solution u is not in general uniformly bounded with respect to in the maximum norm, the convergence analysis of the numerical method requires the use of some unusual barrier functions and a special weighted discrete norm. Numerical examples are provided to support the theoretical results.

Description: We consider the numerical approximation of a general second-order semilinear parabolic stochastic partial differential equation driven by multiplicative and additive space–time noise. We examine convergence of exponential integrators for multiplicative and additive noise. We consider noise that is in a trace class and give a convergence proof in the root-mean-square L 2 norm. We discretize in space with the finite element method and in our implementation we examine both the finite element and the finite volume methods. We present results for a linear reaction–diffusion equation in two dimensions as well as a nonlinear example of a two-dimensional stochastic advection–diffusion–reaction equation motivated from realistic porous media flow.

Description: Sparse grids (Zenger, C. (1990) Sparse grids. Parallel Algorithms for Partial Differential Equations (W. Hackbusch ed.) Notes on Numerical Fluid Dynamics 31. Proceedings of the Sixth GAMM-Seminar; Bungartz, H.-J. & Griebel, M. (2004) Sparse grids. Acta Numer. , 13 , 1–123.) are tailored to the approximation of smooth high-dimensional functions. On a d -dimensional tensor product space, the number of grid points is N = O( h –1 |log h | d –1 ), where h is a mesh parameter. The so-called combination technique, based on hierarchical decomposition and extrapolation, requires specific multivariate error expansions of the discretization error on Cartesian grids to hold. We derive such error expansions for linear difference schemes through an error correction technique of semi-discretizations. We obtain overall error formulae of the type = O ( h p |log h | d –1 ) and analyse the convergence, with its dependence on dimension and smoothness, by examples of linear elliptic and parabolic problems, with numerical illustrations in up to eight dimensions.

Description: The numerical simulation of two-phase flow in a porous medium may lead, when using coupled finite volume schemes on structured grids, to the appearance of the so-called Grid Orientation Effect (GOE). We propose in this paper a procedure to eliminate this phenomenon, based on the use of new fluxes with a new stencil in the discrete version of the convection equation, without changing the discrete scheme for computing the pressure field. Numerical results show that the GOE does not significantly decrease with the size of the discretization using the initial scheme on the coupled problem, but that it is efficiently suppressed by the new procedure, even on coarse meshes. A mathematical study, based on a weak BV inequality using the new fluxes, confirms the convergence of the modified scheme in a particular case.

Description: We build nonuniform numerical meshes for the finite difference and finite element approximations of the one-dimensional wave equation, ensuring that all numerical solutions reach the boundary, as continuous solutions do, in the sense that the full discrete energy can be observed by means of boundary measurements, uniformly with respect to the mesh size. The construction of the nonuniform mesh is achieved by means of a concave diffeomorphic transformation of a uniform grid into a nonuniform one, making the mesh finer and finer when approaching the right boundary. For uniform meshes it is known that high-frequency numerical wave packets propagate very slowly without ever getting to the boundary. Our results show that this pathology can be avoided by taking suitable nonuniform meshes. This also allows us to build convergent numerical algorithms for the approximation of boundary controls of the wave equation.

Description: Spectral discretizations based on rectangular differentiation matrices have recently been demonstrated to be a convenient means of solving linear and nonlinear ordinary differential equations with general boundary conditions and other side constraints. Here, we present explicit formulae for such matrices.

Description: We devise an improved iterative scheme for the numerical solution of total variation regularized minimization problems. The numerical method realizes a primal–dual iteration with discrete metrics that allow for large step sizes.

Description: We extend the ideas of Diening et al. (2015, Instance optimality of the adaptive maximum strategy. Found. Comput. Math. ), from conforming approximations of the Poisson problem to nonconforming Crouzeix–Raviart approximations of the Poisson and Stokes problems in two dimensions. As a consequence, we obtain instance optimality of an adaptive finite element method with a modified maximum marking strategy.

Description: The manuscript presents a technique for efficiently solving the classical wave equation, the shallow water equations, and, more generally, equations of the form $\partial u /\partial t = \mathcal {L}u$ , where $\mathcal {L}$ is a skew-Hermitian differential operator. The idea is to explicitly construct an approximation to the time-evolution operator $\exp (\tau \mathcal {L})$ for a relatively large time-step $\tau $ . Recently developed techniques for approximating oscillatory scalar functions by rational functions, and accelerated algorithms for computing functions of discretized differential operators are exploited. Principal advantages of the proposed method include: stability even for large time-steps, the possibility to parallelize in time over many characteristic wavelengths and large speed-ups over existing methods in situations where simulation over long times are required. Numerical examples involving the 2D rotating shallow water equations and the 2D wave equation in an inhomogenous medium are presented, and the method is compared to the 4th order Runge–Kutta (RK4) method and to the use of Chebyshev polynomials. The new method achieved high accuracy over long-time intervals, and with speeds that are orders of magnitude faster than both RK4 and the use of Chebyshev polynomials.

Description: The computation of eigenvalues nearest the imaginary axis is a hard problem. It is a useful tool for computing eigenvalues with largest real part (also called right-most eigenvalues) of matrix pairs arising from the stability analysis of a dynamical system. We present an efficient implementation of the Lyapunov inverse iteration method, presented by Meerbergen and Spence [(2010) Shift-and-invert iteration for purely imaginary eigenvalues with application to the detection of Hopf bifurcations in large scale problems. SIAM J. Matrix Anal. Appl. , 31 , 1463–1482]. It turns out that when we use the approximate power Lyapunov solver, the method corresponds to the implicitly restarted rational Krylov method and resembles the Iterative Rational Krylov Algorithm for model reduction. Elman and Wu [(2013) Lyapunov inverse iteration for computing a few right-most eigenvalues of large generalized eigenvalue problems. SIAM J. Matrix Anal. Appl ., 34 , 1685–1707] proved that an accurate solution of the Lyapunov equation guarantees the accurate computation of eigenvalues, and often, the right-most eigenvalues. However, the approach in this paper is usually cheaper in terms of memory and allows us to compute more than one eigenvalue more efficiently.

Description: For interpolating between elements of ${\rm SO}{(n)}$ , it is attractive to work in $n$ , passing from one space to the other via the exponential map. However, the logarithm is a multi-valued map and the choice of a particular image affects the quality of the interpolation. In this paper, we propose a fast and accurate algorithm to compute the image that seems the most appropriate for interpolation: given $Q \in {\rm SO}{(n)}$ and $A \in n$ , our algorithm returns the logarithm of $Q$ which is the closest to $A$ , under minimal conditions on $Q$ . We carefully study the mathematical properties of our problem to establish the algorithm, discuss its implementation and demonstrate its efficiency.

Description: We propose a limited memory steepest descent (LMSD) method for solving unconstrained optimization problems. As a steepest descent method, the step computation in each iteration requires the evaluation of a gradient of the objective function and the calculation of a scalar step size only. When employed to solve certain convex problems, our method reduces to a variant of the LMSD method proposed by Fletcher (2012, Math. Program. , 135 , 413–436), which means that, when the history length parameter is set to 1, it reduces to a steepest descent method inspired by that proposed by Barzilai & Borwein (1988, IMA J. Numer. Anal. , 8 , 141–148). However, our method is novel in that we propose new algorithmic features for cases when nonpositive curvature is encountered. That is, our method is particularly suited for solving nonconvex problems. With a nonmonotone line search, we ensure global convergence for a variant of our method. We also illustrate with numerical experiments that our approach often yields superior performance when employed to solve nonconvex problems.

Description: The recently developed TECNO schemes for hyperbolic conservation laws are designed to be high-order accurate and entropy stable, but are, as of yet, only semidiscrete. We perform an explicit discretization of the temporal derivative to obtain a fully discrete scheme, and derive a rather unrestrictive CFL condition that ensures global entropy stability. The scheme is tested in a series of numerical experiments.

Description: In this work, we present several computational results on the complex biharmonic problems. First, we derive fast Fourier transform recursive relation (FFTRR)-based fast algorithms for solving Dirichlet- and Neumann-type complex Poisson problems in the complex plane. These are based on the use of FFT, analysis-based RRs in Fourier space, and high-order quadrature methods. Our second result is the application of these fast Poisson algorithms to solving four types of inhomogeneous biharmonic problems in the complex plane using decomposition methods. Lastly, we apply these high-order accurate fast algorithms for the complex inhomogeneous biharmonic problems to solving Stokes flow problems at low and moderate Reynolds number. All these algorithms are inherently parallelizable, though only sequential implementations have been performed. These algorithms have theoretical complexity of the order ${{\mathcal O}}(\log N)$ per grid point, where $N^2$ is the total number of grid points in the discretization of the domain. These algorithms have many other desirable features, some of which are discussed in the paper. Numerical results have been presented which show performance of these algorithms.

Description: For the saddle point problem arising from the finite element discretization of the hybrid formulation of the time-harmonic eddy current problem, we propose an alternating positive-semidefinite splitting (APSS) preconditioner which is based on two positive-semidefinite splittings of the saddle point matrix. It is proved that the corresponding APSS iteration method is unconditionally convergent. We show that the new preconditioner is much easier to implement than the block alternating splitting implicit preconditioner proposed in Bai (2012, Numer. Linear Algebra Appl. , 19 , 914–936) when they are used to accelerate the convergence rate of Krylov subspace methods such as GMRES. Numerical examples are given to show the effectiveness of our proposed preconditioner.

Description: The stability radius of an n x n matrix A (or distance to instability) is a well-known measure of robustness of stability of the linear stable dynamical system $\dot{x} = Ax$ . Such a distance is commonly measured either in the 2-norm or in the Frobenius norm. Even if the matrix A is real, the distance to instability is most often considered with respect to complex-valued matrices (in such case the two norms turn out to be equivalent) and restricting the distance to real matrices makes the problem more complicated, and in the case of Frobenius norm—to our knowledge—unresolved. Here, we present a novel approach to approximate real stability radii, particularly well-suited for large sparse matrices. The method consists of a two-level iteration, the inner one aiming to compute the -pseudospectral abscissa of a low-rank (1 or 2) dynamical system, and the outer one consisting of an exact Newton iteration. Due to its local convergence property, it generally provides upper bounds for the stability radii, but in practice usually computes the correct values. The method requires the computation of the rightmost eigenvalue of a sequence of matrices, each of them given by the sum of the original matrix A and a low-rank 1. This makes it particularly suitable for large sparse problems, for which several existing methods become inefficient, due to the fact that they require to solve full Hamiltonian eigenvalue problems and/or compute multiple singular value decompositions (SVDs).

Description: Two fully discrete, discontinuous Galerkin schemes with time-dynamic, locally refined meshes in space are developed for a fourth-order Cahn–Hilliard equation with an added nonlinear reaction term, a phenomenological model that can describe cancerous tumour growth. The proposed schemes, which are both second-order in time, are based on a primitive-variable discontinuous Galerkin spatial formulation that is valid in any number of space dimensions. We prove that the schemes are convergent, with optimal-order error bounds, even in the case where the mesh is changing with time, provided that the number of mesh changes is bounded by some constant. The schemes represent flexible, high-order accurate alternatives to the standard mixed C 0 finite element methods and nonconforming (plate) finite element methods for solving fourth-order parabolic partial differential equations. We conclude the paper with tests showing the convergence of the scheme at the predicted rates and the flexibility of the method for approximating complex solution dynamics efficiently.

Description: We analyse a variational time discretization of geodesic calculus on finite- and certain classes of infinite-dimensional Riemannian manifolds. We investigate the fundamental properties of discrete geodesics, the associated discrete logarithm, discrete exponential maps and discrete parallel transport, and we prove convergence to their continuous counterparts. The presented analysis is based on the direct method in the calculus of variation, on -convergence and on weighted finite element error estimation. The convergence results of the discrete geodesic calculus are experimentally confirmed for a basic model on a two-dimensional Riemannian manifold. This provides a theoretical basis for the application to shape spaces in computer vision, for which we present one specific example.

Description: This paper analyses the approximate solution of very weakly well-posed hyperbolic Cauchy problems. These problems have very sensitive dependence on initial data. We treat a single family of such problems showing that, in spite of the sensitive dependence, approximate solutions with desired precision can be computed in finite-precision arithmetic with cost growing polynomially in 1/. The sensitive dependence requires high finite precision. The analysis required a new Gevrey stability estimate for the leapfrog scheme. The latter depends on a new discrete Glaeser inequality. The cost of calculating solutions with features on a scale 〈〈1 grows as e C –1/2 .

Description: We discuss the construction of volume-preserving splitting methods based on a tensor product of single-variable basis functions. The vector field is decomposed as the sum of elementary divergence-free vector fields (EDFVFs), each of them corresponding to a basis function. The theory is a generalization of the monomial basis approach introduced in Xue & Zanna (2013, BIT Numer. Math. , 53 , 265–281) and has the trigonometric splitting of Quispel & McLaren (2003, J. Comp. Phys. , 186 , 308–316) and the splitting in shears of McLachlan & Quispel (2004, BIT , 44 , 515–538) as special cases. We introduce the concept of diagonalizable EDFVFs and identify the solvable ones as those corresponding to the monomial basis and the exponential basis. In addition to giving a unifying view of some types of volume-preserving splitting methods already known in the literature, the present approach allows us to give a closed-form solution also to other types of vector fields that could not be treated before, namely those corresponding to the mixed tensor product of monomial and exponential (including trigonometric) basis functions.

Description: Splitting methods constitute a well-established class of numerical schemes for the solution of evolution equations. Their efficient application, however, requires spatial smoothness of the underlying exact solution. If smoothness is lacking, the methods usually react with order reduction. Depending on the data and the type of boundary condition, splitting methods on rectangular domains, in general, suffer from such order reductions. This is mainly due to corner singularities arising in the solution. In this paper, the regularity of the Dirichlet problem on a rectangle is studied. On the one hand, this analysis reveals compatibility conditions that lead to smooth solutions; on the other hand, it motivates a modification of the original scheme to overcome the order reduction. This idea is exemplified for the Lie splitting. Numerical experiments illustrate the efficiency of the approach.

Description: We prove several discrete Gagliardo–Nirenberg–Sobolev and Poincaré–Sobolev inequalities for some approximations with arbitrary boundary values on finite volume meshes. The key point of our approach is to use the continuous embedding of the space BV( ) into L N /( N –1) ( ) for a Lipschitz domain R N , with N ≥2. Finally, we give several applications to discrete duality finite volume schemes which are used for the approximation of nonlinear and nonisotropic elliptic and parabolic problems.

Description: We consider an optimal control problem subject to the one-dimensional Landau–Lifshitz–Gilbert equation, which describes the evolution of magnetizations in S 2 . The problem is motivated in order to control switching processes of ferromagnets. Existence of an optimum and the first-order necessary optimality system are derived. We show (up to subsequences) convergence of state, adjoint and control variables of a time discretization (semi-implicit Euler method) for vanishing time step size. A main step here is to verify corresponding stability properties for the semidiscrete state, which is nontrivial since the iterates take values which only approximate S 2 . We use a perturbation argument within a variational discretization in order to show error bounds for the semidiscrete state variables, from which we may then infer uniform bounds for the semidiscrete state and also adjoint variables. Numerical studies underline these results and compare this discretization with a further variant, which bases on a projection strategy for the state equation to enhance iterates to better approximate S 2 .

Description: In the past 10 years, the ‘parareal’ (parallel-in-time) algorithm has attracted lots of attention thanks to its excellent performance in scientific computing. The parareal algorithm is iterative and is characterized by two propagators G and F which are associated with a coarse step size T and a fine step size t , respectively, where T = J t and J ≥2 is an integer. When we apply this algorithm to large-scale systems of ordinary differential equations obtained by semidiscretizing partial differential equations, two questions arise naturally. (I) Is the error between the iterate and the target solution contractive at each iteration for any choice of the discretization parameters T , J and x ? (II) How small can the contraction factor be and can such a contraction factor be independent of the discretization parameters? For linear problems u '= A u + g with symmetric negative-definite matrix A , when the implicit Euler method is used as both the G - and F-propagators, positive answers to these two questions were given by Mathew et al. (2010, SIAM J. Sci. Comput. , 32 , 1180–1200) and the contraction factor can be bounded by 0.298 for any choice of the discretization parameters. In this paper, for the case that the implicit Euler method is used as the G -propagator, we provide a positive answer to (I) for three second-order F -propagators: the trapezoidal method, the TR/BDF2 method and the two-stage diagonally implicit Runge–Kutta (2s-DIRK) method. For (II), we prove that the contraction factors can be bounded by 0.316 and 1/3 for the 2s-DIRK method and the TR/BDF2 method (provided the parameter involved in TR/BDF2 satisfies [0.043, 0.977]), respectively, and both bounds are independent of the discretization parameters. For the trapezoidal method, we show that a uniform bound (less than 1) of the contraction factor does not exist. Numerical results are presented to validate the theoretical prediction.

Description: In this paper, we develop a spectral method based on generalized Laguerre functions for the Camassa–Holm equation. We first introduce four normed spaces and present their equivalence relations, which enables us to develop and to analyse generalized Laguerre approximations efficiently. We also establish some basic results on generalized Laguerre orthogonal approximations. The spectral scheme for the Camassa–Holm equation is proposed, and the convergence is proved. Numerical results demonstrate the spectral accuracy.

Description: We prove convergence of a fully discrete finite difference scheme for the Korteweg–de Vries equation. Both the decaying case on the full line and the periodic case are considered. If the initial data $u|_{t=0}=u_0$ is of high regularity, $u_0\in H^3({\mathbb {R}})$ , the scheme is shown to converge to a classical solution, and if the regularity of the initial data is less, $u_0\in L^2({\mathbb {R}})$ , then the scheme converges strongly in $L^2(0,T;L^2_{{\rm loc}}({\mathbb {R}}))$ to a weak solution.

Description: We propose a new variational formulation of the elliptic Monge–Ampère equation and show how classical Lagrange elements can be used for the numerical resolution of classical solutions of the equation. Error estimates are given for Lagrange elements of degree d ≥ n in dimensions n = 2 and n = 3. No jump term is used in the variational formulation. We propose to solve the discrete nonlinear system of equations by a time marching method, and numerical evidence is given which indicates that one approximates in two dimension a larger class of nonsmooth solutions than what is possible if one simply uses Newton's method.

Description: Efficient time integration methods based on operator splitting are introduced for the Westervelt equation, a nonlinear damped wave equation that arises in nonlinear acoustics as a mathematical model for the propagation of sound waves in high intensity ultrasound applications. A global error estimate is deduced for the first-order Lie–Trotter splitting method, confirming that the splitting method remains stable, and that the nonstiff convergence order is retained in situations where the problem data are sufficiently regular. Fundamental ingredients in the stability and error analysis are regularity results for the Westervelt equation and related linear evolution equations of hyperbolic and parabolic type. Numerical examples illustrate and complement the theoretical investigations.

Description: Bounded, semi-infinite Hankel matrices of finite rank over the space 2 of square-summable sequences occur frequently in classical analysis and engineering applications. The notion of finite rank often appears under different contexts and the literature is diverse. The first part of this paper reviews some elegant, classical criteria and establishes connections among the various characterizations of finite rank in terms of rational functions, recursion, matrix factorizations and sinusoidal signals. All criteria require 2 d parameters, though with different meanings, for a matrix of rank d . The Vandermonde factorization, in particular, permits immediately a singular-value preserving, finite-dimensional representation of the original semi-infinite Hankel matrix and, hence, makes it possible to retrieve the nonzero singular values of the semi-infinite Hankel matrix. The second part of this paper proposes using the LDL* decomposition of a specially constructed sample matrix to find the unitarily equivalent finite-dimensional representation. This approach enjoys several advantages, including the ease of computation by avoiding infinite-dimensional vectors, the ability to reveal rank deficiency and the established pivoting strategy for stability. No error analysis is given, but several computational issues are discussed.

Description: Certain numerical methods for initial value problems have as stability function the n th partial sum of the exponential function. We study the stability region, that is, the set in the complex plane over which the n th partial sum has at most unit modulus. It is known that the asymptotic shape of the part of the stability region in the left half-plane is a semidisc. We quantify this by providing discs that enclose or are enclosed by the stability region or its left half-plane part. The radius of the smallest disc centred at the origin that contains the stability region (or its portion in the left half-plane) is determined for 1≤ n ≤20. Bounds on such radii are proved for n ≥2; these bounds are shown to be optimal in the limit n -〉+. We prove that the stability region and its complement, restricted to the imaginary axis, consist of alternating intervals of length tending to , as n -〉. Finally, we prove that a semidisc in the left half-plane centred at the origin and with vertical boundary lying on the imaginary axis is included in the stability region if and only if n 0 mod 4 or n 3 mod 4. The maximal radii of such semidiscs are exactly determined for 1≤ n ≤20.

Description: An absolutely stable weak Galerkin (WG) finite element method is introduced and analysed for the Helmholtz equation. This means that the stability and well-posedness of the method for any wave number k can be derived without a mesh-size constraint. This method is designed by using a discrete weak gradient operator applied to discontinuous piecewise polynomials on finite element partitions consisting of polygons in two dimensions or polyhedra in three dimensions with certain shape regularity. Error estimates in both discrete H 1 - and L 2 -norms are established for these WG finite element solutions. Numerical examples are tested to support the theory.

Description: Surface finite element methods (SFEMs) are widely used to solve surface partial differential equations arising in applications including crystal growth, fluid mechanics and computer graphics. A posteriori error estimators are computable measures of the error and are used to implement adaptive mesh refinement. Previous studies of a posteriori error estimation in SFEM have mainly focused on bounding energy norm errors. In this work, we derive a posteriori L 2 and pointwise error estimates for piecewise linear SFEM for the Laplace–Beltrami equation on implicitly defined surfaces. There are two main error sources in SFEM, a ‘Galerkin error’ arising in the usual way for finite element methods, and a ‘geometric error’ arising from replacing the continuous surface by a discrete approximation when writing the finite element equations. Our work includes numerical estimation of the dependence of the error bounds on the geometric properties of the surface. We provide also numerical experiments where the estimators have been used to implement an adaptive FEM over surfaces with different curvatures.

Description: In this paper we consider explicit, implicit and semiimplicit finite difference schemes for a general nonlinear reaction–diffusion equation. The stability condition for each method is established and several particular cases are highlighted. To illustrate the theoretical results we present some numerical examples.

Description: Sparse tensor product finite elements (FEs) are used for discretizing the high-dimensional multiscale homogenized equation of a linear elasticity equation in R d that depends on n microscopic scales. The solution to the homogenized equation that describes the macroscopic property and the corrector terms that encode the microscopic information are obtained with accuracy and complexity essentially equal to that for solving a one-scale macroscopic equation in R d . An approximation for the solution of the multiscale equation in terms of the FE solution of this high-dimensional problem is obtained. For two-scale problems, an explicit error for this approximation in terms of the FE mesh width and the microscopic scale is deduced. Numerical examples of two- and three-scale elasticity equations in two dimensions confirm the analysis.

Description: The celebrated truncated T-matrix method for wave propagation models belongs to a class of the reduced basis methods (RBMs), with the parameters being incident waves and incident directions. The T-matrix characterizes the scattering properties of the obstacles independent of the incident and receiver directions. In the T-matrix method the reduced set of basis functions for representation of the scattered field is constructed analytically and hence, unlike other classes of the RBM, the T-matrix RBM avoids computationally intensive empirical construction of a reduced set of parameters and the associated basis set. However, establishing a convergence analysis and providing practical a priori estimates for reducing the number of basis functions in the T-matrix method has remained an open problem for several decades. In this work we solve this open problem for time-harmonic acoustic scattering in two and three dimensions. We numerically demonstrate the convergence analysis and the a priori parameter estimates for both point-source and plane-wave incident waves. Our approach can be used in conjunction with any numerical method for solving the forward wave propagation problem.

Description: We derive an algorithm for the adaptive approximation of solutions to parabolic equations. It is based on adaptive finite elements in space and the implicit Euler discretization in time with adaptive time-step sizes. We prove that, given a positive tolerance for the error, the adaptive algorithm reaches the final time with a space–time error between continuous and discrete solution that is below the given tolerance. Numerical experiments reveal a more than competitive performance of our algorithm ASTFEM (adaptive space–time finite element method).

Description: We propose and analyse a new family of nonconforming elements for the Brinkman problem of porous media flow. The corresponding finite element methods are robust with respect to the limiting case of Darcy flow, and the discretely divergence-free functions are in fact divergence-free. Therefore, in the absence of sources and sinks, the method is strongly mass-conservative. We also show how the proposed elements are part of a discrete de Rham complex.

Description: In this paper we investigate the superconvergence of local discontinuous Galerkin (LDG) methods for solving one-dimensional linear time-dependent fourth-order problems. We prove that the error between the LDG solution and a particular projection of the exact solution, e u , achieves th-order superconvergence when polynomials of degree k ( k ≥ 1) are used. Numerical experiments with P k polynomials, with 1 ≤ k ≤ 3, are displayed to demonstrate the theoretical results, which show that the error e u actually achieves ( k +2)th-order superconvergence, indicating that the error bound for e u obtained in this paper is suboptimal. Initial boundary value problems, nonlinear equations and solutions having singularities, are numerically investigated to verify that the conclusions hold true for very general cases.

Description: The discrete mollification method, a convolution-based filtering procedure for the regularization of illposed problems, is applied here to stabilize explicit schemes, which were first analysed by Karlsen & Risebro (2001, An operator splitting method for nonlinear convection–diffusion equations. M2AN Math. Model. Numer. Anal. 35 , 239–269) for the solution of initial value problems of strongly degenerate parabolic partial differential equations in two space dimensions. Two new schemes are proposed, which are based on directionwise and two-dimensional discrete mollification of the second partial derivatives forming the Laplacian of the diffusion function. The mollified schemes permit substantially larger time steps than the original (basic) scheme. It is proven that both schemes converge to the unique entropy solution of the initial value problem. Numerical examples demonstrate that the mollified schemes are competitive in efficiency, and in many cases significantly more efficient, than the basic scheme.

Description: A family of explicit adaptive algorithms is designed to solve nonlinear scalar one-dimensional conservation laws. Based on the Godunov scheme on a uniform grid, a first strategy uses the multiresolution analysis of the solution to design an adaptive grid that evolves in time according to the time-dependent local smoothness. The method is furthermore enhanced by a local time-stepping strategy. Both numerical schemes are shown to converge towards the unique entropy solution.

Description: In this paper the first error analyses of hybridizable discontinuous Galerkin (HDG) methods for convection–diffusion equations for variable-degree approximations and nonconforming meshes are presented. The analysis technique is an extension of the projection-based approach recently used to analyse the HDG method for the purely diffusive case. In particular, for approximations of degree k on all elements and conforming meshes, we show that the order of convergence of the error in the diffusive flux is k + 1 and that of a projection of the error in the scalar unknown is 1 for k = 0 and k + 2 for k 〉 0. When nonconforming meshes are used our estimates do not rule out a degradation of 1/2 in the order of convergence in the diffusive flux and a loss of 1 in the order of convergence of the projection of the error in the scalar variable. However, they do guarantee the optimal convergence of order k + 1 of the scalar variable.

Description: Fast multigrid solvers are considered for the linear systems arising from the bilinear finite element discretizations of second-order elliptic equations with anisotropic diffusion. Optimal convergence of Vcycle multigrid methods in the semicoarsening case and nearly optimal convergence of V-cycle multigrid method with line smoothing in the uniformly-coarsening case are established using the Xu-Zikatanov identity. Since the ‘regularity assumption’ is not used in the analysis, the results can be extended to general domains consisting of rectangles.

Description: In this paper we consider a class of incompressible viscous fluids whose viscosity depends on the shear rate and pressure. We deal with isothermal steady flow and analyse the Galerkin discretization of the corresponding equations. We discuss the existence and uniqueness of discrete solutions and their convergence to the solution of the original problem. In particular, we derive a priori error estimates, which provide optimal rates of convergence with respect to the expected regularity of the solution. Finally, we demonstrate the achieved results by numerical experiments. The fluid models under consideration appear in many practical problems, for instance, in elastohydrodynamic lubrication where very high pressures occur. Here we consider shear-thinning fluid models similar to the power-law/Carreau model. A restricted sublinear dependence of the viscosity on the pressure is allowed. The mathematical theory concerned with the self-consistency of the governing equations has emerged only recently. We adopt the established theory in the context of discrete approximations. To our knowledge, this is the first analysis of the finite element method for fluids with pressure-dependent viscosity. The derived estimates coincide with the optimal error estimates established recently for Carreau-type models, which are covered as a special case.

Description: Discrete maximum principles (DMPs) are established for finite element approximations of systems of nonlinear parabolic partial differential equations with mixed boundary and interface conditions. The results are based on an algebraic DMP for suitable systems of ordinary differential equations.

Description: The adaptive cubic regularization algorithm described in Cartis et al. (2009, Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. , 127 , 245–295; 2010, Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity [online]. Math. Program. , DOI: 10.1007/s10107-009-0337-y) is adapted to the problem of minimizing a nonlinear, possibly nonconvex, smooth objective function over a convex domain. Convergence to first-order critical points is shown under standard assumptions, without any Lipschitz continuity requirement on the objective's Hessian. A worst-case complexity analysis in terms of evaluations of the problem's function and derivatives is also presented for the Lipschitz continuous case and for a variant of the resulting algorithm. This analysis extends the best-known bound for general unconstrained problems to nonlinear problems with convex constraints.

Description: This work is intended to provide a convenient tool for the mathematical analysis of a particular kind of finite volume approximation which can be used, for instance, in the context of nonlinear and/or anisotropic diffusion operators in three dimensions (3D). Following the so-called DDFV (discrete duality finite volume) approach developed by Hermeline (1998, Une méthode de volumes finis pour les équations elliptiques du second ordre. C. R. Math. Acad. Sci. Paris , 326 , 1433–1436 (in French); 2000, A finite volume method for the approximation of diffusion operators on distorted meshes. J. Comput. Phys. , 160 , 481–499) and by Domelevo & Omnès (2005, A finite volume method for the Laplace equation on almost arbitrary two-dimensional grids. M2AN Math. Model. Numer. Anal. , 39 , 1203–1249) in 3D, we consider a ‘double’ covering T of a 3D domain by a rather general primal mesh and by a well-chosen ‘dual’ mesh. The associated discrete divergence operator div  T is obtained by the standard finite volume approach. A simple and consistent discrete gradient operator T is defined by a local affine interpolation that takes into account the geometry of the double mesh. Under mild geometrical constraints on the choice of the dual volumes, we show that –div  T and T are linked by the ‘discrete duality property’, which is an analogue of the integration-by-parts formula. The primal mesh need not be conformal, and its interfaces can be general polygons. We give several numerical examples for anisotropic linear diffusion problems; good convergence properties are observed. The sequel, Andreianov et al. (2011a, On 3D DDFV discretization of gradient and divergence operators. II. Discrete functional analysis tools and applications to degenerate parabolic problems. HAL preprint available at http://hal.archives-ouvertes.fr/hal-00567342 ) to this paper will summarize some key discrete functional analysis tools for DDFV schemes and give applications to proving convergence of DDFV schemes for several nonlinear degenerate parabolic partial differential equations.

Description: This work is concerned with the numerical implementation of the discrepancy principle for nonsmooth Tikhonov regularization for linear inverse problems. First, some theoretical properties of the solutions to the discrepancy equation, i.e., uniqueness and upper bounds, are discussed. Then, the idea of Padé approximation is exploited for designing model functions with model parameters iteratively updated. Two algorithms are proposed for its efficient numerical realization, i.e., a two-parameter algorithm based on model functions and a quasi-Newton method, and their convergence properties are briefly discussed. Numerical results for four nonsmooth models are presented to demonstrate the accuracy of the principle and to illustrate the efficiency and robustness of the proposed algorithms.

Description: This paper is devoted to the convergence analysis of the upwind finite volume scheme for the initialand boundary-value problems associated with the linear transport equation in any dimension, on general unstructured meshes. We are particularly interested in the case where the initial and boundary data are in L and the advection vector field has low regularity properties, namely L 1 (]0, T [, ( W 1,1 ()) d ), with suitable assumptions on its divergence. In this general framework, we prove uniform in time strong convergence in L p (), with p 〈 +, of the approximate solution towards the unique weak solution of the problem as well as the strong convergence of its trace. The proof relies, in particular, on the Friedrichs' commutator argument, which is classical in the renormalized solutions theory. Note that this result remains valid if the data are suitably approximated in L 1 . This is nothing but the discrete counterpart of the nice compactness properties deduced from the renormalized solution theory. We conclude with some numerical experiments showing that the convergence rate seems to be 1/2, as in the case of smoother advection fields, but this is still an open question up to now.

Description: In this paper, we study the existence, uniqueness and regularity properties of solutions for the nonstandard Volterra integral equation . We then present a collocation method to solve this equation, and analyse the convergence and superconvergence of piecewise polynomial collocation approximations. We also illustrate the theoretical results by extensive numerical experiments.

Description: In this paper we consider the discretization error in space and time of an H 1 gradient flow for an energy integral where the energy density is given by the sum of a double-well potential term and a bending energy term. We show that the problem is equivalent to a nonlinear heat equation with nonlocal nonlinearity and adapt the standard error analysis theory developed for the nonlinear heat equation to our case. In doing so we bound the discretization error in terms of the mesh size and time step as well as energy parameters. In particular, we carefully track how the size of the bending energy affects the error bounds.

Description: A local convergence analysis of Newton's method for finding a singularity of a differentiable vector field defined on a complete Riemannian manifold, based on the majorant principle, is presented in this paper. This analysis provides a clear relationship between the majorant function, which relaxes the Lipschitz continuity of the derivative, and the vector field under consideration. It also allows us to obtain the optimal convergence radius and the biggest range for the uniqueness of the solution and to unify some previously unrelated results.

Description: For analytic functions we study the kernel of the remainder terms of Gaussian quadrature rules with respect to Bernstein–Szego weight functions where 0〈 α 〈 β , β != 2 α , | |〈 β – α , and whose denominator is an arbitrary polynomial of exact degree 2 that remains positive on [–1, 1]. The subcase α =1, β =2/(1+ ), –1〈 〈0 and =0 has been considered recently by Spalevíc, M. M. & Praníc, M. S. ((2010) Error bounds of certain Gaussian quadrature formulae. J. Comput. Appl. Math., 234 , 1049–1057). The location on the elliptic contours where the modulus of the kernel attains its maximum value is investigated. This leads to effective error bounds for the corresponding Gaussian quadratures. The approach we use in this paper, which is different from the one adopted in Spalevíc, M. M. & Praníc, M. S. ((2010) Error bounds of certain Gaussian quadrature formulae. J. Comput. Appl. Math., 234 , 1049–1057), ensures that the actual conditions for determining the locations on the elliptic contours where the modulus of the kernel attains its maximum value are approximated very precisely.

Description: We consider an electromagnetic scattering problem produced by a perfect conductor. We pose the problem in a bounded region surrounding the obstacle and impose on the exterior boundary of the computational domain an impedance boundary condition inspired by the asymptotic behaviour of the scattered field at infinity. The operator associated with our problem belongs to a class of operators for which a suitable decomposition of the energy space plays an essential role in the analysis. This decomposition is performed here through a regularizing projector that takes into account the boundary conditions. The discrete version of this projector is the key tool to prove that a Galerkin scheme based on Nédélec’s edge elements is well posed and convergent under general topological assumptions on the scatterer and without assuming special requirements on the triangulations.

Description: Gould and Robinson (2010, SIAM J. Optim. , 20 , 2023–2048; 2010, SIAM J. Optim. , 20 , 2049–2079) introduced a second-derivative sequential quadratic programming method (S2QP) for solving nonlinear nonconvex optimization problems. We proved that the method is globally and locally superlinearly convergent under common assumptions. A critical component of the algorithm is the so-called predictor step, which is computed from a strictly convex quadratic program with a trust-region constraint. This step is essential for proving global convergence but its propensity to identify the optimal active set is paramount for achieving fast local convergence. Thus the global and local efficiency of the method is intimately coupled with the quality of the predictor step. In this paper we study the effects of removing the trust-region constraint from the computation of the predictor step. This is reasonable since the resulting problem is still strictly convex and thus well defined. Although it is interesting theoretically to verify that the same convergence guarantees hold when no trust-region constraint is used, our motivation is based on the practical behaviour of the algorithm. Preliminary numerical experience with S2QP indicates that the trust-region constraint occasionally degrades the quality of the predictor step and diminishes its ability to correctly identify the optimal active set. Moreover, removal of the trust-region constraint allows for re-use of the predictor step over a sequence of failed iterations, thus reducing computation. We show that the modified algorithm remains globally convergent and preserves local superlinear convergence provided that a nonmonotone strategy is incorporated.

Description: We consider a recently proposed finite-element space that consists of piecewise affine functions with discontinuities across a smooth given interface (a curve in two dimensions, a surface in three dimensions). Contrary to existing extended finite element methodologies, the space is a variant of the standard conforming $${\mathbb{P}}_{1}$$ space that can be implemented element by element. Further, it neither introduces new unknowns nor deteriorates the sparsity structure. It is proved that, for u arbitrary in $${W}^{1,p}(\Omega \setminus \Gamma )\cap {W}^{2,s}(\Omega \setminus \Gamma )$$ , the interpolant $${\mathcal{I}}_{h}u$$ defined by this new space satisfies where h is the mesh size, $$\Omega \subset {\mathbb{R}}^{d}$$ is the domain, $$p 〉 d$$ , $$p\ge q$$ , $$s\ge q$$ and standard notation has been adopted for the function spaces. This result proves the good approximation properties of the finite-element space as compared to any space consisting of functions that are continuous across , which would yield an error in the $${L}^{q}(\Omega )$$ -norm of order . These properties make this space especially attractive for approximating the pressure in problems with surface tension or other immersed interfaces that lead to discontinuities in the pressure field. Furthermore, the result still holds for interfaces that end within the domain, as happens for example in cracked domains.

Description: A linear parabolic differential equation on a moving surface is first discretized in space by evolving surface finite elements and then in time by an implicit Runge–Kutta (RK) method. For algebraically stable and stiffly accurate RK methods unconditional stability of the full discretization is proven and the convergence properties are analysed. Moreover, the implementation is described for the case of the Radau IIA time discretization. Numerical experiments illustrate the behaviour of the fully discrete method.

Description: We consider the nonlinear spatially homogeneous Boltzmann equation and its Fourier spectral discretization in velocity space involving periodic continuation of the density and a truncation of the collision operator. We allow discretization based on arbitrary sets of active Fourier modes with particular emphasis on the family of so-called hyperbolic cross approximations. We also discuss an offset method that takes advantage of the known equilibrium solutions. Extending the analysis in Filbet & Mouhot (2011, Analysis of spectral methods for the homogeneous Boltzmann equation. Trans. Amer. Math. Soc. , 363 , 1947–1980), we establish consistency estimates for the discrete collision operators and stability of the semidiscrete evolution. Under an assumption of Gaussian-like decay of the discrete solution, we give a detailed bound for $H^{s}$ -Sobolev norms of the error due to Fourier spectral discretization.

Description: This paper enfolds a medius analysis for first-order nonconforming finite element methods (FEMs) in linear elasticity named after Crouzeix–Raviart and Kouhia–Stenberg, which are robust with respect to the incompressible limit as the Lamé parameter $\lambda$ tends to infinity. The new result is a best-approximation error estimate for the stress error in $L^2$ up to data-oscillation terms. Even for very coarse shape-regular triangulations, two comparison results assert that the errors of the nonconforming FEM are equivalent to those of the conforming first-order FEM. The explicit role of the parameter $\lambda$ in those equivalence constants leads to an advertisement of the robust and quasi-optimal Kouhia–Stenberg FEM, in particular for nonconvex polygons. The proofs are based on conforming companions, a new discrete Helmholtz decomposition and a new discrete-plus-continuous Korn inequality for Kouhia–Stenberg finite element functions. Numerical evidence strongly supports the robustness of the nonconforming FEMs with respect to incompressibility locking and with respect to singularities, and underlines that the dependence of the equivalence constants on $\lambda$ in the comparison of conforming and nonconforming FEMs cannot be improved. This work therefore advertises the Kouhia–Stenberg FEM as a first-order robust discretization in linear elasticity in the presence of Neumann boundary conditions.

Description: This paper develops and analyses two fully discrete interior penalty discontinuous Galerkin (IP-DG) methods for the Allen–Cahn equation, which is a nonlinear singular perturbation of the heat equation and originally arises from phase transition of binary alloys in materials science, and its sharp interface limit (the mean curvature flow) as the perturbation parameter tends to zero. Both fully implicit and energy-splitting time-stepping schemes are proposed. The primary goal of the paper is to derive sharp error bounds which depend on the reciprocal of the perturbation parameter $\epsilon$ (also called ‘interaction length’) only in some lower polynomial order, instead of exponential order, for the proposed IP-DG methods. The derivation is based on a refinement of the nonstandard error analysis technique first introduced in Feng & Prohl (2003, Numerical analysis of the Allen–Cahn equation and approximation for mean curvature flows. Numer. Math. , 2003, 94 , 33–65). The centrepiece of this new technique is to establish a spectrum estimate result in totally discontinuous DG finite element spaces with the help of a similar spectrum estimate result in the conforming finite element spaces which was established in Feng & Prohl. As a nontrivial application of the sharp error estimates, they are used to establish convergence, and the rates of convergence of the zero-level sets of the fully discrete IP-DG solutions to the classical and generalized mean curvature flow. Numerical experiment results are also presented to gauge the theoretical results and the performance of the proposed fully discrete IP-DG methods.