Search

We present a family of high-order trapezoidal rule-based quadratures for a class of singular integrals, where the integrand has a point singularity. The singular part of the integrand is expanded in a Taylor series involving terms of increasing smoothness. The quadratures are based on the trapezoidal rule, with the quadrature weights for Cartesian nodes close to the singularity judiciously corrected based on the expansion. High-order accuracy can be achieved by utilizing a sufficient number of correction nodes around the singularity to approximate the terms in the series expansion. The derived quadratures are applied to the implicit boundary integral formulation of surface integrals involving the Laplace layer kernels. [ABSTRACT FROM AUTHOR]

In this work we show an error estimate for a first order Gaussian beam at a fold caustic, approximating time-harmonic waves governed by the Helmholtz equation. For the caustic that we study the exact solution can be constructed using Airy functions and there are explicit formulae for the Gaussian beam parameters. Via precise comparisons we show that the pointwise error on the caustic is of the order O (k − 5 / 6) where k is the wave number in Helmholtz. [ABSTRACT FROM AUTHOR]

In this paper, we consider several possible ways to set up Heterogeneous Multiscale Methods for the Landau--Lifshitz equation with a highly oscillatory diffusion coefficient, which can be seen as a means to modeling rapidly varying ferromagnetic materials. We then prove estimates for the errors introduced when approximating the relevant quantity in each of the models given a periodic problem, using averaging in time and space of the solution to a corresponding micro problem. In our setup, the Landau--Lifshitz equation with a highly oscillatory coefficient is chosen as the micro problem for all models. We then show that the averaging errors only depend on\varepsilon and the size of the microscopic oscillations, as well as the size of the averaging domain in time and space and the choice of averaging kernels. [ABSTRACT FROM AUTHOR]

The implicit boundary integral method (IBIM) provides a framework to construct quadrature rules on regular lattices for integrals over irregular domain boundaries. This work provides a systematic error analysis for IBIMs on uniform Cartesian grids for boundaries with different degrees of regularity. First, it is shown that the quadrature error gains an additional order of d - 1 2 from the curvature for a strongly convex smooth boundary due to the “randomness” in the signed distances. This gain is discounted for degenerated convex surfaces. Then the extension of error estimate to general boundaries under some special circumstances is considered, including how quadrature error depends on the boundary’s local geometry relative to the underlying grid. Bounds on the variance of the quadrature error under random shifts and rotations of the lattices are also derived. [ABSTRACT FROM AUTHOR]

This paper concerns the analysis of a multiscale method for wave propagation problems in microscopically nonhomogeneous media. A direct numerical approximation of such problems is prohibitively expensive as it requires resolving the microscopic variations over a much larger physical domain of interest. The heterogeneous multiscale method (HMM) is an efficient framework to approximate the solutions of multiscale problems. In the HMM, one assumes an incomplete macroscopic model which is coupled to a known but expensive microscopic model. The micromodel is solved only locally to upscale the parameter values which are missing in the macro- model. The resulting macroscopic model can then be solved at a cost independent of the small scales in the problem. In general, the accuracy of the HMM is related to how good the upscaling step approximates the right macroscopic quantities. The analysis of the method that we consider here was previously addressed only in purely periodic media, although the method itself is numerically shown to be applicable to more general settings. In the present study, we consider a more realistic setting by assuming a locally periodic medium where slow and fast variations are allowed at the same time. We then prove that the HMM captures the right macroscopic effects. The generality of the tools and ideas in the analysis allows us to establish convergence rates in a multidimensional setting. The theoretical findings here imply an improved convergence rate in one dimension, which also justifies the numerical observations from our earlier study. [ABSTRACT FROM AUTHOR]

In this paper, we present a fast time adaptive numerical method for interface tracking. The method uses an explicit multiresolution description of the interface, which is represented by wavelet vectors that correspond to the details of the interface on different scale levels. The complexity of standard numerical methods for interface tracking, where the interface is described by N marker points, is O ( N / Δ t ) , when a time step Δ t is used. The methods that we propose in this paper have O ( tol − 1 / p log ⁡ N + N log ⁡ N ) computational cost, at least for uniformly smooth problems, where tol is some given tolerance and p is the order of the time stepping method that is used for time advection of the interface. The adaptive method is robust in the sense that it can handle problems with both smooth and piecewise smooth interfaces (e.g. interfaces with corners) while keeping a low computational cost. We show numerical examples that verify these properties. [ABSTRACT FROM AUTHOR]

This paper concerns the cell-boundary error present in multiscale algorithms for elliptic homogenization problems. Typical multiscale methods have two essential components: a macro and a micro model. The micro model is used to upscale parameter values which are missing in the macro model. To solve the micro model, boundary conditions are required on the boundary of the microscopic domain. Imposing a naive boundary condition leads to O ( ε / η ) error in the computation, where ε is the size of the microscopic variations in the media and η is the size of the micro-domain. The removal of this error in modern multiscale algorithms still remains an important open problem. In this paper, we present a time-dependent approach which is general in terms of dimension. We provide a theorem which shows that we have arbitrarily high order convergence rates in terms of ε / η in the periodic setting. Additionally, we present numerical evidence showing that the method improves the O ( ε / η ) error to O ( ε ) in general non-periodic media. [ABSTRACT FROM AUTHOR]

We present a novel wavefront method based on Gaussian beams for computing high frequency wave propagation problems. Unlike standard geometrical optics, Gaussian beams compute the correct solution of the wave field also at caustics. The method tracks a front of two canonical beams with two particular initial values for width and curvature. In a fast post-processing step, from the canonical solutions we recreate any other Gaussian beam with arbitrary initial data on the initial front. This provides a simple mechanism to include a variety of optimization processes, including error minimization and beam width minimization, for a posteriori selection of optimal beam initial parameters. The performance of the method is illustrated with two numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a multiscale method developed under the heterogeneous multiscale method (HMM) framework for numerical approximation of multiscale wave propagation problems in periodic media. In particular, we are interested in the long time O(ε-2) wave propagation, where ε represents the size of the microscopic variations in the media. In large time scales, the solutions of multiscale wave equations exhibit O(1) dispersive effects which are not observed in short time scales. A typical HMM has two main components: a macromodel and a micromodel. The macromodel is incomplete and lacks a set of local data. In the setting of multiscale PDEs, one has to solve for the full oscillatory problem over local microscopic domains of size η = O(ε) to upscale the parameter values which are missing in the macroscopic model. In this paper, we prove that if the microproblems are consistent with the macroscopic solutions, the HMM approximates the unknown parameter values in the macromodel up to any desired order of accuracy in terms of ε/η. [ABSTRACT FROM AUTHOR]

• Surface integrals can be seen as volume integrals over a neighborhood of the surface. • Layer kernels in the volume integrals are singular along straight lines. • The trapezoidal rule applied to singular integrands can be improved via correction. • We develop corrected trapezoidal rule for 2D functions singular in one point. • We apply the new rule to each plane of the volume integrals of the layer potentials. We present new higher-order quadratures for a family of boundary integral operators re-derived using the approach introduced in Kublik et al. (2013) [7]. In this formulation, a boundary integral over a smooth, closed hypersurface is transformed into an equivalent volume integral defined in a sufficiently thin tubular neighborhood of the surface. The volumetric formulation makes it possible to use the simple trapezoidal rule on uniform Cartesian grids and relieves the need to use parameterization for developing quadrature. Consequently, typical point singularities in a layer potential extend along the surface's normal lines. We propose new higher-order corrections to the trapezoidal rule on the grid nodes around the singularities. This correction is based on local decompositions of the singularity and is dependent on the angle of approach to the singularity relative to the surface's principal curvature directions. The proposed decomposition, combined with the volumetric formulation, leads to a special quadrature error cancellation. [ABSTRACT FROM AUTHOR]

Gaussian beams are asymptotically valid high frequency solutions to hyperbolic partial differential equations, concentrated on a single curve through the physical domain. They can also be extended to some dispersive wave equations, such as the Schrödinger equation. Superpositions of Gaussian beams provide a powerful tool to generate more general high frequency solutions that are not necessarily concentrated on a single curve. This work is concerned with the accuracy of Gaussian beam superpositions in terms of the wavelength ε. We present a systematic construction of Gaussian beam superpositions for all strictly hyperbolic and Schrödinger equations subject to highly oscillatory initial data of the form AeiΦ/ε. Through a careful estimate of an oscillatory integral operator, we prove that the k-th order Gaussian beam superposition converges to the original wave field at a rate proportional to εk/2 in the appropriate norm dictated by the well-posedness estimate. In particular, we prove that the Gaussian beam superposition converges at this rate for the acoustic wave equation in the standard, ε-scaled, energy norm and for the Schrödinger equation in the L² norm. The obtained results are valid for any number of spatial dimensions and are unaffected by the presence of caustics. We present a numerical study of convergence for the constant coefficient acoustic wave equation in ℝ² to analyze the sharpness of the theoretical results. [ABSTRACT FROM AUTHOR]

We propose and analyze a fast method for computing the solution of the high frequency Helmholtz equation in a bounded one-dimensional domain with a variable wave speed function. The method is based on wave splitting. The Helmholtz equation is split into one-way wave equations with source functions which are solved iteratively for a given tolerance. The source functions depend on the wave speed function and on the solutions of the one-way wave equations from the previous iteration. The solution of the Helmholtz equation is then approximated by the sum of the one-way solutions at every iteration. To improve the computational cost, the source functions are thresholded and in the domain where they are equal to zero, the one-way wave equations are solved with geometrical optics with a computational cost independent of the frequency. Elsewhere, the equations are fully resolved with a Runge-Kutta method. We have been able to show rigorously in one dimension that the algorithm is convergent and that for fixed accuracy, the computational cost is asymptotically just $\mathcal {O}(\omega^{1/ p})$ for a pth order Runge-Kutta method, where ω is the frequency. Numerical experiments indicate that the growth rate of the computational cost is much slower than a direct method and can be close to the asymptotic rate. [ABSTRACT FROM AUTHOR]

We consider a class of finite Markov moment problems with an arbitrary number of positive and negative branches. We show criteria for the existence and uniqueness of solutions, and we characterize in detail the nonunique solution families. Moreover, we present a constructive algorithm to solve the moment problems numerically and prove that the algorithm computes the right solution. [ABSTRACT FROM AUTHOR]

We develop a new sparse spectral method, in which the fast Fourier transform (FFT) is replaced by RAℓSFA (randomized algorithm of sparse Fourier analysis); this is a sublinear randomized algorithm that takes time O(B logN) to recover a B-term Fourier representation for a signal of length N, where we assume B ≤ N. To illustrate its potential, we consider the parabolic homogenization problem with a characteristic fine scale size ε. For fixed tolerance the sparse method has a computational cost of O(|log ε|) per time step, whereas standard methods cost at least O(ε-1). We present a theoretical analysis as well as numerical results; they show the advantage of the new method in speed over the traditional spectral methods when ε is very small. We also show some ways to extend the methods to hyperbolic and elliptic problems. [ABSTRACT FROM AUTHOR]

Abstract: Creeping rays can give an important contribution to the solution of medium to high frequency scattering problems. They are generated at the shadow lines of the illuminated scatterer by grazing incident rays and propagate along geodesics on the scatterer surface, continuously shedding diffracted rays in their tangential direction. In this paper, we show how the ray propagation problem can be formulated as a partial differential equation (PDE) in a three-dimensional phase space. To solve the PDE we use a fast marching method. The PDE solution contains information about all possible creeping rays. This information includes the phase and amplitude of the field, which are extracted by a fast post-processing. Computationally, the cost of solving the PDE is less than tracing all rays individually by solving a system of ordinary differential equations. We consider an application to mono-static radar cross section problems where creeping rays from all illumination angles must be computed. The numerical results of the fast phase space method and a comparison with the results of ray tracing are presented. [Copyright &y& Elsevier]

Abstract: We expose in full detail a constructive procedure to invert the so-called ‘finite Markov moment problem’. The proofs rely on the general theory of Toeplitz matrices together with the classical Newton''s relations. To cite this article: L. Gosse, O. Runborg, C. R. Acad. Sci. Paris, Ser. I 341 (2005). [Copyright &y& Elsevier]

A multiresolution analysis of a curve is normal if each wavelet detail vector with respect to a certain subdivision scheme lies in the local normal direction. In this paper we study properties such as regularity, convergence, and stability of a normal multiresolution analysis. In particular, we show that these properties critically depend on the underlying subdivision scheme and that, in general, the convergence of normal multiresolution approximations equals the convergence of the underlying subdivision scheme. [ABSTRACT FROM AUTHOR]

Geometrical optics is a standard technique used for the approximation of high-frequency wave propagation. Computational methods based on partial differential equations instead of the traditional ray tracing have recently been applied to geometrical optics. These new methods have a number of advantages but typically exhibit difficulties with linear superposition of waves. In this paper we introduce a new partial differential technique based on the segment projection method in phase space. The superposition problem is perfectly resolved and so is the problem of computing amplitudes in the neighborhood of caustics. The computational complexity is of the same order as that of ray tracing. The new algorithm is described and a number of computational examples are given, including a simulation of waveguides. [Copyright &y& Elsevier]

A new iterative method, the WaveHoltz iteration, for solution of the Helmholtz equation is presented. WaveHoltz is a fixed point iteration that filters the solution to the solution of a wave equation with time periodic forcing and boundary data. The WaveHoltz iteration corresponds to a linear and coercive operator which, after discretization, can be recast as a positive definite linear system of equations. The solution to this system of equations approximates the Helmholtz solution and can be accelerated by Krylov subspace techniques. Analysis of the continuous and discrete cases is presented, as are numerical experiments. [ABSTRACT FROM AUTHOR]

We present a new computational approach for a class of large-scale nonlinear eigenvalue problems (NEPs) that are nonlinear in the eigenvalue. The contribution of this paper is twofold. We derive a new iterative algorithm for NEPs, the tensor infinite Arnoldi method (TIAR), which is applicable to a general class of NEPs, and we show how to specialize the algorithm to a specific NEP: the waveguide eigenvalue problem. The waveguide eigenvalue problem arises from a finite-element discretization of a partial differential equation used in the study waves propagating in a periodic medium. The algorithm is successfully applied to accurately solve benchmark problems as well as complicated waveguides. We study the complexity of the specialized algorithm with respect to the number of iterations m and the size of the problem n, both from a theoretical perspective and in practice. For the waveguide eigenvalue problem, we establish that the computationally dominating part of the algorithm has complexity O(nm² + √nm³). Hence, the asymptotic complexity of TIAR applied to the waveguide eigenvalue problem, for n → ∞, is the same as for Arnoldi's method for standard eigenvalue problems. [ABSTRACT FROM AUTHOR]

In this work we construct Gaussian beam approximations to solutions of the high frequency Helmholtz equation with a localized source. Under the assumption of nontrapping rays we show error estimates between the exact outgoing solution and Gaussian beams in terms of the wave number k, both for single beams and superposition of beams. The main result is that the relative local L² error in the beam approximations decay as k-N/2 independent of dimension and presence of caustics for Nth order beams. [ABSTRACT FROM AUTHOR]

We present and test a numerical method which, given an analytical or numerical solution of the Helmholtz equation in a neighborhood of a fixed observation point and assuming that the geometrical optics approximation is relevant, determines at this point the number of crossing rays and computes their directions and associated complex amplitudes. [Copyright &y& Elsevier]

We consider the application of the WaveHoltz iteration to time-harmonic elastic wave equations with energy conserving boundary conditions. The original WaveHoltz iteration for acoustic Helmholtz problems is a fixed-point iteration that filters the solution of the wave equation with time-harmonic forcing and boundary data. As in the original WaveHoltz method, we reformulate the fixed point iteration as a positive definite linear system of equations that is iteratively solved by a Krylov method. We present two time-stepping schemes, one explicit and one (novel) implicit, which completely remove time discretization error from the WaveHoltz solution by performing a simple modification of the initial data and time-stepping scheme. Numerical experiments indicate an iteration scaling similar to that of the original WaveHoltz method, and that the convergence rate is dictated by the shortest (shear) wave speed of the problem. We additionally show that the implicit scheme can be advantageous in practice for meshes with disparate element sizes. [ABSTRACT FROM AUTHOR]