Search

Dynamical low-rank algorithms are a class of numerical methods that compute lowrank approximations of dynamical systems. This is accomplished by projecting the dynamics onto a low-dimensional manifold and writing the solution directly in terms of the low-rank factors. The approach has been successfully applied to many types of differential equations. Recently, efficient dynamical low-rank algorithms have been proposed in [L. Einkemmer, A Low-Rank Algorithm for Weakly Compressible Flow, arXiv:1804.04561, 2018; L. Einkemmer and C. Lubich, SIAM J. Sci. Comput., 40 (2018), pp. B1330-B1360] to treat kinetic equations, including the Vlasov-Poisson and the Boltzmann equation. There it was demonstrated that the methods are able to capture the lowrank structure of the solution and significantly reduce numerical cost, while often maintaining high accuracy. However, no numerical analysis is currently available. In this paper, we perform an error analysis for a dynamical low-rank algorithm applied to the multiscale linear Boltzmann equation (a classical model in kinetic theory) to showcase the validity of the application of dynamical lowrank algorithms to kinetic theory. The equation, in its parabolic regime, is known to be rank 1 theoretically, and we will prove that the scheme can dynamically and automatically capture this low-rank structure. This work thus serves as the first mathematical error analysis for a dynamical low-rank approximation applied to a kinetic problem. [ABSTRACT FROM AUTHOR]

We consider the scalar conservation law with flux function discontinuous in the space variable, i.e., \begin{eqnarray} \label{eq1} u_t+(H(x)f(u)+(1-H(x))g(u))_{x} &=& 0 \quad \mbox{in } \R \times \R_{+}, \nonumber \\ u(0, x) &=& u_{0}(x) \quad \mbox{in } \R, \label{0.1} \end{eqnarray} where $H$ is the Heaviside function and $f$ and $g$ are smooth with the assumptions that either $f$ is convex and $g$ is concave or $f$ is concave and $g$ is convex. The existence of a weak solution of (\ref{eq1}) is proved by showing that upwind finite difference schemes of Godunov and Enquist--Osher type converge to a weak solution. Uniqueness follows from a Kruzkhov-type entropy condition. We also provide explicit solutions to the Riemann problem for (\ref{eq1}). At the level of numerics, we give easy-to-implement numerical schemes of Godunov and Enquist--Osher type. The central feature of this paper is the modification of the singular mapping technique (the main analytical tool for these types of equations) which allows us to show that the numerical schemes converge. Equations of type (\ref{eq1}) with the above hypothesis on the flux may occur when considering the following scalar conservation law with discontinuous flux: \begin{equation} \label{eq2} \begin{array}{r@{\;}l} u_t + (k (x) f (u))_x &= 0, \\ u (0, x) &= u_0 (x), \end{array} \end{equation} with $f$ convex and $k$ of indefinite sign. [ABSTRACT FROM AUTHOR]

This paper provides a theoretical analysis of a higher-order, FFT-based integral equation method introduced recently [IEEE Trans. Antennas and Propagation, 48 (2000), pp. 1862-1864] for the evaluation of transverse electric-polarized electromagnetic scattering from a bounded, penetrable inhomogeneity in two-dimensional space. Roughly speaking, this method is based on Fourier smoothing of the integral operator and the refractive index n (x). Here we prove that the solution of the resulting integral equation approximates the solution of the exact integral equation with higher-order accuracy, even when n (x) is a discontinuous function-as suggested by the numerical experiments contained in the paper mentioned above. In detail, we relate the convergence rates of the computed interior and exterior fields to the regularity of the scatterer, and we demonstrate, with a few numerical examples, that the predicted convergence rates are achieved in practice. [ABSTRACT FROM AUTHOR]

This is the third part of a series of papers on least-squares Galerkin methods for parabolic initial-boundary value problems. These methods are based on the minimization of a least-squares functional for an equivalent first-order system over space and time with respect to suitable discrete spaces. This paper presents the derivation and analysis of one-step methods for semidiscretization in time from least-squares principles for semilinear parabolic problems. One of the most important features of the least-squares methodology is a built-in a posteriori estimate for the approximation error. For the presentation in this paper, we focus our attention on the specific combination of piecewise linear, not necessarily continuous, functions in time with continuous piecewise linear for the flux and scalar variables, respectively. For the resulting method, a convergence result is shown for the scalar variable. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the numerical solution of certain matrix-valued PDEs. Such PDEs arise, for example, when constructing a Riemannian contraction metric for a dynamical system given by an autonomous ODE. We develop and analyze a new meshfree discretization scheme using kernel-based approximation spaces. However, since these approximation spaces have now to be matrix-valued, the kernels we need to use are fourth-order tensors. We will review and extend recent results on even more general reproducing kernel Hilbert spaces. We will then apply this general theory to solve a matrix-valued PDE and derive error estimates for the approximate solution. The paper ends with applications to typical examples from dynamical systems. [ABSTRACT FROM AUTHOR]

The inverse radiative transfer problem finds broad applications in medical imaging, atmospheric science, astronomy, and many other areas. This problem intends to recover optical properties, denoted as absorption and the scattering coefficient of the media, through source-measurement pairs. A typical computational approach is to form the inverse problem as a PDE-constraint optimization, with the minimizer being the to-be-recovered coefficients. The method is tested to be efficient in practice, but it lacks analytical justification: there is no guarantee of the existence or uniqueness of the minimizer, and the error is hard to quantify. In this paper, we provide a different algorithm by levering the ideas from singular decomposition analysis. Our approach is to decompose the measurements into three components, two of which encode the information of the two coefficients, respectively. We then split the optimization problem into two subproblems and use those two components to recover the absorption and scattering coefficients separately. In this regard, we prove the well-posedness of the new optimization, and the error could be quantified with better precision. In the end, we incorporate the diffusive scaling and show that the error is harder to control in the diffusive limit. [ABSTRACT FROM AUTHOR]

We develop a unfied and easy to use framework to study robust fully discrete numerical methods for nonlinear degenerate di ffusion equations ∂u-L[φ(u)] = f(x; t) in ℝN×(0; T); where L is a general symmetric Lévy-type diffusion operator. Included are both local and nonlocal problems with, e.g., L = Δ or L = -(-Δ) ff2, ff ϵ (0; 2), and porous medium, fast diffusion, and Stefan-type nonlinearities φ . By robust methods we mean that they converge even for nonsmooth solutions and under very weak assumptions on the data. We show that they are Lp-stable for p ϵ[1,∞], compact, and convergent in C([0; T];Lploc(ℝN)) for p 2 [1,∞). The first part of this project is given in [F. del Teso, J. Endal, and E. R. Jakobsen, preprint, arXiv:1801.07148v1 [math.NA], 2018] and contains the unified and easy to use theoretical framework. This paper is devoted to schemes and testing. We study many different problems and many different concrete discretizations, proving that the results of Part I apply and testing the schemes numerically. Our examples include fractional diffusions of different orders and Stefan problems, porous medium, and fast diffusion nonlinearities. Most of the convergence results and many schemes are completely new for nonlocal versions of the equation, including results on high order methods, the powers of the discrete Laplacian method, and discretizations of fast diffusions. Some of the results and schemes are new even for linear and local problems. [ABSTRACT FROM AUTHOR]

Numerical schemes provably preserving the positivity of density and pressure are highly desirable for ideal magnetohydrodynamics (MHD), but the rigorous positivity-preserving (PP) analysis remains challenging. The difficulties mainly arise from the intrinsic complexity of the MHD equations as well as the indeterminate relation between the PP property and the divergence-free condition on the magnetic field. This paper presents the first rigorous PP analysis of conservative schemes with the Lax--Friedrichs (LF) flux for 1D and multidimensional ideal MHD. The significant innovation is the discovery of the theoretical connection between the PP property and a discrete divergence-free (DDF) condition. This connection is established through the generalized LF splitting properties, which are alternatives to the usually expected LF splitting property that does not hold for ideal MHD. The generalized LF splitting properties involve a number of admissible states strongly coupled by the DDF condition, making their derivation very difficult. We derive these properties via a novel equivalent form of the admissible state set and an important inequality, which is skillfully constructed by technical estimates. Rigorous PP analysis is then presented for finite volume and discontinuous Galerkin schemes with the LF flux on uniform Cartesian meshes. In the 1D case, the PP property is proved for the first-order scheme with proper numerical viscosity, and also for arbitrarily high-order schemes under conditions accessible by a PP limiter. In the 2D case, we show that the DDF condition is necessary and crucial for achieving the PP property. It is observed that even slightly violating the proposed DDF condition may cause failure to preserve the positivity of pressure. We prove that the 2D LF type scheme with proper numerical viscosity preserves both the positivity and the DDF condition. Sufficient conditions are derived for 2D PP high-order schemes, and extension to 3D is discussed. Numerical examples provided in the supplementary material further confirm the theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of computing the effective diffusivity for a particle moving in chaotic and stochastic flows. In addition, we numerically investigate the residual diffusion phenomenon in chaotic advection. The residual diffusion refers to the nonzero effective (homogenized) diffusion in the limit of zero molecular diffusion as a result of chaotic mixing of the streamlines. In this limit, traditional numerical methods typically fail since the solutions of the advection-diffusion equations develop sharp gradients. Instead of solving the Fokker-Planck equation in the Eulerian formulation, we compute the motion of particles in the Lagrangian formulation, which is modeled by stochastic differential equations (SDEs). We propose an effective numerical integrator based on a splitting method to solve the corresponding SDEs in which the deterministic subproblem is symplectic preserving while the random subproblem can be viewed as a perturbation. We provide rigorous error analysis for the new numerical integrator using the backward error analysis technique and show that our method outperforms standard Euler-based integrators. Numerical results are presented to demonstrate the accuracy and efficiency of the proposed method for several typical chaotic and stochastic flow problems of physical interest. The existence of residual diffusivity for these flow problems is also investigated. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the damped stochastic nonlinear Schrödinger (NLS) equation with multiplicative noise and its splitting-based approximation. When the damped effect is large enough, we prove that the solutions of both the damped stochastic NLS equation and the splitting scheme are exponentially stable and possess some exponential integrability. These properties show that the strong order of the scheme is 1 and independent of time. Additionally, we analyze the regularity of the Kolmogorov equation with respect to the stochastic NLS equation. As a consequence, the weak order of the scheme is shown to be 1 and independent of time. [ABSTRACT FROM AUTHOR]

In the literature, error bound conditions have been widely used to study the linear convergence rates of various first-order algorithms. Most of the literature focuses on how to ensure these error bound conditions, usually posing numerous assumptions or special structures on the model under discussion. In this paper, we focus on the alternating direction method of multipliers (ADMM) and show that the known error bound conditions for studying the ADMM's linear convergence rate can indeed be further weakened if the error bound is studied over the specific iterative sequence it generates. An error bound condition based on ADMM's iterations is thus proposed, and linear convergence under this condition is proved. Furthermore, taking advantage of a specific feature of ADMM's iterative scheme by which part of the perturbation is automatically zero, we propose the so-called partial error bound condition, which is weaker than known error bound conditions in the literature, and we derive the linear convergence rate of ADMM. We further show that this partial error bound condition is useful for interpreting the difference if the two primal variables are updated in different orders when implementing the ADMM. This has been empirically observed in the literature, yet no theory is known. [ABSTRACT FROM AUTHOR]

The Ensemble Kalman methodology in an inverse problems setting can be viewed as an iterative scheme, which is a weakly tamed discretization scheme for a certain stochastic differential equation (SDE). Assuming a suitable approximation result, dynamical properties of the SDE can be rigorously pulled back via the discrete scheme to the original Ensemble Kalman inversion. The results of this paper make a step towards closing the gap of the missing approximation result by proving a strong convergence result in a simplified model of a scalar SDE. We focus here on a toy model with similar properties to the one arising in the context of an Ensemble Kalman filter. The proposed model can be interpreted as a single particle filter for a linear map and thus forms the basis for further analysis. The difficulty in the analysis arises from the formally derived limiting SDE with nonglobally Lipschitz continuous nonlinearities both in the drift and in the diffusion. Here the standard Euler-Maruyama scheme might fail to provide a strongly convergent numerical scheme and taming is necessary. In contrast to the strong taming usually used, the method presented here provides a weaker form of taming. We present a strong convergence analysis by first proving convergence on a domain of high probability by using a cutoff or localization, which then leads, combined with bounds on moments for both the SDE and the numerical scheme, by a bootstrapping argument to strong convergence. [ABSTRACT FROM AUTHOR]

A theoretical analysis of a first-order div least-squares finite element method is presented. Our main interest is providing L2-norm error estimates for the primary function u and the flux σ = -효∇u. While there has been significant progress in the error estimates for the flux in L2-norm, these estimates have drawbacks, such as requiring smooth solutions or that the error estimate for ||σ - σh||0 is coupled with the error estimate for ||u - uh||1, where (uh, σh) is the least squares approximate solution for (u, σ = - 효 ∇u). In this paper, with the minimum regularity assumption u ∈ H1+α, α > 1/2, we separate the error estimate for ||σ - ||h||0 from ||u - uh||1 and establish that ||σ - σh||0 is bounded by the best approximation for a in the finite element space and ||u - uhh||0. Then, we proceed to obtain two new estimates for ||u - uh||0. The first estimate is useful to understand how the accuracy of ||u - uh||0 affects the accuracy of ||σ - σh||0 and the other sheds new light on the convergence behavior of ||u - uh||0. Our analysis does not require smooth solutions and the domain is allowed to be nonconvex. The resulting error estimates are valid for both smooth and low regularity solutions and show that optimal rates of convergence can be achieved by choosing proper finite element spaces such as the Raviart Thomas spaces for the flux σ. [ABSTRACT FROM AUTHOR]

This paper is concerned with delay-independent asymptotic stability of linear neutral delay differential-algebraic equations and linear multistep methods. We first give some sufficient conditions for the delay-independent asymptotic stability of these equations. Then we study and derive a sufficient and necessary condition for the delay-independent asymptotic stability of numerical solutions obtained by linear multistep methods combined with Lagrange interpolation. Finally, one numerical example is performed to confirm our theoretical result. [ABSTRACT FROM AUTHOR]

This paper takes another look at the convergence analysis of the Arnoldi procedure for solving non-Hermitian eigenvalue problems. Two main viewpoints are put in contrast. The first exploits the eigenbasis, when there is one, and relies on classical min-max approximation theory results. The second approach relies on the Schur factorization. Its aim is to link the convergence analysis of the Arnoldi process for eigenvalue problems to that of the generalized minimal residual iterations (GMRES), for which much is known. [ABSTRACT FROM AUTHOR]

In this paper, we study the relation between the error estimate of the bilinear interpolation on a general quadrilateral and the geometric characters of the quadrilateral. Some explicit bounds of the interpolation error are obtained based on some sharp estimates of the integral over 1/∣J∣p-1 for 1 ≤ p≤∞ on the reference element, where J is the Jacobian of the nonaffine mapping. This allows us to introduce weak geometric conditions (depending on p) leading to interpolation error estimates in the W1,p norm, for any p ϵ [1,∞), which can be regarded as a generalization of the regular decomposition property (RDP) condition introduced in [G. Acosta and R. G. Durán, SIAM J. Numer. Anal., 38 (2000), pp. 1073-1088] for p = 2 and new RDP conditions (NRDP) for p ≠ 2. We avoid the use of the reference family elements, which allows us to extend the results to a larger class of elements and to introduce the NRDP condition in a more unified way. As far as we know, the mesh condition presented in this paper is weaker than any other mesh conditions proposed in the literature for any p with 1 ≤ p≤∞. [ABSTRACT FROM AUTHOR]

In this paper, we perform an a posteriori error analysis of a multiscale operator decomposition finite element method for the solution of a system of coupled elliptic problems. The goal is to compute accurate error estimates that account for the effects arising from multiscale discretization via operator decomposition. Our approach to error estimation is based on a well-known a posteriori analysis involving variational analysis, residuals, and the generalized Green's function. Our method utilizes adjoint problems to deal with several new features arising from the multiscale operator decomposition. In part I of this paper, we focus on the propagation of errors arising from the solution of one component to another and the transfer of information between different representations of solution components. We also devise an adaptive discretization strategy based on the error estimates that specifically controls the effects arising from operator decomposition. In part II of this paper, we address issues related to the iterative solution of a fully coupled nonlinear system. [ABSTRACT FROM AUTHOR]

The stress-displacement-pressure formulation of the elasticity problem may suffer from two types of numerical instabilities related to the finite element interpolation of the unknowns. The first is the classical pressure instability that occurs when the solid is incompressible, whereas the second is the lack of stability in the stresses. To overcome these instabilities, there are two options. The first is to use different interpolation for all the unknowns satisfying two inf-sup conditions. Whereas there are several displacement-pressure interpolations that render the pressure stable, less possibilities are known for the stress interpolation. The second option is to use a stabilized finite element formulation instead of the plain Galerkin approach. If this formulation is properly designed, it is possible to use arbitrary interpolation for all the unknowns. The purpose of this paper is precisely to present one of such formulations. In particular, it is based on the decomposition of the unknowns into their finite element component and a subscale, which will be approximated and whose goal is to yield a stable formulation. A singular feature of the method to be presented is that the subscales will be considered orthogonal to the finite element space. We describe the design of the formulation and present the results of its numerical analysis. [ABSTRACT FROM AUTHOR]

In this paper, the frequency domain-based numerical methods for simulation of fractional order systems are studied in the sense of stability preservation. First, the stability boundary curve is exactly determined for these methods. Then, this boundary is analyzed and compared with an accurate (ideal) boundary in different frequency ranges. Also, the critical regions in which the stability does not preserve are determined. Finally, the analytical achievements are confirmed via some numerical illustrations. [ABSTRACT FROM AUTHOR]

In this paper we propose and analyze a new, fast method for the numerical solution of time domain boundary integral formulations of the wave equation. We employ Lubich's convolution quadrature method for the time discretization and a Galerkin boundary element method for the spatial discretization. The coefficient matrix of the arising system of linear equations is a triangular block Toeplitz matrix. Possible choices for solving the linear system arising from the above discretization include the use of fast Fourier transform (FFT) techniques and the use of data-sparse approximations. By using FFT techniques, the computational complexity can be reduced substantially while the storage cost remains unchanged and is, typically, high. Using data-sparse approximations, the gain is reversed; i.e., the computational cost is (approximately) unchanged while the storage cost is substantially reduced. The method proposed in this paper combines the advantages of these two approaches. First, the discrete convolution (related to the block Toeplitz system) is transformed into the (discrete) Fourier image, thereby arriving at a decoupled system of discretized Helmholtz equations with complex wave numbers. A fast data-sparse (e.g., fast multipole or panel-clustering) method can then be applied to the transformed system. Additionally, significant savings can be achieved if the boundary data are smooth and time-limited. In this case the right-hand sides of many of the Helmholtz problems are almost zero, and hence can be disregarded. Finally, the proposed method is inherently parallel. We analyze the stability and convergence of these methods, thereby deriving the choice of parameters that preserves the convergence rates of the unperturbed convolution quadrature. We also present numerical results which illustrate the predicted convergence behavior. [ABSTRACT FROM AUTHOR]

In this paper, we consider the singularly perturbed reaction-diffusion problem in one and two dimensions. The boundary value problem is decomposed into a first-order system to which a suitable weighted least-squares formulation is proposed. A robust, stable, and efficient approach is developed based on local discontinuous Galerkin (LDG) discretization for the weak form. Uniform error estimates are derived. Numerical examples are presented to illustrate the method and the theoretical results. Comparison studies are made between the proposed method and other methods. [ABSTRACT FROM AUTHOR]

The paper concerns numerical algorithms for solving the Beltrami equation fz¯(z) = μ(z)fz(z) for a compactly supported μ. First, we study an efficient algorithm that has been proposed in [P. Daripa, J. Comput. Phys., 106 (1993), pp. 355-365] and [P. Daripa and D. Mashat, Numer. Algorithms, 18 (1998), pp. 133-157] and present its rigorous justification. We then propose a different scheme for solving the Beltrami equation which has a comparable speed and accuracy, but has the virtue of easier implementation by avoiding the use of the Hilbert transform. The present paper can also be viewed as a prologue to one important application of the Beltrami equation: it provides a detailed description of the algorithm that has been used in [D. Gaidashev, Nonlinearity, 20 (1998), pp. 713-741] and [D. Gaidashev and M. Yampolsky, Experiment. Math., 16 (2007), pp. 215-226] to address an important issue in complex dynamics-conjectural universality for Siegel disks. [ABSTRACT FROM AUTHOR]

In this paper, we develop, analyze, and test a local discontinuous Galerkin (LDG) method for solving the Camassa-Holm equation which contains nonlinear high-order derivatives. The LDG method has the flexibility for arbitrary h and p adaptivity. We prove the L2 stability for general solutions and give a detailed error estimate for smooth solutions, and provide numerical simulation results for different types of solutions of the nonlinear Camassa-Holm equation to illustrate the accuracy and capability of the LDG method. [ABSTRACT FROM AUTHOR]

In this paper, we analyze convergence rates of wavelet schemes for time-dependent convection-reaction equations within the framework of the Eulerian--Lagrangian localized adjoint method (ELLAM). Under certain minimal assumptions that guarantee $ H^1 $-regularity of exact solutions, we show that a generic ELLAM scheme has a convergence rate $ \mathcal{O}(h/\sqrt{\Delta t} + \Delta t) $ in $ L^2 $-norm. Then, applying the theory of operator interpolation, we obtain error estimates for initial data with even lower regularity. Namely, it is shown that the error of such a scheme is $ \mathcal{O}((h/\sqrt{\Delta t})^\theta + (\Delta t)^\theta) $ for initial data in a Besov space $ \displaystyle B^\theta_{2,q} (0 < \theta < 1, 0 < q <= infinity) $. The error estimates are {a priori} and optimal in some cases. Numerical experiments using orthogonal wavelets are presented to illustrate the theoretical estimates. [ABSTRACT FROM AUTHOR]

The aim of this work is to solve hyperbolic conservation laws by means of a finite volume method for both spatial and time discretization. We extend the ideas developed in [X.-D. Liu and S. Osher, SIAM J. Numer. Anal., 33 (1996), pp. 760--779; X.-D. Liu and E. Tadmor, Numer. Math., 79 (1998), pp. 397--425] to fourth-order upwind and central schemes. In order to do this, once we know the cell-averages of the solution, $\overline {u}_j ^n$, in cells $I_{j}$ at time $T=t^n$, we define a new three-degree reconstruction polynomial that in each cell, $I_{j}$, presents the same shape as the cell-averages $\{ {\overline {u}_{j-1} ^n,\overline {u}_j ^n,\overline {u}_{j+1} ^n}\}$. By combining this reconstruction with the nonoscillatory property and the maximum principle requirement described in [X.-D. Liu and S. Osher, SIAM J. Numer. Anal., 33 (1996), pp. 760--779] we obtain a fourth-order scheme that satisfies the total variation bounded (TVB) property. Extension to systems is carried out by componentwise application of the scalar framework. Numerical experiments confirm the order of the schemes presented in this paper and their nonoscillatory behavior in different test problems. [ABSTRACT FROM AUTHOR]

Local mesh-refining algorithms known from adaptive finite element methods are adopted for locally conservative and monotone finite volume discretizations of boundary value problems for steady-state convection-diffusion-reaction equations. The paper establishes residual-type explicit error estimators and averaging techniques for a posteriori finite volume error control with and without upwind in global H1- and L2-norms. Reliability and efficiency are verified theoretically and confirmed empirically with experimental support for the superiority of the suggested adaptive mesh-refining algorithms over uniform mesh refining. A discussion of adaptive computations in the simulation of contaminant concentration in a nonhomogeneous water reservoir concludes the paper. [ABSTRACT FROM AUTHOR]

In this paper we establish an explicit asymptotic formula for the steady state voltage perturbations caused by closely spaced small conductivity inhomogeneities. Based on this new formula we design a very effective numerical method to identify the location and some geometric features of these inhomogeneities from a finite number of boundary measurements. The viability of our approach is documented by numerical examples. [ABSTRACT FROM AUTHOR]

We study necessary and sufficient conditions that a nonsingular matrix A can be B-orthogonally reduced to upper Hessenberg form with small bandwidth. By this we mean the existence of a decomposition AV=VH, where H is upper Hessenberg with few nonzero bands, and the columns of V are orthogonal in an inner product generated by a hermitian positive definite matrix B. The classical example for such a decomposition is the matrix tridiagonalization performed by the hermitian Lanczos algorithm, also called the orthogonal reduction to tridiagonal form. Does there exist such a decomposition when A is nonhermitian? In this paper we completely answer this question. The related (but not equivalent) question of necessary and sufficient conditions on A for the existence of short-term recurrences for computing B-orthogonal Krylov subspace bases was completely answered by the fundamental theorem of Faber and Manteuffel [SIAM J. Numer. Anal.}, 21 (1984), pp. 352--362]. We give a detailed analysis of B-normality, the central condition in both the Faber--Manteuffel theorem and our main theorem, and show how the two theorems are related. Our approach uses only elementary linear algebra tools. We thereby provide new insights into the principles behind Krylov subspace methods, that are not provided when more sophisticated tools are employed. [ABSTRACT FROM AUTHOR]

A new fully variational approach is studied for elliptic grid generation (EGG). It is based on a general algorithm developed in a companion paper [A. L. Codd, T. A. Manteuffel, and S. F. McCormick, SIAM I Numer. Anal., 41 (2003), pp. 2197-2209] that involves using Newton's method to linearize an appropriate equivalent first-order system, first-order system least squares (FOSLS) to formulate and discretize the Newton step, and algebraic multigrid (AMG) to solve the resulting matrix equation. The approach is coupled with nested iteration to provide an accurate initial guess for finer levels using coarse-level computation. The present paper verifies the assumptions of the companion work and confirms the overall efficiency of the scheme with numerical experiments. [ABSTRACT FROM AUTHOR]

Electromagnetic waveguides in integrated optics are propagation structures which are invariant under translation in one space direction and whose cross section is a local perturbation of a stratified medium. In this paper, we propose a new method for computing the guided modes of such devices under the weak guiding assumption. The method results from a combination of analytical techniques which take into account the unbounded and stratified character of the propagation medium so that numerical computations can be reduced to a neighborhood of the perturbation. [ABSTRACT FROM AUTHOR]

This paper is devoted to a study of the numerical solution of elliptic hemivariationalinequalities with or without convex constraints by the nite element method. For a general family of elliptic hemivariational inequalities that facilitates error analysis for numerical solutions. the solution existence and uniqueness are proved. The Galerkin approximation of the general elliptic hemivariational inequality is shown to converge. and Cea's inequality is derived for error estimation. For various elliptic hemivariational inequalities arising in contact mechanics, we provide error estimates of their numerical solutions, which are of optimal order for the linearnite element method, under appropriate solution regularity assumptions. Numerical examples are reported on using linear elements to solve sample contact problems, and the simulation results are in good agreement with the theoretically predicted linear convergence. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we introduce an overlapping mortar finite element method for solving two-dimensional elliptic problems discretized on overlapping nonmatching grids. We prove an optimal error bound and estimate the condition numbers of certain overlapping Schwarz preconditioned systems for the two-subdomain case. We show that the error bound is independent of the size of the overlap and the ratio of the mesh parameters. In the second part, we introduce three additive Schwarz preconditioned conjugate gradient algorithms based on the trivial and harmonic extensions. We provide estimates for the spectral bounds on the condition numbers of the preconditioned operators. We show that although the error bound is independent of the size of the overlap, the condition number does depend on it. Numerical examples are presented to support our theory. [ABSTRACT FROM AUTHOR]

We present in this paper numerical simulations of reactive flows interacting with shock waves. We argue that spectral methods are suitable for these problems and review the recent developments in spectral methods that have made them a powerful numerical tool appropriate for long-term integrations of complicated flows, even in the presence of shock waves. A spectral code is described in detail, and the theory that leads to each of its components is explained. Results of interactions of hydrogen jets with shock waves are presented and analyzed, and comparisons with ENO finite difference schemes are carried out. [ABSTRACT FROM AUTHOR]

This paper develops a least-squares approach to the solution of the incompressible Navier­Stokes equations in primitive variables. As with our earlier work on Stokes equations, we recast the Navier­Stokes equations as a first-order system by introducing a velocity-flux variable and associated curl and trace equations. We show that a least-squares principle based on L2 norms applied to this system yields optimal discretization error estimates in the H1 norm in each variable, including the velocity flux. An analogous principle based on the use of an H-1 norm for the reduced system (with no curl or trace constraints) is shown to yield similar estimates, but now in the L2 norm for velocity-flux and pressure. Although the H-1 least-squares principle does not allow practical implementation, these results are critical to the analysis of a practical least-squares method for the reduced system based on a discrete equivalent of the negative norm. A practical method of this type is the subject of a companion paper. Finally, we establish optimal multigrid convergence estimates for the algebraic system resulting from the L2 norm approach. [ABSTRACT FROM AUTHOR]

New classes of stochastic differential equations can now be studied using rough path theory (see, e.g., [T. J. Lyons, M. Caruana, and T. Lévy, Differential Equations Driven by Rough Paths, Springer, Berlin, 2007] or [P. K. Friz and M. Hairer, A Course on Rough Paths, Universitext, Springer, Cham, 2014]). In this paper we investigate, from a numerical analysis point of view, stochastic differential equations driven by Gaussian noise in the aforementioned sense. Our focus lies on numerical implementations, and more speciffcally on the savings possible via multilevel methods. Our analysis relies on a subtle combination of pathwise estimates, Gaussian concentration, and multilevel ideas. Numerical examples are given which both illustrate and confirm our findings. [ABSTRACT FROM AUTHOR]

Evans function computation is a useful tool in the study of asymptotically constant coefficient linear operators such as those found in the investigation of traveling wave stability. The roots of this analytic function correspond to the eigenvalues of the operator, and by employing both winding number and root-finding methods, one can demonstrate spectral stability and determine the precise location of the eigenvalues up to numerical tolerance. It is often desirable to track these eigenvalues as parameters vary in a system, particularly as they may cross into the right half of the complex plane, thus signaling the onset of instability. In this paper, we present a numerical method to track these eigenvalues using continuation to follow the roots of the Evans function instead of using winding number and root-finding techniques, therefore saving time and effort. We then consider some examples. [ABSTRACT FROM AUTHOR]

Preconditioned gradient iterations for very large eigenvalue problems are efficient solvers with growing popularity. However, only for the simplest preconditioned eigensolver, namely the preconditioned gradient iteration (or preconditioned inverse iteration) with fixed step size, are sharp nonasymptotic convergence estimates known. These estimates require a properly scaled pre-conditioner. In this paper a new sharp convergence estimate is derived for the preconditioned steepest descent iteration which combines the preconditioned gradient iteration with the Rayleigh--Ritz procedure for optimal line search convergence acceleration. The new estimate always improves that of the fixed-step-size iteration. The practical importance of this new estimate is that arbitrarily scaled preconditioners can be used. The Rayleigh--Ritz procedure implicitly computes the optimal scaling constant. [ABSTRACT FROM AUTHOR]

We prove that front tracking approximations to scalar conservation laws with convex fluxes converge at a rate of Δ x2 in the 1-Wasserstein distance W1. Assuming positive initial data, we also show that the approximations converge at a rate of Δ x in the ∞ -Wasserstein distance W∞ . Moreover, from a simple interpolation inequality between W1 and W∞ we obtain convergence rates in all the p-Wasserstein distances: Δ x1+1/p, p ϵ [1,∞ ]. [ABSTRACT FROM AUTHOR]

In this paper, a three-level balancing domain decomposition by constraints (BDDC) algorithm is developed for the solutions of large sparse algebraic linear systems arising from the mortar discretization of elliptic boundary value problems. The mortar discretization is considered on geometrically nonconforming subdomain partitions. In two-level BDDC algorithms, the coarse problem needs to be solved exactly. However, its size will increase with the increase of the number of the subdomains. To overcome this limitation, the three-level algorithm solves the coarse problem inexactly while a good rate of convergence is maintained. This is an extension of previous work: the three-level BDDC algorithms for standard finite element discretization. Estimates of the condition numbers are provided for the three-level BDDC method, and numerical experiments are also discussed. [ABSTRACT FROM AUTHOR]

The Malliavin-Thalmaier formula was introduced in [P. Malliavin and A. Thalmaier, Stochastic Calculus of Variations in Mathematical Finance, Springer-Verlag, Berlin, 2006] as an alternative expression for the density of a multivariate smooth random variable in Wiener space. In comparison with classical integration by parts formulae, this alternative formulation requires the application of the integration by parts formula only once to obtain an expression that can be simulated. Therefore, this expression is free from the curse of dimensionality. Unfortunately, when this formula is applied directly in computer simulation, it exhibits unstable behavior. We propose an approximation to the Malliavin-Thalmaier formula in the spirit of the theory of kernel density estimation to solve this problem. In the first part of this paper, we obtain a central limit theorem for the estimation error. And in the latter part, we apply the Malliavin-Thalmaier formula for the calculation of Greeks in finance. [ABSTRACT FROM AUTHOR]

An accuracy-enhancing postprocessing technique for finite-element discretizations of the Navier-Stokes equations is analyzed. The technique had been previously analyzed only for semidiscretizations, and fully discrete methods are addressed in the present paper. We show that the increased spatial accuracy of the postprocessing procedure is not affected by the errors arising from any convergent time-stepping procedure. Further refined bounds are obtained when the timestepping procedure is either the backward Euler method or the two-step backward differentiation formula. [ABSTRACT FROM AUTHOR]

This paper deals with superconvergence phenomena in general grids when projectionbased approximations are used for solving Fredholm integral equations of the second kind with weakly singular kernels. Four variants of the Galerkin method are considered. They are the classical Galerkin method, the iterated Galerkin method, the Kantorovich method, and the iterated Kantorovich method. It is proved that the iterated Kantorovich approximation exhibits the best superconvergence rate if the right-hand side of the integral equation is nonsmooth. All error estimates are derived for an arbitrary grid without any uniformity or quasi-uniformity condition on it, and are formulated in terms of the data without any additional assumption on the solution. Numerical examples concern the equation governing transfer of photons in stellar atmospheres. The numerical results illustrate the fact that the error estimates proposed in the different theorems are quite sharp, and confirm the superiority of the iterated Kantorovich scheme. [ABSTRACT FROM AUTHOR]

In this paper, we present a rigorous numerical analysis for a bounded artificial viscosity model (τ = μδσa(δ∥∇su∥F )∇su) for the numerical simulation of turbulent flows. In practice, the commonly used Smagorinsky model (τ = (csδ)2∥∇su∥F ∇su) is overly dissipative and yields unphysical results. To date, several methods for "clipping" the Smagorinsky viscosity have proven useful in improving the physical characteristics of the simulated flow. However, such heuristic strategies strongly rely upon a priori knowledge of the flow regime. The bounded artificial viscosity model relies on a highly nonlinear, but monotone and smooth, semilinear elliptic form for the artificial viscosity. For this model, we have introduced a variational computational strategy, provided finite element error convergence estimates, and included several computational examples indicating its improvement on the overly diffusive Smagorinsky model. [ABSTRACT FROM AUTHOR]

A recent study [D. N. Arnold, D. Boffi, and R. S. Falk, SIAM J. Numer. Anal., 42 (2005), pp. 2429-2451] reveals that convergence of finite element methods using H(div , O)-compatible finite element spaces deteriorates on nonaffine quadrilateral grids. This phenomena is particularly troublesome for the lowest-order Raviart-Thomas elements, because it implies loss of convergence in some norms for finite element solutions of mixed and least-squares methods. In this paper we propose reformulation of finite element methods, based on the natural mimetic divergence operator [M. Shashkov, Conservative Finite Difference Methods on General Grids, CRC Press, Boca Raton, FL, 1996], which restores the order of convergence. Reformulations of mixed Galerkin and leastsquares methods for the Darcy equation illustrate our approach. We prove that reformulated methods converge optimally with respect to a norm involving the mimetic divergence operator. Furthermore, we prove that standard and reformulated versions of the mixed Galerkin method lead to identical linear systems, but the two versions of the least-squares method are veritably different. The surprising conclusion is that the degradation of convergence in the mixed method on nonaffine quadrilateral grids is superficial, and that the lowest-order Raviart-Thomas elements are safe to use in this method. However, the breakdown in the least-squares method is real, and there one should use our proposed reformulation. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to construct universal, auto-adaptive, localized, linear, polynomial (-valued) operators based on scattered data on the (hyper) sphere Sq (q ≥ 2). The approximation and localization properties of our operators are studied theoretically in deterministic as well as probabilistic settings. Numerical experiments are presented to demonstrate their superiority over traditional least squares and discrete Fourier projection polynomial approximations. An essential ingredient in our construction is the construction of quadrature formulas based on scattered data, exact for integrating spherical polynomials of (moderately) high degree. Our formulas are based on scattered sites; i.e., in contrast to such well-known formulas as Driscoll-Healy formulas, we need not choose the location of the sites in any particular manner. While the previous attempts to construct such formulas have yielded formulas exact for spherical polynomials of degree at most 18, we are able to construct formulas exact for spherical polynomials of degree 178. [ABSTRACT FROM AUTHOR]

We develop a family of new interior penalty discontinuous Galerkin methods for the Keller-Segel chemotaxis model. This model is described by a system of two nonlinear PDEs: a convection-diffusion equation for the cell density coupled with a reaction-diffusion equation for the chemoattractant concentration. It has been recently shown that the convective part of this system is of a mixed hyperbolic-elliptic-type, which may cause severe instabilities when the studied system is solved by straightforward numerical methods. Therefore, the first step in the derivation of our new methods is made by introducing the new variable for the gradient of the chemoattractant concentration and by reformulating the original Keller-Segel model in the form of a convection-diffusionreaction system with a hyperbolic convective part. We then design interior penalty discontinuous Galerkin methods for the rewritten Keller-Segel system. Our methods employ the central-upwind numerical fluxes, originally developed in the context of finite-volume methods for hyperbolic systems of conservation laws. In this paper, we consider Cartesian grids and prove error estimates for the proposed high-order discontinuous Galerkin methods. Our proof is valid for pre-blow-up times since we assume boundedness of the exact solution. We also show that the blow-up time of the exact solution is bounded from above by the blow-up time of our numerical solution. In the numerical tests presented below, we demonstrate that the obtained numerical solutions have no negative values and are oscillation-free, even though no slope-limiting technique has been implemented. [ABSTRACT FROM AUTHOR]

The fast marching method (FMM) has proved to be a very efficient algorithm for solving the isotropic Eikonal equation. Because it is a minor modification of Dijkstra's algorithm for finding the shortest path through a discrete graph, FMM is also easy to implement. In this paper we describe a new class of Hamilton-Jacobi (HJ) PDEs with axis-aligned anisotropy which satisfy a causality condition for standard finite-difference schemes on orthogonal grids and can hence be solved using the FMM; the only modification required to the algorithm is in the local update equation for a node. This class of HJ PDEs has applications in anelliptic wave propagation and robotic path planning, and brief examples are included. Since our class of HJ PDEs and grids permit asymmetries, we also examine some methods of improving the efficiency of the local update that do not require symmetric grids and PDEs. Finally, we include explicit update formulas for variations of the Eikonal equation that use the Manhattan, Euclidean, and infinity norms on orthogonal grids of arbitrary dimension and with variable node spacing. [ABSTRACT FROM AUTHOR]

In recent years, implicit stochastic Runge-Kutta (SRK) methods have been developed both for strong and weak approximations. For these methods, the stage values are only given implicitly. However, in practice these implicit equations are solved by iterative schemes such as simple iteration, modified Newton iteration or full Newton iteration. We employ a unifying approach for the construction of stochastic B-series which is valid both for Itô- and Stratonovich-stochastic differential equations (SDEs) and applicable both for weak and strong convergence to analyze the order of the iterated Runge-Kutta method. Moreover, the analytical techniques applied in this paper can be of use in many other similar contexts. [ABSTRACT FROM AUTHOR]

In this paper, proper orthogonal decomposition (POD) is used for model reduction of mixed finite element (MFE) for the nonstationary Navier-Stokes equations and error estimates between a reference solution and the POD solution of reduced MFE formulation are derived. The basic idea of this reduction technique is that ensembles of data are first compiled from transient solutions computed equation system derived with the usual MFE method for the nonstationary Navier-Stokes equations or from physics system trajectories by drawing samples of experiments and interpolation (or data assimilation), and then the basis functions of the usual MFE method are substituted with the POD basis functions reconstructed by the elements of the ensemble to derive the POD-reduced MFE formulation for the nonstationary Navier-Stokes equations. It is shown by considering numerical simulation results obtained for the illustrating example of cavity flows that the error between POD solution of reduced MFE formulation and the reference solution is consistent with theoretical results. Moreover, it is also shown that this result validates the feasibility and efficiency of the POD method. [ABSTRACT FROM AUTHOR]

In this paper, we consider convergence of classical high-order Godunov-type schemes towards entropy solutions for scalar conservation laws. It is well known that sufficient conditions for such convergence include total variation boundedness of the reconstruction and cell or wavewise entropy inequalities. We prove that under large time steps, we only need total variation boundedness of the reconstruction to guarantee such convergence. We discuss high-order total variation bounded reconstructions to fulfill this sufficient condition and provide numerical examples on one-dimensional convex conservation laws to assess the performance of such large time step Godunov-type methods. To demonstrate the generality of this approach, we also prove convergence and give numerical examples for a large time step Godunov-like scheme involving Sanders' third-order total variation diminishing reconstruction using both cell averages and point values at cell boundaries. [ABSTRACT FROM AUTHOR]