Search

In this paper we derive families of Gershgorin-type inclusion sets for the spectra and pseudospectra of finite matrices. In common with previous generalisations of the classical Gershgorin bound for the spectrum, our inclusion sets are based on a block decomposition. In contrast to previous generalisations that treat the matrix as a perturbation of a block-diagonal submatrix, our arguments treat the matrix as a perturbation of a block-tridiagonal matrix, which can lead to sharp spectral bounds, as we show for the example of large Toeplitz matrices. Our inclusion sets, which take the form of unions of pseudospectra of square or rectangular submatrices, build on our own recent work on inclusion sets for bi-infinite matrices [Chandler-Wilde, Chonchaiya, Lindner, {\em J. Spectr. Theory} {\bf 14}, 719--804 (2024)]., Comment: 28 pages + 9 pages of Supplementary Information

In this paper we derive novel families of inclusion sets for the spectrum and pseudospectrum of large classes of bounded linear operators, and establish convergence of particular sequences of these inclusion sets to the spectrum or pseudospectrum, as appropriate. Our results apply, in particular, to bounded linear operators on a separable Hilbert space that, with respect to some orthonormal basis, have a representation as a bi-infinite matrix that is banded or band-dominated. More generally, our results apply in cases where the matrix entries themselves are bounded linear operators on some Banach space. In the scalar matrix entry case we show that our methods, given the input information we assume, lead to a sequence of approximations to the spectrum, each element of which can be computed in finitely many arithmetic operations, so that, with our assumed inputs, the problem of determining the spectrum of a band-dominated operator has solvability complexity index one, in the sense of Ben-Artzi et al. (C. R. Acad. Sci. Paris, Ser. I 353 (2015), 931-936). As a concrete and substantial application, we apply our methods to the determination of the spectra of non-self-adjoint bi-infinite tridiagonal matrices that are pseudoergodic in the sense of Davies (Commun. Math. Phys. 216 (2001) 687-704).

We obtain sequences of inclusion sets for the spectrum, essential spectrum, and pseudospectrum of banded, in general non-normal, matrices of finite or infinite size. Each inclusion set is the union of the pseudospectra of certain submatrices of a chosen size $n$. Via the choice of $n$, one can balance accuracy of approximation against computational cost, and we show, in the case of infinite matrices, convergence as $n\to\infty$ of the respective inclusion set to the corresponding spectral set.

We say that $\Gamma$, the boundary of a bounded Lipschitz domain, is locally dilation invariant if, at each $x\in \Gamma$, $\Gamma$ is either locally $C^1$ or locally coincides (in some coordinate system centred at $x$) with a Lipschitz graph $\Gamma_x$ such that $\Gamma_x=\alpha_x\Gamma_x$, for some $\alpha_x\in (0,1)$. In this paper we study, for such $\Gamma$, the essential spectrum of $D_\Gamma$, the double-layer (or Neumann-Poincar\'e) operator of potential theory, on $L^2(\Gamma)$. We show, via localisation and Floquet-Bloch-type arguments, that this essential spectrum is the union of the spectra of related continuous families of operators $K_t$, for $t\in [-\pi,\pi]$; moreover, each $K_t$ is compact if $\Gamma$ is $C^1$ except at finitely many points. For the 2D case where, additionally, $\Gamma$ is piecewise analytic, we construct convergent sequences of approximations to the essential spectrum of $D_\Gamma$; each approximation is the union of the eigenvalues of finitely many finite matrices arising from Nystr\"om-method approximations to the operators $K_t$. Through error estimates with explicit constants, we also construct functionals that determine whether any particular locally-dilation-invariant piecewise-analytic $\Gamma$ satisfies the well-known spectral radius conjecture, that the essential spectral radius of $D_\Gamma$ on $L^2(\Gamma)$ is $<1/2$ for all Lipschitz $\Gamma$. We illustrate this theory with examples; for each we show that the essential spectral radius is $<1/2$, providing additional support for the conjecture. We also, via new results on the invariance of the essential spectral radius under locally-conformal $C^{1,\beta}$ diffeomorphisms, show that the spectral radius conjecture holds for all Lipschitz curvilinear polyhedra.

Sound-soft fractal screens can scatter acoustic waves even when they have zero surface measure. To solve such scattering problems we make what appears to be the first application of the boundary element method (BEM) where each BEM basis function is supported in a fractal set, and the integration involved in the formation of the BEM matrix is with respect to a non-integer order Hausdorff measure rather than the usual (Lebesgue) surface measure. Using recent results on function spaces on fractals, we prove convergence of the Galerkin formulation of this ``Hausdorff BEM'' for acoustic scattering in $\mathbb{R}^{n+1}$ ($n=1,2$) when the scatterer, assumed to be a compact subset of $\mathbb{R}^n\times\{0\}$, is a $d$-set for some $d\in (n-1,n]$, so that, in particular, the scatterer has Hausdorff dimension $d$. For a class of fractals that are attractors of iterated function systems, we prove convergence rates for the Hausdorff BEM and superconvergence for smooth antilinear functionals, under certain natural regularity assumptions on the solution of the underlying boundary integral equation. We also propose numerical quadrature routines for the implementation of our Hausdorff BEM, along with a fully discrete convergence analysis, via numerical (Hausdorff measure) integration estimates and inverse estimates on fractals, estimating the discrete condition numbers. Finally, we show numerical experiments that support the sharpness of our theoretical results, and our solution regularity assumptions, including results for scattering in $\mathbb{R}^2$ by Cantor sets, and in $\mathbb{R}^3$ by Cantor dusts., Comment: 61 pages

We present new second-kind integral-equation formulations of the interior and exterior Dirichlet problems for Laplace's equation. The operators in these formulations are both continuous and coercive on general Lipschitz domains in $\mathbb{R}^d$, $d\geq 2$, in the space $L^2(\Gamma)$, where $\Gamma$ denotes the boundary of the domain. These properties of continuity and coercivity immediately imply that (i) the Galerkin method converges when applied to these formulations; and (ii) the Galerkin matrices are well-conditioned as the discretisation is refined, without the need for operator preconditioning (and we prove a corresponding result about the convergence of GMRES). The main significance of these results is that it was recently proved (see Chandler-Wilde and Spence, Numer. Math., 150(2):299-271, 2022) that there exist 2- and 3-d Lipschitz domains and 3-d starshaped Lipschitz polyhedra for which the operators in the standard second-kind integral-equation formulations for Laplace's equation (involving the double-layer potential and its adjoint) $\textit{cannot}$ be written as the sum of a coercive operator and a compact operator in the space $L^2(\Gamma)$. Therefore there exist 2- and 3-d Lipschitz domains and 3-d starshaped Lipschitz polyhedra for which Galerkin methods in $L^2(\Gamma)$ do $\textit{not}$ converge when applied to the standard second-kind formulations, but $\textit{do}$ converge for the new formulations.

The Half-Space Matching (HSM) method has recently been developed as a new method for the solution of 2D scattering problems with complex backgrounds, providing an alternative to Perfectly Matched Layers (PML) or other artificial boundary conditions. Based on half-plane representations for the solution, the scattering problem is rewritten as a system coupling (1) a standard finite element discretisation localised around the scatterer and (2) integral equations whose unknowns are traces of the solution on the boundaries of a finite number of overlapping half-planes contained in the domain. While satisfactory numerical results have been obtained for real wavenumbers, well-posedness and equivalence of this HSM formulation to the original scattering problem have been established only for complex wavenumbers. In the present paper we show, in the case of a homogeneous background, that the HSM formulation is equivalent to the original scattering problem also for real wavenumbers, and so is well-posed, provided the traces satisfy radiation conditions at infinity analogous to the standard Sommerfeld radiation condition. As a key component of our argument we show that, if the trace on the boundary of a half-plane satisfies our new radiation condition, then the corresponding solution to the half-plane Dirichlet problem satisfies the Sommerfeld radiation condition in a slightly smaller half-plane. We expect that this last result will be of independent interest, in particular in studies of rough surface scattering.

It is well known that, with a particular choice of norm, the classical double-layer potential operator $D$ has essential norm $<1/2$ as an operator on the natural trace space $H^{1/2}(\Gamma)$ whenever $\Gamma$ is the boundary of a bounded Lipschitz domain. This implies, for the standard second-kind boundary integral equations for the interior and exterior Dirichlet and Neumann problems in potential theory, convergence of the Galerkin method in $H^{1/2}(\Gamma)$ for any sequence of finite-dimensional subspaces $(\mathcal{H}_N)_{N=1}^\infty$ that is asymptotically dense in $H^{1/2}(\Gamma)$. Long-standing open questions are whether the essential norm is also $<1/2$ for $D$ as an operator on $L^2(\Gamma)$ for all Lipschitz $\Gamma$ in 2-d; or whether, for all Lipschitz $\Gamma$ in 2-d and 3-d, or at least for the smaller class of Lipschitz polyhedra in 3-d, the weaker condition holds that the operators $\pm \frac{1}{2}I+D$ are compact perturbations of coercive operators -- this a necessary and sufficient condition for the convergence of the Galerkin method for every sequence of subspaces $(\mathcal{H}_N)_{N=1}^\infty$ that is asymptotically dense in $L^2(\Gamma)$. We settle these open questions negatively. We give examples of 2-d and 3-d Lipschitz domains with Lipschitz constant equal to one for which the essential norm of $D$ is $\geq 1/2$, and examples with Lipschitz constant two for which the operators $\pm \frac{1}{2}I +D$ are not coercive plus compact. We also give, for every $C>0$, examples of Lipschitz polyhedra for which the essential norm is $\geq C$ and for which $\lambda I+D$ is not a compact perturbation of a coercive operator for any real or complex $\lambda$ with $|\lambda|\leq C$. Finally, we resolve negatively a related open question in the convergence theory for collocation methods.

The Half-Space Matching (HSM) method has recently been developed as a new method for the solution of 2D scattering problems with complex backgrounds, providing an alternative to Perfectly Matched Layers (PML) or other artificial boundary conditions. Based on half-plane representations for the solution, the scattering problem is rewritten as a system of integral equations in which the unknowns are restrictions of the solution to the boundaries of a finite number of overlapping half-planes contained in the domain: this integral equation system is coupled to a standard finite element discretisation localised around the scatterer. While satisfactory numerical results have been obtained for real wavenumbers, wellposedness and equivalence to the original scattering problem have been established only for complex wavenumbers. In the present paper, by combining the HSM framework with a complex-scaling technique, we provide a new formulation for real wavenumbers which is provably well-posed and has the attraction for computation that the complex-scaled solutions of the integral equation system decay exponentially at infinity. The analysis requires the study of double-layer potential integral operators on intersecting infinite lines, and their analytic continuations. The effectiveness of the method is validated by preliminary numerical results.

In this paper we propose a method for computing the Faddeeva function $w(z) := e^{-z^2}\mathrm{erfc}(-i z)$ via truncated modified trapezoidal rule approximations to integrals on the real line. Our starting point is the method due to Matta and Reichel (Math. Comp. 25 (1971), pp. 339-344) and Hunter and Regan (Math. Comp. 26 (1972), pp. 339-541). Addressing shortcomings flagged by Weideman (SIAM. J. Numer. Anal. 31 (1994), pp. 1497-1518), we construct approximations which we prove are exponentially convergent as a function of $N+1$, the number of quadrature points, obtaining error bounds which show that accuracies of $2\times 10^{-15}$ in the computation of $w(z)$ throughout the complex plane are achieved with $N = 11$, this confirmed by computations. These approximations, moreover, provably achieve small relative errors throughout the upper complex half-plane where $w(z)$ is non-zero. Numerical tests suggest that this new method is competitive, in accuracy and computation times, with existing methods for computing $w(z)$ for complex $z$.

We study boundary element methods for time-harmonic scattering in $\mathbb{R}^n$ ($n=2,3$) by a fractal planar screen, assumed to be a non-empty bounded subset $\Gamma$ of the hyperplane $\Gamma_\infty=\mathbb{R}^{n-1}\times \{0\}$. We consider two distinct cases: (i) $\Gamma$ is a relatively open subset of $\Gamma_\infty$ with fractal boundary (e.g.\ the interior of the Koch snowflake in the case $n=3$); (ii) $\Gamma$ is a compact fractal subset of $\Gamma_\infty$ with empty interior (e.g.\ the Sierpinski triangle in the case $n=3$). In both cases our numerical simulation strategy involves approximating the fractal screen $\Gamma$ by a sequence of smoother "prefractal" screens, for which we compute the scattered field using boundary element methods that discretise the associated first kind boundary integral equations. We prove sufficient conditions on the mesh sizes guaranteeing convergence to the limiting fractal solution, using the framework of Mosco convergence. We also provide numerical examples illustrating our theoretical results.

We propose a boundary element method for problems of time-harmonic acoustic scattering by multiple obstacles in two dimensions, at least one of which is a convex polygon. By combining a Hybrid Numerical Asymptotic (HNA) approximation space on the convex polygon with standard polynomial-based approximation spaces on each of the other obstacles, we show that the number of degrees of freedom required in the HNA space to maintain a given accuracy needs to grow only logarithmically with respect to the frequency, as opposed to the (at least) linear growth required by standard polynomial-based schemes. This method is thus most effective when the convex polygon is many wavelengths in diameter and the small obstacles have a combined perimeter comparable to the problem wavelength.

This paper is concerned with resolvent estimates on the real axis for the Helmholtz equation posed in the exterior of a bounded obstacle with Dirichlet boundary conditions when the obstacle is trapping. There are two resolvent estimates for this situation currently in the literature: (i) in the case of elliptic trapping the general "worst case" bound of exponential growth applies, and examples show that this growth can be realised through some sequence of wavenumbers, (ii) in the prototypical case of hyperbolic trapping where the Helmholtz equation is posed in the exterior of two strictly convex obstacles (or several obstacles with additional constraints) the nontrapping resolvent estimate holds with a logarithmic loss. This paper proves the first resolvent estimate for parabolic trapping by obstacles, studying a class of obstacles the prototypical example of which is the exterior of two squares (in 2-d), or two cubes (in 3-d), whose sides are parallel. We show, via developments of the vector-field/multiplier argument of Morawetz and the first application of this methodology to trapping configurations, that a resolvent estimate holds with a polynomial loss over the nontrapping estimate. We use this bound, along with the other trapping resolvent estimates, to prove results about integral-equation formulations of the boundary value problem in the case of trapping. Feeding these bounds into existing frameworks for analysing finite and boundary element methods, we obtain the first wavenumber-explicit proofs of convergence for numerical methods for solving the Helmholtz equation in the exterior of a trapping obstacle.

We consider time-harmonic acoustic scattering by planar sound-soft (Dirichlet) and sound-hard (Neumann) screens embedded in $\mathbb{R}^n$ for $n = 2$ or $3$. In contrast to previous studies in which the screen is assumed to be a bounded Lipschitz (or smoother) relatively open subset of the plane, we consider screens occupying an arbitrary bounded subset of the plane. Thus our study includes cases where the screen is a relatively open set with a boundary that is fractal, or indeed has positive surface measure, and cases where the screen has empty interior and is fractal, or indeed has positive surface measure. We elucidate for which screen geometries the classical formulations of screen scattering are well-posed, showing that the classical formulation for sound-hard scattering is not well-posed if the screen boundary has Hausdorff dimension greater than $n-2$. We also propose novel well-posed boundary integral equation (BIE) and boundary value problem (BVP) formulations, valid for arbitrary bounded screens. In fact, we show that for sufficiently irregular screens there exist whole families of well-posed formulations, with infinitely many distinct solutions, the distinct formulations distinguished by the sense in which the boundary conditions are understood. To select the physically correct solution we propose limiting geometry principles, taking the limit of solutions for a convergent sequence of more regular screens, this a natural procedure for those fractal screens for which there exists a standard sequence of prefractal approximations. We present examples exhibiting interesting physical behaviours, including penetration of waves through screens with "holes" in them, where the "holes" have no interior points, so that the screen and its closure scatter differently. Our results depend on subtle and interesting properties of fractional Sobolev spaces on non-Lipschitz sets.