Search

We prove convergence of Anderson acceleration for a class of nonsmooth fixed-point problems for which the nonlinearities can be split into a smooth contractive part and a nonsmooth part which has a...

We present a Trefftz-type finite element method on meshes consisting of curvilinear polygons. Local basis functions are computed using integral equation techniques that allow for the efficient and accurate evaluation of quantities needed in the formation of local stiffness matrices. To define our local finite element spaces in the presence of curved edges, we must also properly define what it means for a function defined on a curved edge to be "polynomial" of a given degree on that edge. We consider two natural choices, before settling on the one that yields the inclusion of complete polynomial spaces in our local finite element spaces, and discuss how to work with these edge polynomial spaces in practice. An interpolation operator is introduced for the resulting finite elements, and we prove that it provides optimal order convergence for interpolation error under reasonable assumptions. We provide a description of the integral equation approach used for the examples in this paper, which was recently developed precisely with these applications in mind. A few numerical examples illustrate this optimal order convergence of the finite element solution on some families of meshes in which every element has at least one curved edge. We also demonstrate that it is possible to exploit the approximation power of locally singular functions that may exist in our finite element spaces in order to achieve optimal order convergence without the typical adaptive refinement toward singular points.

We propose a high-order integral equation based method for evaluating interior and boundary derivatives of harmonic functions that are specified by their Dirichlet data in planar domains. The tangential derivative of the given Dirichlet data is used to form a complementary Neumann problem, whose solution is a harmonic conjugate of the function whose derivatives we seek. We use a high-order Nystrom method to compute the Dirichlet trace of the harmonic conjugate on the domain boundary. The tangential derivative of this harmonic conjugate, effected via an FFT, is the normal derivative of the original function. Because the original and conjugate harmonic functions are the real and imaginary parts of a complex analytic function, we are able to use Cauchy's integral formulas to compute function values and derivatives inside the domain. Several numerical experiments, on smooth domains and domains with corners, illustrate the rapid convergence and high accuracy of the proposed approach.

We derive a representation formula for harmonic polynomials and Laurent polynomials in terms of densities of the double-layer potential on bounded piecewise smooth and simply connected domains. From this result, we obtain a method for the numerical computation of conformal maps that applies to both exterior and interior regions. We present analysis and numerical experiments supporting the accuracy and broad applicability of the method.

Despite important applications in unsteady Stokes flow, a Fredholm second kind integral equation formulation modeling the first Dirichlet problem of the modified biharmonic equation in the plane ha...

We present a method to precondition the discretized Lippmann--Schwinger integral equations to model scattering of time-harmonic acoustic waves through a thin inhomogeneous scattering medium. The preconditioner is based on asymptotic results as the thickness of the third component direction goes to zero and requires solving a two dimensional formulation of the problem at the preconditioning step.

High frequency integral equation methodologies display the capability of reproducing single-scattering returns in frequency-independent computational times and employ a Neumann series formulation to handle multiple-scattering effects. This requires the solution of an enormously large number of single-scattering problems to attain a reasonable numerical accuracy in geometrically challenging configurations. Here we propose a novel and effective Krylov subspace method suitable for the use of high frequency integral equation techniques and significantly accelerates the convergence of Neumann series. We additionally complement this strategy utilizing a preconditioner based upon Kirchhoff approximations that provides a further reduction in the overall computational cost., 21 pages, 6 figures

A bilinear quadrature numerically evaluates a continuous bilinear map, such as the $L^2$ inner product, on continuous $f$ and $g$ belonging to known finite-dimensional function spaces. Such maps arise in Galerkin methods for differential and integral equations. The construction of bilinear quadratures over arbitrary domains in $\mathbb{R}^d$ is presented. In one dimension, integration rules of this type include Gaussian quadrature for polynomials and the trapezoidal rule for trigonometric polynomials as special cases. A numerical procedure for constructing bilinear quadratures is developed and validated.

We present a fast direct solver for two-dimensional scattering problems, where an incident wave impinges on a penetrable medium with compact support. We represent the scattered field using a volume potential whose kernel is the outgoing Green's function for the exterior domain. Inserting this representation into the governing partial differential equation, we obtain an integral equation of Lippmann--Schwinger type. The principal contribution here is the development of an automatically adaptive, high-order accurate discretization based on a quad-tree data structure which provides rapid access to arbitrary elements of the discretized system matrix. This permits the straightforward application of state-of-the-art algorithms for constructing compressed versions of the solution operator. These solvers typically require $O(N^{3/2})$ work, where $N$ denotes the number of degrees of freedom. We demonstrate the performance of the method for a variety of problems in both low and high frequency regimes.

Dense particulate flow simulations using integral equation methods demand accurate evaluation of Stokes layer potentials on arbitrarily close interfaces. In this paper, we generalize techniques for close evaluation of Laplace double-layer potentials in [J. Helsing and R. Ojala, J. Comput. Phys., 227 (2008), pp. 2899--2921]. We create a “globally compensated” trapezoid rule quadrature for the Laplace single-layer potential on the interior and exterior of smooth curves. This exploits a complex representation, a product quadrature (in the style of Kress) for the sawtooth function, careful attention to branch cuts, and second-kind barycentric-type formulae for Cauchy integrals and their derivatives. Upon this we build accurate single- and double-layer Stokes potential evaluators by expressing them in terms of Laplace potentials. We test their convergence for vesicle-vesicle interactions, for an extensive set of Laplace and Stokes problems, and when applying the system matrix in a boundary value problem solver...

We develop new probabilistic and deterministic approaches for moment statistics of stochastic partial differential equations with pure jump tempered $\alpha$-stable (T$\alpha$S) Levy processes. With the compound Poisson (CP) approximation or the series representation of the T$\alpha$S process, we simulate the moment statistics of stochastic reaction-diffusion equations with additive T$\alpha$S white noises by the probability collocation method (PCM) and the Monte Carlo (MC) method. PCM is shown to be more efficient and accurate than MC in relatively low dimensions. Then as an alternative approach, we solve the generalized Fokker--Planck equation that describes the evolution of the density for stochastic overdamped Langevin equations to obtain the density and the moment statistics for the solution following two different approaches. First, we solve an integral equation for the density by approximating the T$\alpha$S processes as CP processes; second, we directly solve the tempered fractional PDE (TFPDE). W...

The fast multipole method (FMM) is a technique allowing the fast calculation of long-range interactions between $N$ points in ${\mathcal{O}}(N)$ or ${\mathcal{O}}(N \log N)$ steps with some prescribed error tolerance. The FMM has found many applications in the field of integral equations and boundary element methods, in particular by accelerating the solution of dense linear systems arising from such formulations. Standard FMMs are derived from analytical expansions of the kernel, for example using spherical harmonics or Taylor expansions. In recent years, the range of applicability and the ease of use of FMMs have been extended by the introduction of black-box and kernel independent techniques. In these approaches, the user provides only a subroutine to numerically calculate the interaction kernel. This allows changing the definition of the kernel with minimal changes to the computer program. This paper presents a novel kernel independent FMM, which leads to diagonal multipole-to-local operators. The res...

We present a new temporal approximation scheme for the boundary integral formulation of time-dependent scattering problems which can be combined with either collocation or Galerkin approximation in space. It uses the backward-in-time framework introduced in [P. J. Davies and D. B. Duncan, Convolution Spline Approximations of Volterra Integral Equations, www.mathstat.strath.ac.uk/research/reports/2012 (2012)] with new temporal basis functions which share some properties with radial basis function multiquadrics. We analyze the stability and convergence properties of the new scheme for associated Volterra integral equations and perform extensive numerical tests for scattering from flat polygonal plates and open and closed cubes and spheres, which demonstrate effectiveness of this approach.

We consider a coupled problem of Stokes and Darcy equations. This involves solving PDEs of different orders simultaneously. To overcome this difficulty, we apply a nonoverlapping domain decomposition method based on a Robin boundary condition obtained by combining the velocity and force interface conditions. The coupled system is then reduced to solving each problem separately by an iterative procedure using a Krylov subspace method. The numerical solution in each subdomain is based on the boundary integral formulation, where the kernels are regularized and correction terms are added to reduce the regularization error.

We describe a boundary integral equation that solves the exterior Neumann problem for the Helmholtz equation in three dimensions for smooth obstacles that can be described globally in spherical coordinates. The unique solution is found by approximating the Fredholm integral equation of the second kind with the Galerkin method, where the basis functions are spherical harmonics. This leads to a fast method for small and medium wave numbers, since the system of equations is of size smaller than 64. To smooth the integrand a new map is introduced which significantly improves the accuracy. Numerical results for several smooth surfaces are presented.

The space-angle multiple/semicoarsening multigrid methods of [B. Lee, SIAM J. Sci. Comput., 31 (2010), pp. 4744--4773] for $S_n$ discretizations of the Boltzmann transport equation were developed assuming rediscretizations of the streaming-collision operators on the coarser spatial grids. These rediscretized operators are directly used in the kernels of the spatial coarse-level scalar flux integral equations. Since the computational procedure of these methods is essentially performed on these integral equations, it appears that the multigrid procedure is applied directly to the finest level scalar flux integral equation rather than to the finest level $S_n$ system. However, this procedure is actually implicitly applied to the finest level $S_n$ system. It would be beneficial to relate the multiple/semicoarsening methods directly to the full $S_n$ system or, better yet, to develop a general multigrid framework for the full $S_n$ system, of which the multiple/semicoarsening methods are particular cases. Thi...

We present an integral equation formulation for the unsteady Stokes equations in two dimensions. This problem is of interest in its own right as a model for slow viscous flow, but perhaps more importantly as an ingredient in the solution of the full, incompressible Navier--Stokes equations. Using the unsteady Green's function, the velocity evolves analytically as a divergence-free vector field. This avoids the need for either the solution of coupled field equations (as in fully implicit PDE-based marching schemes) or the projection of the velocity field onto a divergence-free field at each time step (as in operator splitting methods). In addition to discussing the analytic properties of the operators that arise in the integral formulation, we describe a family of high order accurate numerical schemes and illustrate their performance with several examples.

We introduce a solver for stiff ordinary differential equations that is based on the deferred correction scheme for the corresponding Picard integral equation. Our solver relies on the assumption that the solution can be accurately represented by a combination of carefully selected complex exponentials. The solver's accuracy and stability rely on the computation of highly accurate quadrature weights for the integration of the selected exponentials on equidistant nodes. We analyze our solver stability and accuracy regions, and demonstrate its fast convergence on stiff problems. The solver is combined with an adaptive step-size scheme employing interpolation formulas for the exponentially fitted solution.

We analyze the existence, uniqueness, and regularity properties of solutions for general Volterra functional integral equations with the delay function $\theta(t)$ vanishing at the initial point of the given interval $[0,T]$ (with $\theta(t)=qt, \; 0

A scheme for the numerical solution of singular integral equations on piecewise smooth curves is presented. It relies on several techniques: reduction, Nyström discretization, composite quadrature, recursive compressed inverse preconditioning, and multipole acceleration. The scheme is fast and stable. Its computational cost grows roughly logarithmically with the precision sought and linearly with overall system size. When the integral equation models a boundary value problem, the achievable accuracy may be close to the condition number of that problem times machine epsilon. This is illustrated by application to elastostatic problems involving zigzag-shaped cracks with up to twenty thousand corners and branched cracks with hundreds of triple junctions.

This paper concerns numerical methods for computing complex geometrical optics (CGO) solutions to the conductivity equation $\nabla\cdot\sigma\nabla u(\cdot,k)=0$ in $\mathbb{R}^2$ for piecewise smooth conductivities $\sigma$, where $k$ is a complex parameter. The key is to solve an $\mathbb R$-linear singular integral equation defined in the unit disk. Recently, Astala et al. [Appl. Comput. Harmon. Anal., 29 (2010), pp. 2-17] proposed a complicated method for numerical computation of CGO solutions by solving a periodic version of the $\mathbb{R}$-linear integral equation in a rectangle containing the unit disk. In this paper, based on the fast algorithms in [P. Daripa and D. Mashat, Numer. Algorithms, 18 (1998), pp. 133-157] for singular integral transforms, we propose a simpler numerical method which solves the $\mathbb{R}$-linear integral equation in the unit disk directly. For the resulting $\mathbb{R}$-linear operator equation, a minimal residual iterative method is proposed. Numerical examples illustrate the accuracy and efficiency of the new method.

Surface integral-equation methods accelerated with the multilevel fast multipole algorithm (MLFMA) provide a suitable mechanism for electromagnetic analysis of real-life dielectric problems. Unlike the perfect-electric-conductor case, discretizations of surface formulations of dielectric problems yield 2 × 2 partitioned linear systems. Among various surface formulations, the combined tangential formulation (CTF) is the closest to the category of first-kind integral equations, and hence it yields the most accurate results, particularly when the dielectric constant is high and/or the dielectric problem involves sharp edges and corners. However, matrix equations of CTF are highly ill-conditioned, and their iterative solutions require powerful preconditioners for convergence. Second-kind surface integral-equation formulations yield better conditioned systems, but their conditionings significantly degrade when real-life problems include high dielectric constants. In this paper, for the first time in the context of surface integral-equation methods of dielectric objects, we propose Schur complement preconditioners to increase their robustness and efficiency. First, we approximate the dense system matrix by a sparse near-field matrix, which is formed naturally by MLFMA. The Schur complement preconditioning requires approximate solutions of systems involving the (1,1) partition and the Schur complement. We approximate the inverse of the (1,1) partition with a sparse approximate inverse (SAI) based on the Frobenius norm minimization. For the Schur complement, we first approximate it via incomplete sparse matrix-matrix multiplications, and then we generate its approximate inverse with the same SAI technique. Numerical experiments on sphere, lens, and photonic crystal problems demonstrate the effectiveness of the proposed preconditioners. In particular, the results for the photonic crystal problem, which has both surface singularity and a high dielectric constant, shows that accurate CTF solutions for such problems can be obtained even faster than with second-kind integral equation formulations, with the acceleration provided by the proposed Schur complement preconditioners. Scientific and Technical Research Council of Turkey (TÜBİTAK

In a recent series of articles, the author presented a multiple-coarsening multigrid method for solving $S_n$ discretizations of the Boltzmann transport equation. This algorithm is applied to an integral equation for the scalar flux or moments. Although this algorithm is very efficient over parameter regimes that describe realistic neutron/photon transport applications, improved methods that can reduce the computational cost are presented in this paper. These improved methods are derived through a careful examination of the frequencies, particularly the near nullspace, of the integral equation. In the earlier articles, the near-nullspace components were shown to be smooth in angle in the sense that the angular fluxes generated by these components are smooth in angle. In this paper, we present a spatial description of these near-nullspace components. Using the angular description of the earlier papers together with the spatial description reveals the intrinsic space-angle dependence of the integral equation's frequencies. This space-angle dependence is used to determine the appropriate space-angle grids to represent and efficiently attenuate the near-nullspace error components on. It will be shown that these components can have multiple spatial scales. By using only the appropriate space-angle grids that can represent these spatial scales in the original multiple-coarsening algorithm, an improved algorithm is obtained. Moreover, particularly for anisotropic scattering, recognizing the strong angle dependence of the angular fluxes generated by the high frequencies of the integral equation, another improved multiple-coarsening scheme is derived. Restricting this scheme to the appropriate space-angle grids produces a very efficient method.

This paper presents mechanical quadrature methods with high accuracy for solving mixed boundary integral equations of the Helmholtz equation. By estimating the range of eigenvalues for the discretization matrix of the integral equations and applying the collectively compact convergent theory, we prove the stability and convergence of numerical solutions, which is a challenging task for this method. Moreover, the asymptotic error expansions show the method is of order $h^3$. Hence, extrapolation algorithms can be introduced to achieve higher approximation accuracy degree $(\mathcal{O}(h^5))$. Meanwhile, an a posteriori asymptotic error estimate is derived, which can be used to construct self-adaptive algorithms. The numerical examples support our theoretical analysis.

This paper presents a new multigrid method applied to the most common Sn discretizations (Petrov–Galerkin, diamond-differenced, corner-balanced, and discontinuous Galerkin) of the mono-energetic Boltzmann transport equation in the optically thick and thin regimes, and with strong anisotropic scattering. Unlike methods that use scalar DSA diffusion preconditioners for the source iteration, this multigrid method is applied directly to an integral equation for the scalar flux. Thus, unlike the former methods that apply a multigrid strategy to the scalar DSA diffusion operator, this method applies a multigrid strategy to the integral source iteration operator, which is an operator for 5 independent variables in spatial three dimensions (3-d), 3 in space and 2 in angle, and 4 independent variables in spatial 2-d (2 in space and 2 in angle). The core smoother of this multigrid method involves applications of the integral operator. Since the kernel of this integral operator involves the transport sweeps, applyin...

The fast Gauss transform allows for the calculation of the sum of $N$ Gaussians at $M$ points in $\mathcal{O}(N+M)$ time. Here, we extend the algorithm to a wider class of kernels, motivated by quadrature issues that arise in using integral equation methods for solving the heat equation on moving domains. In particular, robust high-order product integration methods require convolution with $\mathcal{O}(q)$ distinct Gaussian-type kernels in order to obtain $q$th-order accuracy in time. The generalized Gauss transform permits the computation of each of these kernels and, thus, the construction of fast solvers with optimal computational complexity. We also develop plane-wave representations of these Gaussian-type fields, permitting the “diagonal translation” version of the Gauss transform to be applied. When the sources and targets lie on a uniform grid, or a hierarchy of uniform grids, we show that the curse of dimensionality (the exponential growth of complexity constants with dimension) can be mitigated. Under these conditions, the algorithm has a lower operation count than the fast Fourier transform even for modest values of $N$ and $M$.

With the help of the multilevel fast multipole algorithm, integral-equation methods can be used to solve real-life electromagnetics problems both accurately and efficiently. Increasing problem dimensions, on the other hand, necessitate effective parallel preconditioners with low setup costs. In this paper, we consider sparse approximate inverses generated from the sparse near-field part of the dense coefficient matrix. In particular, we analyze pattern selection strategies that can make efficient use of the block structure of the near-field matrix, and we propose a load-balancing method to obtain high scalability during the setup. We also present some implementation details, which reduce the computational cost of the setup phase. In conclusion, for the open-surface problems that are modeled by the electric-field integral equation, we have been able to solve ill-conditioned linear systems involving millions of unknowns with moderate computational requirements. For closed surface problems that can be modeled by the combined-field integral equation, we reduce the solution times significantly compared to the commonly used block-diagonal preconditioner. This work was supported by the Scientific and Technical Research Council of Turkey (TUBITAK) under research grants 105E172 and 107E136, the Turkish Academy of Sciences in the framework of the Young Scientist Award Program (LG/TUBAGEBIP/2002-1-12), and contracts from ASELSAN and SSM.

We describe a fast high-order accurate method for the solution of the heat equation in domains with moving Dirichlet or Neumann boundaries and distributed forces. We assume that the motion of the boundary is prescribed. Our method extends the work of Greengard and Strain [Comm. Pure Appl. Math., XLIII (1990), pp. 949-963]. Our scheme is based on a time-space Chebyshev pseudo-spectral collocation discretization, which is combined with a recursive product quadrature rule to accurately and efficiently approximate convolutions with Green's function for the heat equation. We present numerical results that exhibit up to eighth-order convergence rates. Assuming $N$ time steps and $M$ spatial discretization points, the evaluation of the solution of the heat equation at the same number of points in space-time requires ${\mathcal{O}} ( N M \log M)$ work. Thus, our scheme can be characterized as “fast”; that is, it is work-optimal up to a logarithmic factor.

A method is developed for the computation of the weights and nodes of a numerical quadrature which integrates functions containing singularities up to order $1/x^{2}$, without the requirement to know the coefficients of the singularities exactly. The work is motivated by the need to evaluate such integrals on boundary elements in potential problems and is a simplification of a previously published method, but with the advantage of handling singularities at the endpoints of the integral. The numerical performance of the method is demonstrated by application to an integral containing logarithmic, first, and second order singularities, characteristic of the problems encountered in integrating a Green's function in boundary element problems. It is found that the quadrature is accurate to 11-12 decimal places when computed in double precision.

We consider two-dimensional scattering problems, formulated as an integral equation defined on the boundary of the scattering obstacle. The oscillatory nature of high-frequency scattering problems necessitates a large number of unknowns in classical boundary element methods. In addition, the corresponding discretization matrix of the integral equation is dense. We formulate a boundary element method with basis functions that incorporate the asymptotic behavior of the solution at high frequencies. The method exhibits the effectiveness of asymptotic methods at high frequencies with only few unknowns, but retains accuracy for lower frequencies. New in our approach is that we combine this hybrid method with very effective quadrature rules for oscillatory integrals. As a result, we obtain a sparse discretization matrix for the oscillatory problem. Moreover, numerical experiments indicate that the accuracy of the solution actually increases with increasing frequency. The sparse discretization applies to problems where the phase of the solution can be predicted a priori, for example in the case of smooth and convex scatterers. © 2007 Society for Industrial and Applied Mathematics. ispartof: SIAM Journal on Scientific Computing vol:29 issue:6 pages:2305-2328 status: published

This paper introduces a new directional multilevel algorithm for solving $N$-body or $N$-point problems with highly oscillatory kernels. These systems often result from the boundary integral formulations of scattering problems and are difficult due to the oscillatory nature of the kernel and the non-uniformity of the particle distribution. We address the problem by first proving that the interaction between a ball of radius $r$ and a well-separated region has an approximate low rank representation, as long as the well-separated region belongs to a cone with a spanning angle of $O(1/r)$ and is at a distance which is at least $O(r^2)$ away from from the ball. We then propose an efficient and accurate procedure which utilizes random sampling to generate such a separated, low rank representation. Based on the resulting representations, our new algorithm organizes the high frequency far field computation by a multidirectional and multiscale strategy to achieve maximum efficiency. The algorithm performs well on a large group of highly oscillatory kernels. Our algorithm is proved to have $O(N\log N)$ computational complexity for any given accuracy when the points are sampled from a two dimensional surface. We also provide numerical results to demonstrate these properties.

Averaging techniques or gradient recovery techniques are frequently employed tools for the a posteriori finite element error analysis. Their very recent mathematical justification for partial differential equations allows unstructured meshes and nonsmooth exact solutions. This paper establishes an averaging technique for the hypersingular integral equation on a one-dimensional boundary and presents numerical examples that show averaging techniques can be employed for an effective mesh-refining algorithm. For the discussed test examples, the provided estimator estimates the (in general unknown) error very accurately in the sense that the quotient error/estimator stays bounded with a value close to $1$.

We describe a high-order method for computing the monostatic and bistatic radar cross section (RCS) of a class of three-dimensional targets. Our method is based on an electric field surface integral equation reformulation of the Maxwell equations. The hybrid nature of the scheme is due to approximations based on a combination of tangential and nontangential basis functions on a parametric reference spherical surface. A principal feature of the high-order algorithm is that it requires solutions of linear systems with substantially fewer unknowns than existing methods. We demonstrate that very accurate RCS values for medium (electromagnetic-) sized scatterers can be computed using a few tens of thousands of unknowns. Thus linear systems arising in the high-order method for low to medium frequency scattering can be solved using direct solves. This is extremely advantageous in monostatic RCS computations, for which transmitters and receivers are co-located and hence the discretized electromagnetic linear system must be solved for hundreds of right-hand sides corresponding to receiver locations. We demonstrate the high-order convergence of our method for several three-dimensional targets. We prove the high-order spectral accuracy of our approximations to the RCS for a class of perfect conductors described globally in spherical coordinates.

In this paper, we propose a new kind of numerical simulation method for backward stochastic differential equations (BSDEs). We discretize the continuous BSDEs on time-space discrete grids, use the Monte Carlo method to approximate mathematical expectations, and use space interpolations to compute values at non-grid points. To demonstrate the accuracy and the effectiveness of our method, several numerical examples are given.

The goal of this work is the numerical realization of the probe method suggested by Ikehata for the detection of an obstacle D in inverse scattering. The main idea of the method is to use probes in the form of point source $\Phi(\cdot,z)$ with source point z to define an indicator function $\hat{I}(z)$ which can be reconstructed from Cauchy data or far field data. The indicator function $\hat{I}(z)$ can be shown to blow off when the source point z tends to the boundary $\partial D$, and this behavior can be used to find D. To study the feasibility of the probe method we will use two equivalent formulations of the indicator function. We will carry out the numerical realization of the functional and show reconstructions of a sound-soft obstacle.

Averaging techniques for finite element error control, occasionally called ZZ estimators for the gradient recovery, enjoy a high popularity in engineering because of their striking simplicity and universality: One does not even require a PDE to apply the nonexpensive post-processing routines. Recently, averaging techniques have been mathematically proved to be reliable and efficient for various applications of the finite element method. This paper establishes a class of averaging error estimators for boundary integral methods. Symm's integral equation of the first kind with a nonlocal single-layer integral operator serves as a model equation studied both theoretically and numerically. We introduce four new error estimators which are proven to be reliable and efficient up to terms of higher order. The higher-order terms depend on the regularity of the exact solution. Several numerical experiments illustrate the theoretical results and show that the [normally unknown] error is sharply estimated by the proposed estimators, i.e., error and estimators almost coincide.

A strategy for controlling the stepsize in the numerical integration of stochastic differential equations (SDEs) is presented. It is based on estimating the pth mean of local errors. The strategy leads to stepsize sequences that are identical for all computed paths. For the family of Euler schemes for SDEs with small noise, we derive computable estimates for the dominating term of the pth mean of local errors and show that the strategy becomes efficient for reasonable stepsizes. Numerical experience is reported for test examples including scalar SDEs and a stochastic circuit model.

We present new numerical methods for scalar stochastic differential equations. Successive time increments are independent random variables with an exponential distribution. We perform numerical experiments using a double-well potential. Exponential timestepping algorithms are efficient for escape-time problems because a simple boundary test can be performed at the end of each step.

Sobolev-Slobodeckij norms on small overlapping domains of two neighboring elements serve as a posteriori error estimators and mesh-refining indicators in adaptive boundary element methods. This paper is concerned with two error estimators, $\eta_F$ and $\mu_F$. The first variant $\eta_F$ is efficient and the second $\mu_F$ is reliable; that is, up to multiplicative constants and numerical quadrature errors, they are lower or upper error bounds. Faermann recently established reliability and efficiency of $\eta_F$ for the Galerkin boundary element method and considered $\mu_F$. This work approaches the two estimators $\eta_F\le\mu_F$ for the Galerkin, qualocation, and collocation boundary element methods for a single layer operator integral equation of the first kind. Upper and lower bounds are established theoretically and validated numerically. Numerical experiments support the estimators' accuracies and the efficiencies of proposed adaptive mesh-refining algorithms even in energy norms. For qualocation and collocation schemes, difficulties for $\alpha\le 1/2$ are caused by the lack of a Sobolev embedding $H^\alpha(\Gamma)\hookrightarrow{\mathcal{C}} (\Gamma)$. Hence, for the latter schemes, equivalence of error and estimators in $H^{\alpha-1}(\Gamma)$ can be proven only for $\alpha>1/2$. Numerical evidence conjectures equivalence for $\alpha=1/2$ as well.

Within the framework of two-dimensional potential theory, we consider problems defined on slender domains. The boundary element matrices for such problems are poorly conditioned due to the presence of two disparate length scales. A new class of preconditioners is proposed to remedy this problem so that the preconditioned boundary element matrices become insensitive to the domain slenderness. The preconditioners are constructed using the spectral properties of the boundary integral operators defined on the elliptical domains.

In this paper we develop irregular wavelet representations for complex domains with the goal of demonstrating their potential for three-dimensional (3D) scientific and engineering computing applications. We show existence and construction of a large class of continuous spatially adapted multiwavelets in $R^{\eta}$ with vanishing moments over complex geometries. These wavelets share all of the major advantages of conventional wavelets in that they provide an analytical tool for studying data, functions, and operators at different scales. However, unlike conventional wavelets, which are restricted to uniform grids, spatially adapted multiwavelets allow fast transform, localization, and decorrelation on complex meshes, such as those encountered in finite element modeling. We show how these new constructions can be applied to partial differential equations cast in the integral form. We implement the wavelet approach for several model two-dimensional (2D) and 3D potential problems. It is shown that the optimal convergence rate is achieved, with only ${\cal O}( N ( {{\rm log}N} )^{\alpha} )$ entries of the discrete operator matrix, where $\alpha$ is a small number and N is the number of unknowns.

We present an adaptive fast multipole method for inverting the square root of the Laplacian in two dimensions. Solving this problem is the dominant computational cost in many applications arising in electrical engineering, geophysical fluid dynamics, and the study of thin films. It corresponds to the evaluation of the field induced by a planar distribution of charge or vorticity. Our algorithm is direct and assumes only that the source distribution is discretized using an adaptive quad-tree. The amount of work grows linearly with the number of mesh points.

Choosing the regularization parameter for an ill-posed problem is an art based on good heuristics and prior knowledge of the noise in the observations. In this work, we propose choosing the parameter, without a priori information, by approximately minimizing the distance between the true solution to the discrete problem and the family of regularized solutions. We demonstrate the usefulness of this approach for Tikhonov regularization and for an alternate family of solutions. Further, we prove convergence of the regularization parameter to zero as the standard deviation of the noise goes to zero.

The volume integral equation of electromagnetic scattering can be used to compute the scattering by inhomogeneous or anisotropic scatterers. In this paper we compute the spectrum of the scattering integral operator for a sphere and the eigenvalues of the coefficient matrices that arise from the discretization of the integral equation. For the case of a spherical scatterer, the eigenvalues lie mostly on a line in the complex plane, with some eigenvalues lying below the line. We show how the spectrum of the integral operator can be related to the well-posedness of a modified scattering problem. The eigenvalues lying below the line segment arise from resonances in the analytical series solution of scattering by a sphere. The eigenvalues on the line are due to the branch cut of the square root in the definition of the refractive index. We try to use this information to predict the performance of iterative methods. For a normal matrix the initial guess and the eigenvalues of the coefficient matrix determine the rate of convergence of iterative solvers. We show that when the scatterer is a small sphere, the convergence rate for the nonnormal coefficient matrices can be estimated but this estimate is no longer valid for large spheres.

The inverse scattering problem under consideration is to determine the shape of an obstacle in $\RE^3$ from a knowledge of the time harmonic incident acoustic wave and the far field pattern of the scattered wave with frequency in the resonance region. A method for solving this nonlinear and improperly posed problem is presented which is based on solving a linear integral equation of the first kind and avoids the use of nonlinear optimization methods. Numerical examples are given showing the practicality of this new approach.