betaFeedback

WorksMathematics

An overlapping domain decomposition method based on solution-transfer operators

Abstract

An overlapping domain decomposition method is described for variable-coefficient elliptic boundary value problems on domains that can be decomposed into slabs or shells. The method represents the global solution through its traces on internal interfaces, coupled by local Dirichlet solution transfer operators posed on overlapping double slab domains. The key observation is that these interface maps act between separated interfaces, and as such can be written as smooth-kernel integral operators. The resulting global equilibrium system is Fredholm second kind and, unlike non-overlapping formulations, requires no same-interface Dirichlet-to-Neumann or other interface maps with singular kernels. This makes its off-diagonal blocks highly amenable to hierarchical low-rank compression. The formulation admits complementary continuum and discrete interpretations. At fixed slab width, the method is stable under discretization, sufficiently accurate local solves and compression. At the discrete level, the system can be interpreted as a block Jacobi preconditioned Schur complement system. For compatible SPD discretizations satisfying a standard stable-splitting assumption, the symmetrically scaled interface matrix satisfies an energy-norm condition-number bound that depends on the slab width but is uniform with respect to the local resolution. The formulation is implemented using high-order local solvers and hierarchical compression based on randomized sampling. Numerical experiments report iteration counts, accuracy, and compressibility for 2D and 3D elliptic, nonsymmetric, and oscillatory problems with as many as 28 million degrees of freedom.

Introduction

We describe a numerical method for solving boundary value problems of the form

{[Au](x)=f(x)x∈Ω,u(x)=g(x)x∈Γ,(1)\begin{cases} [\mathcal{A}u](x)=f(x) & x\in\Omega,\\ u(x)=g(x) & x\in\Gamma, \tag*{(1)} \end{cases}

where Ω\Omega is a domain in R2\mathbb{R}^{2} or R3\mathbb{R}^{3} with boundary Γ\Gamma, and where A\mathcal{A} is a scalar elliptic partial differential operator that may have variable coefficients. We restrict ourselves in this manuscript to coefficients in R\mathbb{R}, but generalizing to C\mathbb{C} poses no significant additional challenge. The method described works best on domains that can naturally be tessellated into thin slabs, as illustrated in Figure 1. The central object is our overlapping solution-transfer formulation, not a particular choice of local discretization. The solution-transfer blocks can in principle be approximated using finite differences, finite elements, spectral elements, or other local solvers, provided that the interface discretizations give accurate approximations of the local Dirichlet solution maps. For the large-scale numerical experiments in this paper, we use a multidomain spectral collocation implementation, since the thin local Dirichlet problems are particularly well suited to high-order discretizations and direct local solvers.

Figure 1. Examples of domains that can naturally be tessellated into thin slabs or shells. Each is decomposed into 4 overlapping double-wide-slabs, derived from 5 non-overlapping slabs.

A model problem

To introduce the key ideas, let us consider a model problem where a square domain Ω\Omega has been partitioned into five thin strips, as shown in Figure 2. We discretize (1) to obtain a linear system Au=b\mathbf{A}\mathbf{u}=\mathbf{b} for some sparse matrix A\mathbf{A}. For simplicity, assume that we use finite differences, so that each entry of u\mathbf{u} holds a collocated value of the solution uu at some grid point. Now suppose that we — in principle — use block Gaussian elimination to excise all nodes that are interior to the five slabs (blue dots in Figure 2), keeping only nodes associated with the interfaces. This would result in a block tridiagonal linear system of the form

Figure 2. The model problem considered in § 2.1: A linear system A\mathbf{A} results from discretization on a computational grid (gray nodes hold Dirichlet data and are not ‘active’). The domain is split into thin slabs, separated by the nodes in J:={Jj}j=1NdsJ := \{J_j\}_{j=1}^{N_{\mathrm{ds}}} (red). The reduced linear system (middle, see (1.2)) has the Schur complement coefficient matrix T=A(J,J)−A(J,Jc)A(Jc,Jc)−1A(Jc,J)\mathbf{T} = \mathbf{A}(J,J) - \mathbf{A}(J,J^{c})\mathbf{A}(J^{c},J^{c})^{-1}\mathbf{A}(J^{c},J). The matrix S\mathbf{S} from (1.3) shown on the right is obtained by block diagonal preconditioning of T\mathbf{T}.

\begin{bmatrix} \mathbf{T}_{1,1} & \mathbf{T}_{1,2} & 0 & 0 \\ \mathbf{T}_{2,1} & \mathbf{T}_{2,2} & \mathbf{T}_{2,3} & 0 \\ 0 & \mathbf{T}_{3,2} & \mathbf{T}_{3,3} & \mathbf{T}_{3,4} \\ 0 & 0 & \mathbf{T}_{4,3} & \mathbf{T}_{4,4} \end{bmatrix} \begin{bmatrix} \mathbf{u}_1 \\ \mathbf{u}_2 \\ \mathbf{u}_3 \\ \mathbf{u}_4 \end{bmatrix} = \begin{bmatrix} \mathbf{f}'_1 \\ \mathbf{f}'_2 \\ \mathbf{f}'_3 \\ \mathbf{f}'_4 \end{bmatrix}, \tag*{(2)}\end{bmatrix}

where the blocks Tj,j′\mathbf{T}_{j,j'} are dense matrices formed by taking Schur complements in the original sparse matrix A\mathbf{A}, where the vectors hj\mathbf{h}_j encode the body load and the boundary data, and where the vectors uj\mathbf{u}_j hold the function values of uu on the grid nodes on the four internal boundaries (see § 2.1 for details). Following standard practice, we could solve (2) using a preconditioned iterative solver, where each block Tj,j′\mathbf{T}_{j,j'} is applied implicitly using local solvers for the five domain interiors (oftentimes a sparse direct solver, to accelerate repeated solves).

In the method proposed here, we consider the block diagonally pre-conditioned version of the system (1.2), which results in a system of the form

\begin{bmatrix} \mathbf{I} & -\mathbf{S}_{1,2} & 0 & 0 \\ -\mathbf{S}_{2,1} & \mathbf{I} & -\mathbf{S}_{2,3} & 0 \\ 0 & -\mathbf{S}_{3,2} & \mathbf{I} & -\mathbf{S}_{3,4} \\ 0 & 0 & -\mathbf{S}_{4,3} & \mathbf{I} \end{bmatrix} \begin{bmatrix} \mathbf{u}_1 \\ \mathbf{u}_2 \\ \mathbf{u}_3 \\ \mathbf{u}_4 \end{bmatrix} = \begin{bmatrix} \widehat{\mathbf{f}}_1 \\ \widehat{\mathbf{f}}_2 \\ \widehat{\mathbf{f}}_3 \\ \widehat{\mathbf{f}}_4 \end{bmatrix}, \tag*{(3)}\end{bmatrix}

where Sj,j′=−Tj,j−1Tj,j′\mathbf{S}_{j,j'}=-\mathbf{T}_{j,j}^{-1}\mathbf{T}_{j,j'} and f^j=Tj,j−1fj′\widehat{\mathbf{f}}_j=\mathbf{T}_{j,j}^{-1}\mathbf{f}'_j. In contrast to standard practice, we will form the blocks Sj,j′\mathbf{S}_{j,j'} explicitly, exploiting that they have internal structure that allows us to store them to high accuracy using data sparse representations (see, e.g., [22, 5, 23, 7, 6, 28, 21, 38, 36, 37, 4]) that exploit rank deficiencies in the off-diagonal blocks of Sj,j′\mathbf{S}_{j,j'}. Importantly, we will not compute the blocks Sj,j′\mathbf{S}_{j,j'} using the formula Sj,j′=−Tj,j−1Tj,j′\mathbf{S}_{j,j'}=-\mathbf{T}_{j,j}^{-1}\mathbf{T}_{j,j'}, but we will use the fact that they can be written as Dirichlet-to-Dirichlet maps (see § 1.2).

The key observation underpinning our work is that the matrices Sj,j′\mathbf{S}_{j,j'} are very benign. They turn out to be discrete approximations to integral operators that are not only compact, but in fact have smooth kernels, with no singularity at the diagonal. In consequence, these matrices are highly compressible. In practice, the matrix S\mathbf{S} from the global interface system (3) is often substantially better conditioned than the original discretized PDE system. Its favorable behavior is connected to the Fredholm second-kind structure of the underlying continuum equilibrium equation. In discrete form, we write

Su=(I−K)u=f^,(4)\mathbf{S}\mathbf{u}=(\mathbf{I}-\mathbf{K})\mathbf{u}=\widehat{\mathbf{f}}, \tag*{(4)}

Here K\mathbf{K} approximates a compact operator assembled from smooth-kernel maps between separated interfaces. This second-kind structure explains the observed favorable conditioning and, more precisely, why local refinement at fixed physical slab width does not introduce the large spectral scales associated with discretizing the underlying differential operator; § 3 makes the latter approximation statement precise. For compatible SPD discretizations, § 4 gives an upper bound for the symmetrically scaled system, equivalently for S\mathbf{S} in an associated energy norm. The supplementary material reports empirical spectral diagnostics for representative stencil and collocation realizations of the raw matrix. For reasons that will become apparent in § 2, the matrix S\mathbf{S} is referred to as the (discretized) equilibrium operator.

Constructing the reduced system

A key observation of our work is that it is possible to directly form the coefficient matrix in the linear system (3), without first forming the blocks Tj,j′T_{j,j'} in (2). We provide the details of this technique in Section 2, but the idea is quite simple: the jj’th block row in (3) can be written as

uj=Sj,j−1uj−1+Sj,j+1uj+1+f^j,j∈{2,3}.(5)\mathbf{u}_j = \mathbf{S}_{j,j-1}\mathbf{u}_{j-1} + \mathbf{S}_{j,j+1}\mathbf{u}_{j+1} + \widehat{\mathbf{f}}_j,\qquad j \in\{2,3\}. \tag*{(5)}

We refer to the matrices Sj,j−1\mathbf{S}_{j,j-1} and Sj,j+1\mathbf{S}_{j,j+1} as local solution-transfer operators. In the present Dirichlet-trace formulation, they are Dirichlet-to-Dirichlet operators that map trace data on Γj−1\Gamma_{j-1} and Γj+1\Gamma_{j+1} to solution values on the separated interface Γj\Gamma_j. This means that we can consider a local Dirichlet problem on the subdomain Ψj\Psi_j located between Γj−1\Gamma_{j-1} and Γj+1\Gamma_{j+1}, cf. Figure 3, and construct Sj,j−1\mathbf{S}_{j,j-1} and Sj,j+1\mathbf{S}_{j,j+1} directly by simply solving this local problem.

Figure 3. Continuum domain decomposition described in § 2.2.

In fact, the matrices Sj,j−1\mathbf{S}_{j,j-1} and Sj,j+1\mathbf{S}_{j,j+1} can be built using any local BVP solver defined on the double-wide slab Ψj\Psi_j. The only requirement is that the discretizations of the local maps are sufficiently accurate. In our implementation, available at https://github.com/SimonDirckx/SslabLU, we employ a multidomain spectral collocation method. Since the local domains are thin strips, sparse direct solvers are highly efficient even for problems in three dimensions.

In principle, it is not necessary to explicitly form the blocks Sj,j′\mathbf{S}_{j,j'}. If an LU-factorization of the local stiffness matrix Aj\mathbf{A}_j is computed, this can be used to compute the action of Sj,j+1\mathbf{S}_{j,j+1} and Sj,j−1\mathbf{S}_{j,j-1}. We will refer to this approach as the “matrix-free” approach. However, there are a number of scenarios in which one may wish to form the off-diagonal blocks Sj,j′\mathbf{S}_{j,j'} explicitly:

  1. the number of matrix vector-products with S\mathbf{S} is very high (e.g., S\mathbf{S} is used in an iterative solver with many right-hand sides and/or iterations),

  2. the memory footprint of storing all local factorizations is prohibitively large, or

  3. a direct solver for the equilibrium system is to be used.

We return to the first two scenarios in Section 5.1. The development of a direct solver for S\mathbf{S} is currently work in progress.

In case the off-diagonal blocks are formed explicitly, the final component that enables high computational efficiency even in 3D is that, while the blocks Sj,j′\mathbf{S}_{j,j'} are all dense, they can be represented efficiently by exploiting that their off-diagonal blocks have low numerical rank. In this work, we use the Hierarchically Block Separable format of [21]. This format admits fast and simple matrix arithmetic, but its weak-admissibility structure is generally not effective for three-dimensional same-interface boundary operators. Same-interface Dirichlet-to-Neumann and related maps retain a local pseudodifferential singularity. They remain compressible in hierarchical formats with suitable admissibility conditions, but their near-field and adjacent-cluster interactions do not generally have uniformly low rank. By contrast, the matrices Sj,j′\mathbf{S}_{j,j'} act between separated interfaces and approximate integral operators whose kernels are smooth on the entire source-target product. This permits effective use of weak-admissibility HBS even in three dimensions. We obtain the rank structured representations of Sj,j′\mathbf{S}_{j,j'} using the black-box randomized compression technique of [26].

Remark 1. *The use of rank-structured matrices in the context of problems with oscillatory solutions is a delicate matter. It is well known that as the wave-length shrinks, or the solid angle between domains increases relative to the wave number, the ranks of the off-diagonal blocks increase (see [10]). This eventually makes H-matrix arithmetic infeasible. For fixed slab width measured in wavelengths, the required ranks remain controlled in two dimensions (even to the point that the exact rank often is small, see [29 Ch. 21]). In three dimensions, the experiments show mild rank growth over the tested range.

Main features of the reduced formulation

The reduced formulation has several useful features:

Fredholm second-kind structure. For fixed slab width HH, the equilibrium operator has the form identity minus compact kernel integral operators between separated interfaces. As such, its kernels are smooth everywhere at the continuum level, and the resulting operator has the character of a second-kind trace equation.

Conditioning in the compatible SPD setting. For compatible SPD discretizations, the equilibrium matrix S\mathbf{S} is self-adjoint and positive definite in the associated D\mathbf{D}-energy inner product. Equivalently, the symmetrically scaled matrix S~=D−1/2TD−1/2\widetilde{\mathbf{S}} = \mathbf{D}^{-1/2}\mathbf{T}\mathbf{D}^{-1/2} satisfies κ2(S~)≤2CssH−2\kappa_2(\widetilde{\mathbf{S}}) \leq2C_{\mathrm{ss}}H^{-2}. The scaling D\mathbf{D} and its induced norm depend on the compatible discretization, but the bound is uniform with respect to local refinement at fixed HH. The supplementary material reports empirical diagnostics suggesting that the raw Euclidean condition number follows a similar trend in the stencil and collocation realizations tested. Nonsymmetric and oscillatory problems are studied empirically.

Data sparsity. The off-diagonal blocks Sj,j±1\mathbf{S}_{j,j\pm1} in the reduced system S\mathbf{S} are discrete Dirichlet-to-Dirichlet operators between separated interfaces. This is the reason that formats based on weak admissibility, such as HODLR or HBS/HSS, are effective even in three dimensions.

Explicit compressed assembly. A matrix-free implementation would apply each off-diagonal block Sj,j±1\mathbf{S}_{j,j\pm1} of the equilibrium system S\mathbf{S} by performing local solves at every Krylov iteration. We instead construct compressed representations of the dense blocks during the setup phase. This pays the local-solve cost up front, enables fast repeated matrix-vector products, and is particularly attractive for multiple right-hand sides or for a future direct solver for the equilibrium system.

High-order local discretizations and parallelism. The local problems are posed on thin slabs, so sparse direct solvers are effective even when high-order (multidomain) spectral discretizations are used. The local LU factorizations and blocks compression are independent from slab to slab, and matrix-vector products with the assembled operator are naturally parallel.

Connection to prior work and classical domain decompositions

The method outlined in this manuscript belongs to the broad class of substructuring methods; a particular type of domain decomposition methods, in which interior degrees of freedom are eliminated and a reduced problem is posed as an equilibrium equation using interface maps. Standard references include [32, 34]. Classical substructuring methods arise from non-overlapping formulations where the interface maps are discrete Poincaré–Steklov maps. These can be Dirichlet-to-Neumann maps, as in § 1.1, but Robin-to-Robin and impedance-to-impedance operators can also be used. For classical substructuring methods, the resulting equilibrium systems contain self-interactions, i.e., maps between interfaces and themselves. Because these operators are pseudodifferential, their same-interface kernels are locally singular and are less amenable to weak-admissibility compression. Appendix § 10 compares the Dirichlet-to-Neumann, impedance-to-impedance, and overlapping equilibrium formulations for the numerical example introduced in § 6.2. In contrast to the classical non-overlapping substructuring methods, our method considers an overlapping formulation that only ever constructs interface maps between separated interfaces. In this sense, it is closely related to the local Dirichlet solves underlying Schwarz’ original method [31]. Recently, there has been renewed interest in overlapping substructuring methods, as, in e.g., [8]. In contrast to the method there, we consider a broad class of local discretizations and study the compressibility of the resulting interface operators. We do not consider Schwarz iterations or coarse space correction here. In contrast, we iterate on the global equilibrium system.

The discrete equilibrium system S\mathbf{S} can be viewed algebraically as a preconditioned Schur-complement, but its blocks Sj,j±1\mathbf{S}_{j,j\pm1} also have a direct continuum interpretation as local Dirichlet-to-Dirichlet maps: operators mapping data from one interface to solution values on a separated interface. This separation removes the kernel singularity present in the non-overlapping formulation.

For wave problems, domain decomposition methods often use transmission conditions designed to reduce internal numerical resonances. This includes optimized Schwarz methods, sweeping preconditioners, polarized traces and impedance-to-impedance maps [13, 14, 41, 42, 16, 19, 9]. For oscillatory problems, the solution-transfer formulation separates refinement-induced stiffness from frequency-dependent stability. At fixed frequency and fixed slab width, local refinement approximates a fixed interface equation built from local solution maps. Frequency-dependent effects, including proximity to local or global resonances, remain. The Helmholtz experiments investigate this behavior empirically. Combining the separated-interface viewpoint with wave-adapted trace variables is a natural direction for future work.

The closest precursor to the present work is “SlabLU”, the slab-based direct solver of [40] which also uses high-order multidomain solvers, randomized compression, and rank-structured H\mathcal{H}-matrix algebra, but uses a non-overlapping slab decomposition. The present work introduces overlap and replaces the same-interface blocks of the non-overlapping formulation by Dirichlet-to-Dirichlet solution-transfer maps between separated interfaces.

Outline

Our manuscript is structured as follows: in § 2 the reduced equilibrium system is derived numerically and analytically. Its construction using local solvers and randomized compression is outlined. § 3 establishes the continuum second-kind structure and stability under convergent trace approximation. § 4 analyzes compatible SPD discretizations and proves a conditioning bound in the natural energy norm that depends on the slab width, but not on the local resolution. In section 5 we analyze the complexity of our method and compare it to the non-overlapping and matrix-free approach. In section 6 we test our method on illustrative and challenging numerical experiments.

Derivation of the reduced linear system

This section describes how we construct the reduced linear system (1.3) that forms the foundation of our method. Throughout this section, we assume that the computational domain Ω\Omega in (1.1) has been tessellated into Nds+1N_{\mathrm{ds}}+1 thin slabs separated by some interfaces {Γj}j=1Nds\{\Gamma_j\}_{j=1}^{N_{\mathrm{ds}}}, forming NdsN_{\mathrm{ds}} double slabs {Ψj}j=1Nds\{\Psi_j\}_{j=1}^{N_{\mathrm{ds}}} (cf. Figure 1). Our objective is to build the blocks in the coefficient matrix in (1.3), as well as the equivalent reduced loads. We restrict our attention in this manuscript to the case of equispaced slabs. For irregularly spaced slabs the derivations in this Section as well as § 3 carry through unchanged, but we make no claim about the conditioning (see § 4) in this case.

We will start in § 2.1 with showing how one could in principle form the reduced system using classical linear algebraic techniques. This path connects our treatment to standard domain decomposition techniques. We then describe an alternative, more computationally efficient, path in § 2.2 and § 2.3.

A numerical derivation

For purposes of illustration, let us revisit the toy problem introduced in § 1.1 where we split the unit square Ω=[0,1]2\Omega= [0,1]^2 into five thin strips, and then discretize (1) using the five-point finite difference stencil on a regular grid such as the one shown in Figure 2. This results in a linear system

Au=b\mathbf{A}\mathbf{u} = \mathbf{b}

where A\mathbf{A} is a sparse matrix, where u\mathbf{u} holds the values of the approximate solution at the interior grid points, and where b\mathbf{b} holds the information from the boundary condition ff and the body load gg.

To derive the first reduced linear system (2), we collect the indices in the mesh separators into the index vector

J=J1∪J2∪J3∪J4,J = J_1 \cup J_2 \cup J_3 \cup J_4,

cf. Figure 2. All remaining interior indices are listed in the complement JcJ^c. Performing one step of block Gaussian elimination, we eliminate all nodes in the interiors of the slabs. The resulting matrix T\mathbf{T} in (2) is then simply the Schur complement

T=A(J,J)−A(J,Jc)A(Jc,Jc)−1A(Jc,J).\mathbf{T} = \mathbf{A}(J,J) - \mathbf{A}(J,J^c)\mathbf{A}(J^c,J^c)^{-1}\mathbf{A}(J^c,J).

The matrix T\mathbf{T} is block tridiagonal, as any two interfaces Γj\Gamma_j and Γj′\Gamma_{j'} are disconnected if ∣j−j′∣>1|j-j'|>1. As spelled out in § 1.1, the linear system (3) is obtained by simply applying block diagonal pre-conditioning to (2). In other words, the blocks in S\mathbf{S} are given by

Sj,j′=−Tj,j−1Tj,j′=−RjA(Ij,Ij)−1A(Ij,Jj′)(6)S_{j,j'}=-T_{j,j}^{-1}T_{j,j'}=-R_jA(I_j,I_j)^{-1}A(I_j,J_{j'}) \tag*{(6)}

in which IjI_j are the DOFs internal to Ψj\Psi_j, and RjR_j is the restriction to JjJ_j (viewed as a subset of IjI_j). From the second part of equation (6) we see that Sj,j′S_{j,j'} behaves like a solution operator, followed by a restriction operator. If the blocks of S\mathbf{S} are to be built explicitly (i.e. we do not use a matrix-free approach), we could in principle do this by first forming T\mathbf{T}, and then evaluating the formula (6). In practice, this would be very expensive for large scale problems in 3D, as all blocks in T\mathbf{T} are dense. It is possible to exploit rank deficiencies in the off-diagonal blocks of Tj,jT_{j,j} and Tj,j′T_{j,j'} and use, e.g., H-matrix algebra, but a key observation of our work is that S\mathbf{S} is far more compressible than T\mathbf{T}, so we will avoid ever forming T\mathbf{T}; § 2.2 describes how.

An analytic derivation

In this section, we take a different path towards deriving the reduced linear system that starts with a domain decomposition of the continuum problem (1), before discretization. To simplify the discussion, we stick to the simple toy problem where a square Ω=[0,1]2\Omega= [0,1]^2 has been tessellated into five thin slabs with interfaces {Γr}r=14\{\Gamma_r\}_{r=1}^{4}, as shown in Figure 3(a). We assume that the global problem and each of the local problems is well-posed. Standard techniques for decomposing the full problem (1) into smaller disconnected subproblems typically involve enforcing continuity of potentials and normal derivatives across domain boundaries, and involve forming Dirichlet-to-Neumann operators (or other Poincaré–Steklov operators such as Impedance-to-Impedance maps) for each of the subdomains. A challenge in this framework is that all boundary operators involve integral or pseudo-integral operators that have strong singularities at the diagonal. Our objective is to find an alternative formulation that involves only integral operators with smooth kernels.

To simplify the presentation, let us initially consider a problem where the Dirichlet data on the top and the bottom boundaries are both zero. We will soon return to the general case.

For the local slab pair, we write

Ψj=Ωj(α)∪Ωj(β),(7)\Psi_j = \Omega_j^{(\alpha)} \cup\Omega_j^{(\beta)}, \tag*{(7)}

where Ωj(α)\Omega_j^{(\alpha)} and Ωj(β)\Omega_j^{(\beta)} are the left and right halves of the double-wide strip Ψj\Psi_j.

As a first step, let us for each interface Γj\Gamma_j consider a local Dirichlet problem defined on the double wide strip Ψj\Psi_j that is enclosed between Γj−1\Gamma_{j-1} and Γj+1\Gamma_{j+1}, as shown in Figure 3(b). Suppose that the values of the solution to (1) at the left and the right boundaries, uj−1u_{j-1} and uj+1u_{j+1}, are known. Then the solution is uniquely determined everywhere inside Ψj\Psi_j, and in particular on the line Γj\Gamma_j. In other words, there exist linear operators Sj,j−1S_{j,j-1} and Sj,j+1S_{j,j+1} called the solution operators such that

uj(x)=[Sj,j−1uj−1](x)+[Sj,j+1uj+1](x).u_j(x) = [S_{j,j-1}u_{j-1}](x) + [S_{j,j+1}u_{j+1}](x).

To be precise, if we let G(j)(x,y)G^{(j)}(x,y) denote the Poisson kernel for A\mathcal{A} in Ψ(j)\Psi^{(j)}, then the solution operators take the form

[Sj,j−1uj−1](x)=∫Γj−1G(j)(x,y)uj−1(y) dy,(8)[S_{j,j-1}u_{j-1}](x) = \int_{\Gamma_{j-1}} G^{(j)}(x,y)u_{j-1}(y)\,\mathrm{d}y, \tag*{(8)}

and

[Sj,j+1uj+1](x)=∫Γj+1G(j)(x,y)uj+1(y) dy.(9)[S_{j,j+1}u_{j+1}](x) = \int_{\Gamma_{j+1}} G^{(j)}(x,y)u_{j+1}(y)\,\mathrm{d}y. \tag*{(9)}

The measure G(j)(x,y) dyG^{(j)}(x,y)\,\mathrm{d}y is also called the harmonic measure of A\mathcal{A} in Ψ(j)\Psi^{(j)}. Provided the Dirichlet Green’s functions of A\mathcal{A} exist in Ψ(j)\Psi^{(j)} (which is always true for symmetric positive definite elliptic PDE operators, see [12]), the property follows from Green’s second identity. If the coefficients of A\mathcal{A} are smooth, then, since xx and yy are never close to each other in (8) and (9), the Poisson kernels in these integral operators are smooth (see [18 Thm. 6.17]).

For the general loaded Poisson problem with nonzero Dirichlet boundary conditions, the solution uju_j at interface Γj\Gamma_j can be written as

uj=Sj,j−1uj−1+Sj,j+1uj+1+f^j(10)u_j = S_{j,j-1}u_{j-1} + S_{j,j+1}u_{j+1} + \hat{f}_j \tag*{(10)}

where f^j\hat{f}_j is the restriction to Γj\Gamma_j of the solution to the original boundary value problem (1) restricted to Ψj\Psi_j, with zero Dirichlet conditions on {Γj−1,Γj+1}\{\Gamma_{j-1},\Gamma_{j+1}\}. Figure 4 shows a diagram illustrating this principle. Re-writing equation (10) we obtain the equilibrium equations

Figure 4. Illustration of the solution operator principle for general configurations, with nonzero boundary conditions (blue) and load (gray).

−Sj,j−1uj−1+uj−Sj,j+1uj+1=f^j(11)-S_{j,j-1}u_{j-1}+u_j-S_{j,j+1}u_{j+1}=\hat{f}_j \tag*{(11)}

which we can accumulate into

S[u1u2u3u4]=[f^1f^2f^3f^4],whereS=[I−S1,2−S2,1I−S2,3−S3,2I−S3,4−S4,3I].(12)\mathcal{S} \begin{bmatrix} u_1\\ u_2\\ u_3\\ u_4 \end{bmatrix} = \begin{bmatrix} \hat{f}_1\\ \hat{f}_2\\ \hat{f}_3\\ \hat{f}_4 \end{bmatrix}, \qquad \text{where}\qquad \mathcal{S}= \begin{bmatrix} \mathcal{I} & -S_{1,2} & &\\ -S_{2,1} & \mathcal{I} & -S_{2,3} &\\ & -S_{3,2} & \mathcal{I} & -S_{3,4}\\ & & -S_{4,3} & \mathcal{I} \end{bmatrix}. \tag*{(12)}

For this reason S\mathcal{S} is called the equilibrium operator. Of course in practice we do not have access to the Green’s kernel, but the discretized solution operators Sj,j′\mathbf{S}_{j,j'} can be computed as

Sj,j′=−RjAj(I,I)−1Aj(I,J)Rj′∗(13)\mathbf{S}_{j,j'}=-\mathbf{R}_j\mathbf{A}_j(I,I)^{-1}\mathbf{A}_j(I,J)\mathbf{R}_{j'}^{*} \tag*{(13)}

where Aj\mathbf{A}_j is the local stiffness matrix for Ψj\Psi_j, i.e., the discretization of the PDE operator in the double-wide slab Ψj\Psi_j, II and JJ are its (local) interior and boundary DOFs, and Rj\mathbf{R}_j and Rj′∗\mathbf{R}_{j'}^{*} denote the restrictions (locally in Ψj\Psi_j and ∂Ψj′\partial\Psi_{j'} respectively) to interface Γj\Gamma_j and Γj′\Gamma_{j'} respectively. To be explicit, Aj\mathbf{A}_j can be derived from a global discretization, but in our implementation it will be constructed separately for each double-wide slab Ψj\Psi_j.

Remark 2. In principle, even if the original boundary value problem (1) is not degenerate, it can still happen that one of the local problems is either degenerate or highly unstable. In practice, we have never observed this to happen despite extensive numerical experiments. However, a code targeted at oscillatory problems could be designed to either use other boundary conditions (e.g. impedance), or to deploy an explicit numerical check for ill-posedness and a mechanism to rectify this as needed.

Discretization of the local problem

The local Dirichlet problem described in § 2.2 can in principle be solved with a wide variety of discretization techniques and elliptic solvers. Our formulation is therefore not tied to the particular local discretizations (and corresponding local stiffness matrices {Aj}j\{\mathbf{A}_j\}_j), and not tied to the chosen local solvers. All that is required is that the local discretizations are suitably compatible. By this we mean that the discretizations of Γj\Gamma_j in each of the double-wide slabs that intersects with Γj\Gamma_j (that is, Ψj−1\Psi_{j-1}, Ψj\Psi_j and Ψj+1\Psi_{j+1}) are the same. In principle this requirement can be relaxed through the use of interpolation operators between the various discretizations, but we will not consider this in our manuscript. The H\mathcal{H}-matrix compression technique considered in this article imposes the additional restriction that all interfaces {Γj}j=1Nds\{\Gamma_j\}_{j=1}^{N_{\mathrm{ds}}} are discretized isomorphically (see § 2.4). This requirement can be lifted through the use of more involved hierarchical matrix formats, but for the applications here it is not restrictive.

For the high-order experiments in § 6, we use a multidomain spectral collocation technique known as Hierarchical Poincaré–Steklov (HPS) [27, 20] (cf. also [30]). Specifically, we use the implementation from [25]. Following [39], we combine this discretization with a local sparse solver, which is particularly efficient in the present context because the local domains are thin. This HPS implementation is briefly summarized in Figure 5; for further details, see [29 Ch. 25].

Figure 5. The local boundary value problem on each double-wide slab Ψj\Psi_j is solved using a multidomain high order spectral method where the slab is tessellated into small cells. On each square, a Chebyshev grid with p×pp \times p nodes is placed (shown for p=6p = 6). The PDE is enforced directly via spectral differentiation and collocation at each node that is interior to a cell (black). At each edge node (red), continuity of normal derivatives is enforced via spectral differentiation. Zero Dirichlet conditions are enforced at the green nodes, and general Dirichlet conditions are enforced at the blue nodes. Corner nodes (gray) are inactive. See [25] for more details. Illustration of the discretization technique described in § 2.3 for discretizing the local boundary value problems introduced in § 2.2.

Rank structure of the off-diagonal blocks

For small two-dimensional problems, one can form the off-diagonal blocks Sj,j−1\mathbf{S}_{j,j-1} and Sj,j+1\mathbf{S}_{j,j+1} in the reduced system (3) densely, regardless of the local solver used to approximate the double-slab Dirichlet maps. However, this dense formation becomes impractical in three dimensions, and even in two dimensions it can become expensive as the number of interfaces or the local resolution on the subdomains grows.

To overcome this problem, we use that the discretized Dirichlet-to-Dirichlet operators inherit exploitable structure from the integral operators (8) and (9). In particular, the off-diagonal blocks of the Sj,j′\mathbf{S}_{j,j'}-matrices tend to have very low numerical rank, which means that they can efficiently be represented as rank-structured matrices. The idea is to, based on some hierarchical clustering of the DOFs, divide a large dense matrix into a moderate number of blocks in such a way that each block is either of low numerical rank, or is sufficiently small that it can be handled densely. The low-rank matrix blocks correspond to cluster-cluster interactions that are considered ‘well-separated’, in the sense that one expects the local solution kernel from (8) and (9) to be smooth. Various such hierarchical matrix (H\mathcal{H}-matrix) formats can be used for this purpose. In this manuscript, we focus on hierarchical matrices with weak admissibility. An illustration of a hierarchical matrix with weak admissibility is given in Figure 6.

Figure 6. Example of a rank-structured matrix with weak admissibility. Each off-diagonal block (gray) has low numerical rank, and each diagonal block (red) is treated as dense. The tessellation pattern shown is just one example among many possible ones. Illustration of a representative rank-structured matrix, such as an ‘H\mathcal{H}-matrix’, a ‘HODLR matrix’ as well as an ‘HBS matrix’.

Foundational work in this area was done by Hackbusch and co-workers using the so called H\mathcal{H}- and H2\mathcal{H}^{2}-matrix formats [22, 5, 23, 7, 6]. However, we will use a simpler format, that for our set-up is faster and more efficient: Hierarchically Block Separable (HBS) matrices (sometimes referred to as Hierarchically Semi Separable (HSS)) [28, 21, 38, 36, 37, 4].

We will not go into detail here on exactly how HBS matrices are constructed, but a detailed description can be found in [26]. For the purposes of this text, it suffices to know that an HBS compression of a block Sj,j±1∈RN×N\mathbf{S}_{j,j\pm1} \in\mathbb{R}^{N\times N} of hierarchical rank kk can be computed from 2s=O(k)2s = O(k) samples Y=Sj,j±1Ω\mathbf{Y} = \mathbf{S}_{j,j\pm1}\mathbf{\Omega} and Z=Sj,j±1∗Ψ\mathbf{Z} = \mathbf{S}_{j,j\pm1}^{*}\mathbf{\Psi}, where Ω,Ψ∈RN×s\mathbf{\Omega}, \mathbf{\Psi} \in\mathbb{R}^{N\times s} are Gaussian i.i.d. matrices. Once constructed, the memory footprint of an HBS matrix and the cost for one matrix-vector apply are both O(kN)O(kN). The HBS format we use recursively builds a hierarchical approximation based on a shared cluster tree for both Γj\Gamma_j and Γj′\Gamma_{j'}; this is somewhat restrictive, requiring the DOF sets of Γj\Gamma_j and Γj′\Gamma_{j'} to be isomorphic. This requirement can be lifted by moving to more complicated Hierarchical matrix formats, but for the problems considered here the HBS format is not restrictive.

We stress again that in this manuscript we compress blocks that correspond to separated surfaces of source and target points, Γj′\Gamma_{j}' and Γj\Gamma_j. This means that our definition of weak admissibility aligns algebraically with the usual definition of weak admissibility for HBS matrices (i.e., only the diagonal blocks of the Sj,j′\mathbf{S}_{j,j'} are considered dense), but geometrically it differs slightly from the usual definition (see [29 Ch. 15]). Instead of cluster interactions being considered inadmissible only if the clusters are adjacent, we consider them to be inadmissible if they are of minimal distance, as shown in Figure 7. For the 3D case, to our knowledge, this manuscript presents the first use of the randomized HBS compression method from [26] for surfaces in 3D.

Figure 7. Illustration of the far field of a cluster τ\tau with weak admissibility in the S-formulation.

Remark 3. The effectiveness of basic HBS compression for Sj,j±1\mathbf{S}_{j,j\pm1} crucially relies on the validity of weak admissibility (see [29 Ch. 15]). This assumption is not always valid, especially in 3D, as the slab width HH tends to zero. Indeed, it is known in H-matrix techniques for the Helmholtz equation (see, e.g., [10]) that for the discretizations of boundary integral operators weak admissibility does not suffice in the high-frequency regime. We return to this in § 5.

With local compression enabled, the global equilibrium systems T and S have the structures shown in Figure 8. Here, weak admissibility can be used for the off-diagonal blocks of T and S since these correspond to interactions between separated interfaces, but since the block diagonal of T consists of same-interface DtN maps, weak admissibility no longer suffices there (see also Figure 9). For these blocks, strong admissibility is required. Under strong admissibility, a block is treated as low rank only when the corresponding source and target clusters satisfy a prescribed geometric separation condition relative to their diameters. Especially in 3D, this significantly increases the memory footprint and computational complexity required to compress these blocks.

Figure 8. The structure of the global equilibrium systems T and S with hierarchical compression.

Comparison of solution error for formulations S and T as a function of slab width H and the HBS compression rank

Figure 9. Comparison of solution error for formulations S and T as a function of slab width HH and the HBS compression rank.

Remark 4. As already mentioned in § 1.2, one alternative to forming the blocks of T\mathbf{T} or S\mathbf{S} explicitly is the “matrix-free” approach: they are applied using only the factorized interior solver Aj\mathbf{A}_j in Ψj\Psi_j. This is the standard way of constructing iterative solvers based on substructuring domain decompositions (see, e.g., [34]). We return to this topic in § 5.

Summary of the Proposed Method

We now summarize our procedure for constructing the discrete solution maps Sj,j′\mathbf{S}_{j,j'} (local assembly) and the discretized equilibrium operator S\mathbf{S} (global assembly). The ingredients for our procedure are:

  1. a domain Ω\Omega in R2\mathbb{R}^2 or R3\mathbb{R}^3,

  2. overlapping double-wide slabs {Ψj}j=1Nds\{\Psi_j\}_{j=1}^{N_{\mathrm{ds}}} covering Ω\Omega,

  3. local stiffness matrices {Aj}j=1Nds\{\mathbf{A}_j\}_{j=1}^{N_{\mathrm{ds}}} (these can be computed ‘on the fly’).

With IjI_j and JjJ_j the local interior and boundary DOFs in Ψj\Psi_j, set Cj⊂IjC_j \subset I_j and Jj,j′⊂JjJ_{j,j'} \subset J_j to correspond to the central interface Γj\Gamma_j and the interfaces Γj′\Gamma_{j'} on the boundary of Ψj\Psi_j respectively.4 The solution map is given by

Sj,j′=−RCjAj(Ij,Ij)−1Aj(Ij,Jj,j′).\mathbf{S}_{j,j'}=-\mathbf{R}_{C_j}\mathbf{A}_j(I_j,I_j)^{-1}\mathbf{A}_j(I_j,J_{j,j'}).

Of course inverting the interior stiffness matrix in this way is computationally undesirable, so instead Aj(Ij,Ij)\mathbf{A}_j(I_j,I_j) is factorized into Aj(Ij,Ij)=LjUj\mathbf{A}_j(I_j,I_j)=\mathbf{L}_j\mathbf{U}_j.5 As spelled out in § 2.4, we do not compute Sj,j′\mathbf{S}_{j,j'} densely, but approximate it using HBS compression, implemented using the method from [26].

The local and global assembly are summarized in Algorithm 2.1 and 2.2.

Algorithm 2.1 Local Sj,j′\mathbf{S}_{j,j'}-matrix construction
Input interface DOF sets Cj⊂IjC_j \subset I_j, Jj,j′⊂JjJ_{j,j'} \subset J_j, stiffness matrix Aj\mathbf{A}_j, factorization Aj(Ij,Ij)=LjUj\mathbf{A}_j(I_j,I_j)=\mathbf{L}_j\mathbf{U}_j, rank and tree (kj,Tj)(k_j,\mathcal{T}_j)
Output Solution operator Sj,j′\mathbf{S}_{j,j'}
1: nj←∣Cj∣n_j \leftarrow|C_j|▹\triangleright We assume ∣Jj,j′∣=nj|J_{j,j'}|=n_j
2: s←αkj+qs \leftarrow\alpha k_j+q▹\triangleright sample count; typically q=10q=10, α=3\alpha=3
3: draw Ω,Ψ∼N(0,1)nj×s\boldsymbol{\Omega},\boldsymbol{\Psi}\sim\mathcal{N}(0,1)^{n_j\times s}
4: Y←−RCjAj−1Aj(Ij,Jj,j′)Ω\mathbf{Y}\leftarrow-\mathbf{R}_{C_j}\mathbf{A}_j^{-1}\mathbf{A}_j(I_j,J_{j,j'})\boldsymbol{\Omega}▹\triangleright Computed using the LU-factorization of Aj\mathbf{A}_j
5: Z←−Aj(Ij,Jj′)Aj−1RCjTΨ\mathbf{Z}\leftarrow-\mathbf{A}_j(I_j,J_{j'})\mathbf{A}_j^{-1}\mathbf{R}_{C_j}^{T}\boldsymbol{\Psi}
6: Sj,j′←HBS(Ω,Ψ,Y,Z,kj,Tj)\mathbf{S}_{j,j'}\leftarrow HBS(\boldsymbol{\Omega},\boldsymbol{\Psi},\mathbf{Y},\mathbf{Z},k_j,\mathcal{T}_j)▹\triangleright HBS compression from [26]

Table 2.1.

Algorithm 2.2 Total S\mathbf{S}-matrix construction
Input Local double slabs {Ψj}j=1Nds\{\Psi_j\}_{j=1}^{N_{\mathrm{ds}}}, HBS ranks and trees {(kj,Tj)}j=1Nds\{(k_j,\mathcal{T}_j)\}_{j=1}^{N_{\mathrm{ds}}}
Output Discrete equilibrium operator S\mathbf{S}
1: S←I∈R∣JΓ∣×∣JΓ∣\mathbf{S}\leftarrow\mathbf{I}\in\mathbb{R}^{|J_\Gamma|\times|J_\Gamma|}
2: for j=1,…,Ndsj=1,\ldots,N_{\mathrm{ds}} do
3: compute local discretization Aj\mathbf{A}_j
4: factorize Aj(Ij,Ij)=LjUj\mathbf{A}_j(I_j,I_j)=\mathbf{L}_j\mathbf{U}_j
5: compute central interface DOFs Cj⊂IjC_j\subset I_j
6: for j′∈{j−1,j+1}∩{1,…,Nds}j'\in\{j-1,j+1\}\cap\{1,\ldots,N_{\mathrm{ds}}\} do
7: compute interface DOFs Jj,j′⊂JjJ_{j,j'}\subset J_j
8: compute HBS approx. Sj,j′\mathbf{S}_{j,j'} using Algorithm 2.1
9: set corresponding block in S\mathbf{S} to −Sj,j′-\mathbf{S}_{j,j'}
10: end for
11: end for

Table 2.2.

Continuum trace formulation and stability under approximation

The construction in § 2.2 is most naturally viewed at the continuum level. The continuous equilibrium system solves for the unknown solution traces on the internal interfaces, and its off-diagonal blocks are solution-transfer operators in the overlapping double-wide slabs. In this section we first record the fixed-HH Fredholm structure of the resulting trace equation. We then show that standard finite-dimensional trace approximations inherit its stability, and finally account for errors introduced by numerical local solves and rank-structured compression. Symmetry and positive definiteness are not required in this section, as opposed to in § 4, where the conditioning of the equilibrium system is discussed.

Throughout this section, the slab width H>0H > 0 is fixed. We assume that the global boundary value problem and the local Dirichlet problems on the single and double-wide slabs are uniquely solvable. We also assume sufficient regularity, i.e., that the local Dirichlet solution kernels are sufficiently smooth away from the diagonal. For uniformly elliptic second-order differential operators with smooth coefficients this is always satisfied. For indefinite problems, it is additionally required that neither the global problem nor any local problem is resonant.

Fredholm second-kind structure

Let Γ1,…,ΓNds\Gamma_1,\ldots,\Gamma_{N_{\mathrm{ds}}} denote the internal interfaces, and let Ψj\Psi_j be the double slab with central interface Γj\Gamma_j. We use the trace space X=⨁j=1NdsXjX = \bigoplus_{j=1}^{N_{\mathrm{ds}}} X_j with Xj=L2(Γj)X_j = L^2(\Gamma_j). The natural Dirichlet trace space is H1/2(Γj)H^{1/2}(\Gamma_j), but the L2L^2 setting is convenient here because separation of source and target interfaces makes the local solution maps smoothing.

As outlined in § 2.2, the local Dirichlet problems define solution-transfer operators

Sj,j−1:Xj−1→Xj,Sj,j+1:Xj+1→Xj.S_{j,j-1}:X_{j-1}\to X_j,\qquad S_{j,j+1}:X_{j+1}\to X_j.

In the present Dirichlet-trace formulation, these are Dirichlet-to-Dirichlet maps between separated interfaces. Including body loads and physical boundary data gives the row-wise equilibrium equations

−Sj,j−1uj−1+uj−Sj,j+1uj+1=f^j.(14)-S_{j,j-1}u_{j-1}+u_j-S_{j,j+1}u_{j+1}=\widehat{f}_j. \tag*{(14)}

The obvious modifications apply at interfaces adjacent to the physical boundary. In block form,

SHu=(I−KH)u=f^,(15)S_Hu=(\mathcal{I}-K_H)u=\widehat{f}, \tag*{(15)}

where KHK_H contains the solution-transfer operators as its nearest-neighbor off-diagonal blocks.

Proposition 3.1 (Fredholm structure of the trace equation). Under the assumptions stated above, KHK_H is Hilbert–Schmidt, and hence compact, on XX. Consequently, SH=I−KHS_H=\mathcal{I}-K_H is Fredholm of index zero. If the homogeneous global boundary value problem is uniquely solvable, then SHS_H is invertible.

Proof. By equations (8) and (9), each nonzero block of KHK_H is an integral operator whose source variable lies on Γj±1\Gamma_{j\pm1} and whose target variable lies on Γj\Gamma_j. These interfaces are separated by a positive distance for fixed HH. The corresponding solution kernel is therefore smooth on the compact product Γj×Γj±1\Gamma_j\times\Gamma_{j\pm1} and, in particular, is square integrable. Each block Sj,j±1S_{j,j\pm1} is thus Hilbert–Schmidt. Since KHK_H has only finitely many nonzero blocks, it is Hilbert–Schmidt and hence compact. The operator SH=I−KHS_H=\mathcal{I}-K_H is therefore Fredholm of index zero.

It remains to establish injectivity. Suppose that u∈Xu\in X satisfies the homogeneous trace equation SHu=0S_Hu=0. Use the components of uu as Dirichlet data to solve the homogeneous local problems on the double slabs. The equilibrium equations ensure that the trace produced on each central interface Γj\Gamma_j is precisely uju_j. Two neighboring double-slab solutions therefore solve the same homogeneous equation on their common single-slab overlap and have the same Dirichlet data on the boundary of that overlap. Uniqueness of the local Dirichlet problem implies that the two solutions agree there. The local solutions consequently patch together to form a homogeneous solution of the global boundary value problem. Global uniqueness implies that this solution vanishes, and hence u=0u=0. Thus SHS_H is injective; since it is Fredholm of index zero, it is invertible. ∎

The essential spectrum of SH\mathcal{S}_H is therefore the singleton {1}\{1\}. Any other spectral values are isolated eigenvalues of finite multiplicity, with possible accumulation only at 11. Moreover,

SH∗SH=I−KH−KH∗+KH∗KH=I+compact,\mathcal{S}_H^*\mathcal{S}_H=\mathcal{I}-\mathcal{K}_H-\mathcal{K}_H^*+\mathcal{K}_H^*\mathcal{K}_H=\mathcal{I}+\text{compact},

so the singular values away from 11 can likewise accumulate only at 11. This is the fixed-HH second-kind interpretation of the equilibrium formulation.

Finite-dimensional approximation

Consider a sequence of successively more finely refined finite-dimensional trace spaces {Xj}j=1∞\{X_j\}_{j=1}^{\infty}. We assume that these are nested, X1⊂X2⊂⋯⊂XX_1\subset X_2\subset\cdots\subset X, and that their union is dense in XX. Let Pn∈B(X)P_n\in\mathcal{B}(X) be the orthogonal projection onto XnX_n. Then Pn→IP_n\to\mathcal{I} strongly. Compactness upgrades this convergence to operator-norm convergence after composition with KH\mathcal{K}_H:

∥KH−PnKHPn∥⟶0.(16)\lVert\mathcal{K}_H-P_n\mathcal{K}_HP_n\rVert\longrightarrow0. \tag*{(16)}

Indeed, Pn→IP_n\to\mathcal{I} uniformly on the relatively compact image under KH\mathcal{K}_H of the unit ball, so ∥(I−Pn)KH∥→0\lVert(\mathcal{I}-P_n)\mathcal{K}_H\rVert\to0. Since Pn=Pn∗P_n=P_n^* and KH∗\mathcal{K}_H^* is also compact,

∥KH(I−Pn)∥=∥(I−Pn)KH∗∥→0,\lVert\mathcal{K}_H(\mathcal{I}-P_n)\rVert=\lVert(\mathcal{I}-P_n)\mathcal{K}_H^*\rVert\to0,

and (16) follows.

Define the projected trace operator on XnX_n by SH,n=IXn−PnKH∣Xn\mathcal{S}_{H,n}=\mathcal{I}_{X_n}-P_n\mathcal{K}_H|_{X_n}. For comparison on a common space, extend it to XX by setting S‾H,n=I−PnKHPn\overline{\mathcal{S}}_{H,n}=\mathcal{I}-P_n\mathcal{K}_HP_n. The extended operator acts as the identity on Xn⊥X_n^\perp and restricts to SH,n\mathcal{S}_{H,n} on XnX_n.

Proposition 3.2 (Stability of projected trace operators). Assume that SH\mathcal{S}_H is invertible. Then, for all sufficiently large nn, the extended operator S‾H,n\overline{\mathcal{S}}_{H,n} and the projected operator SH,n\mathcal{S}_{H,n} are invertible. Moreover,

∥S‾H,n−1∥≤∥SH−1∥1−∥SH−1∥∥SH,n−SH∥.(17)\lVert\overline{\mathcal{S}}_{H,n}^{-1}\rVert\leq\frac{\lVert\mathcal{S}_H^{-1}\rVert}{1-\lVert\mathcal{S}_H^{-1}\rVert\lVert\mathcal{S}_{H,n}-\mathcal{S}_H\rVert}. \tag*{(17)}

and

∥SH,n−1∥≤∥S‾H,n−1∥.(18)\lVert\mathcal{S}_{H,n}^{-1}\rVert\leq\lVert\overline{\mathcal{S}}_{H,n}^{-1}\rVert. \tag*{(18)}

In particular, both families of inverse norms are uniformly bounded for sufficiently large nn.

Proof. By (16),

∥S‾H,n−SH∥=∥KH−PnKHPn∥→0.\lVert\overline{\mathcal{S}}_{H,n}-\mathcal{S}_H\rVert=\lVert\mathcal{K}_H-P_n\mathcal{K}_HP_n\rVert\to0.

For sufficiently large nn, the product of this norm with ∥SH−1∥\lVert\mathcal{S}_H^{-1}\rVert is smaller than one. A Neumann-series argument then gives invertibility of S‾H,n\overline{\mathcal{S}}_{H,n} and the bound (17). Since S‾H,n\overline{\mathcal{S}}_{H,n} is the identity on Xn⊥X_n^\perp and restricts to SH,n\mathcal{S}_{H,n} on XnX_n, the projected operator is invertible as well, and (18) follows by restriction.

We next apply this operator stability result to the projected equation for a fixed right-hand side. The following corollary separates the effects of approximating the data and approximating the operator.

Corollary 3.3 (Convergence of projected solutions). Let u∈Xu\in X solve SHu=f\mathcal{S}_Hu=f, and let un∈Xnu_n\in X_n solve

SH,nun=Pnf.\mathcal{S}_{H,n}u_n=P_nf.

Then, for all sufficiently large nn,

∥u−un∥≤∥S‾H,n−1∥(∥(I−Pn)f∥+∥S‾H,n−SH∥∥u∥).(19)\lVert u-u_n\rVert\leq\lVert\overline{\mathcal{S}}_{H,n}^{-1}\rVert\bigl(\lVert(\mathcal{I}-P_n)f\rVert+\lVert\overline{\mathcal{S}}_{H,n}-\mathcal{S}_H\rVert\lVert u\rVert\bigr). \tag*{(19)}

In particular, un→uu_n\to u as n→∞n\to\infty.

Proof. Viewing unu_n as an element of XX, we have

S‾H,n(un−u)=Pnf−S‾H,nu=−(I−Pn)f−(S‾H,n−SH)u.\overline{\mathcal{S}}_{H,n}(u_n-u)=P_nf-\overline{\mathcal{S}}_{H,n}u=-(\mathcal{I}-P_n)f-(\overline{\mathcal{S}}_{H,n}-\mathcal{S}_H)u.

Applying S‾H,n−1\overline{\mathcal{S}}_{H,n}^{-1} gives (19). Strong convergence of PnP_n and operator-norm convergence of S‾H,n\overline{\mathcal{S}}_{H,n} then imply un→uu_n\to u.

The projected construction above provides a stable reference approximation of the continuum equation. A collocation or finite-difference implementation need not be literally obtained by orthogonal projection; instead, the computed operator can be compared with the stable projected operator through a standard perturbation argument (see, e.g., [3 Ch. 3-4]).

Remark 5 (Inexact local solves and compression). Proposition 3.2 provides a stability result that can be used to quantify how errors introduced by numerical local solves and rank-structured compression affect the computed solution. To illustrate, let

S^H,n=IXn−K^H,n\widehat{S}_{H,n}=I_{X_n}-\widehat{K}_{H,n}

denote the operator obtained after trace discretization, numerical local Dirichlet solves, quadrature or collocation, and rank-structured compression, and set

ηn:=∥S^H,n−SH,n∥.\eta_n:=\left\|\widehat{S}_{H,n}-S_{H,n}\right\|.

If ηn∥SH,n−1∥<1\eta_n\left\|S_{H,n}^{-1}\right\|<1, then the standard Neumann-series perturbation argument shows that S^H,n\widehat{S}_{H,n} is invertible and

∥S^H,n−1∥≤∥SH,n−1∥1−ηn∥SH,n−1∥(20)\left\|\widehat{S}_{H,n}^{-1}\right\|\leq\frac{\left\|S_{H,n}^{-1}\right\|}{1-\eta_n\left\|S_{H,n}^{-1}\right\|} \tag*{(20)}

Moreover, if SH,nun=PnfS_{H,n}u_n=P_nf and S^H,nu^n=f^n\widehat{S}_{H,n}\widehat{u}_n=\widehat{f}_n, then

∥u^n−un∥≤∥SH,n−1∥1−ηn∥SH,n−1∥(∥f^n−Pnf∥+ηn∥un∥).(21)\left\|\widehat{u}_n-u_n\right\|\leq\frac{\left\|S_{H,n}^{-1}\right\|}{1-\eta_n\left\|S_{H,n}^{-1}\right\|}\left(\left\|\widehat{f}_n-P_nf\right\|+\eta_n\left\|u_n\right\|\right). \tag*{(21)}

The point here is not to estimate the individual error terms; rather, (3.8) shows how they control the difference between the computed solution and the stable projected solution, once the local solves and compression attain sufficient accuracy.

The results in this section concern refinement of a fixed continuum trace equation at fixed physical slab width HH. They do not quantify how ∥SH−1∥\left\|S_H^{-1}\right\| depends on HH, on the frequency in an oscillatory problem, or on proximity to local or global resonances. § 4 addresses the HH-dependence of the conditioning for compatible symmetric positive-definite discretizations. In that setting, the locally constructed solution-transfer equation is algebraically equivalent to a block-scaled Schur complement and admits a quantitative energy estimate.

Compatible SPD discretizations

§ 2.1 and § 2.2 introduced two routes to the reduced interface equation. Conceptually, we regard the continuum-first route of § 2.2 as primary: first partition the domain into overlapping double slabs and define the local solution-transfer operators, and then approximate those operators using suitable local discretizations. This is in contrast to the “discretize first, then eliminate degrees algebraically by forming Schur complements” approach of § 2.1. In many standard settings, the order of these operations can be reversed without changing the resulting discrete interface equation. This occurs, for example, for standard low-order finite differences on matching grids and for conforming finite-element discretizations with matching trace spaces, when the local discrete spaces and operators are obtained by restriction from a single global discretization. One may then first discretize the global problem, eliminate the slab interiors, and form a block-scaled Schur complement. We refer to such a realization as a compatible discretization.

Throughout this section, we restrict attention to the case in which the boundary value problem (1.1) is symmetric and coercive, and the compatible discretization matrix is symmetric positive definite (SPD). The continuum analysis in § 3 does not require this restriction or the equivalence described above. The purpose of the present section is to exploit the compatible SPD setting, where it supplies a natural discrete energy structure and a quantitative estimate of the dependence on the slab width HH.

A compatible Schur-complement realization

Let Au=bA\mathbf{u}=\mathbf{b} be the linear system obtained from a compatible SPD discretization of the boundary value problem (1.1). Partition the active degrees of freedom into the interface set J\mathcal{J}, corresponding to Γ1,…,ΓNds\Gamma_1,\ldots,\Gamma_{N_{\mathrm{ds}}}, and the remaining slab-interior set II. (In Figure 2, JJ are the red nodes, and II are the blue nodes.) Boundary values prescribed on the physical boundary are understood to have been moved to the right-hand side. Eliminating the interior degrees of freedom gives the interface Schur complement

TH=AJJ−AJIAII−1AIJ.(22)T_H = A_{JJ} - A_{JI}A_{II}^{-1}A_{IJ}. \tag*{(22)}

Since AA is SPD, so is THT_H, and so is each of its principal diagonal blocks. Split J=J1∪⋯∪JNdsJ=J_1\cup\cdots\cup J_{N_{\mathrm{ds}}} by interface, and define

DH=diag⁡(T11,…,TNds,Nds).(23)D_H=\operatorname{diag}(T_{11},\ldots,T_{N_{\mathrm{ds}},N_{\mathrm{ds}}}). \tag*{(23)}

The corresponding block-scaled interface matrix is

SH=DH−1TH.(24)S_H=D_H^{-1}T_H. \tag*{(24)}

For a slab decomposition, THT_H is block tridiagonal. Compatibility of the global and local discretizations implies that the off-diagonal blocks −Tjj−1Tj,j±1-T_{jj}^{-1}T_{j,j\pm1} are exactly the discrete solution-transfer operators obtained by solving the corresponding local Dirichlet problems on the double slab Ψj\Psi_j. Thus (24) is a discrete realization of the continuum trace equation from § 3; the Schur-complement construction is a tool for analysis, rather than a prerequisite for computing the method.

The Schur complement has the variational characterization (see, e.g., [33])

vTTHv=min⁡w(J)=vwTAw.(25)\mathbf{v}^{T}T_H\mathbf{v}=\min_{\mathbf{w}(J)=\mathbf{v}}\mathbf{w}^{T}A\mathbf{w}. \tag*{(25)}

Hence vTTHv\mathbf{v}^{T}T_H\mathbf{v} is the energy of the global discrete AA-harmonic extension of the interface data v\mathbf{v}. Similarly,

vTDHv=∑j=1NdsvjTTjjvj\mathbf{v}^{T}D_H\mathbf{v}=\sum_{j=1}^{N_{\mathrm{ds}}}\mathbf{v}_j^{T}T_{jj}\mathbf{v}_j

is the corresponding additive local interface energy. The conditioning estimate below follows from comparing these two energies.

Energy scaling and red-black structure

Although SH=DH−1THS_H=D_H^{-1}T_H is generally not symmetric in the Euclidean inner product, it is symmetric positive definite in the natural DHD_H-inner product.

Proposition 4.1 (Energy symmetry and symmetric scaling). Let THT_H and DHD_H be defined by (22) and (23). Then SH=DH−1THS_H=D_H^{-1}T_H is self-adjoint and positive definite in the inner product

⟨x,y⟩DH=xTDHy.\langle\mathbf{x},\mathbf{y}\rangle_{D_H}=\mathbf{x}^{T}D_H\mathbf{y}.

Equivalently, SHS_H is similar to the Euclidean SPD matrix

S~H=DH−1/2THDH−1/2.(26)\widetilde{S}_H=D_H^{-1/2}T_HD_H^{-1/2}. \tag*{(26)}

Proof. For any vectors x\mathbf{x} and y\mathbf{y}, ⟨SHx,y⟩DH=xTTHy=⟨x,SHy⟩DH\langle S_H\mathbf{x},\mathbf{y}\rangle_{D_H}=\mathbf{x}^{T}T_H\mathbf{y}=\langle\mathbf{x},S_H\mathbf{y}\rangle_{D_H}, and ⟨SHx,x⟩DH=xTTHx>0\langle S_H\mathbf{x},\mathbf{x}\rangle_{D_H}=\mathbf{x}^{T}T_H\mathbf{x}>0 for every nonzero x\mathbf{x}. The similarity relation SH=DH−1/2S~HDH1/2S_H=D_H^{-1/2}\widetilde{S}_HD_H^{1/2} then gives the equivalent Euclidean SPD representation.

Writing ∥x∥DH2=xTDHx\lVert\mathbf{x}\rVert_{D_H}^{2}=\mathbf{x}^{T}D_H\mathbf{x} and using the induced operator norm, the natural DHD_H-condition number is

κDH(SH):=∥SH∥DH∥SH−1∥DH=κ2(S~H).(27)\kappa_{D_H}(S_H):=\lVert S_H\rVert_{D_H}\lVert S_H^{-1}\rVert_{D_H}=\kappa_2(\widetilde{S}_H). \tag*{(27)}

This energy condition number is the quantity controlled below.

The upper spectral bound has a useful red-black interpretation. For a nonperiodic slab chain, color the odd-numbered interfaces red and the even-numbered interfaces black. The same two-coloring applies to a periodic decomposition when NdsN_{\mathrm{ds}} is even. After this ordering,

TH=[TrrTrbTbrTbb],DH=[Trr00Tbb],T_H= \begin{bmatrix} T_{\mathrm{rr}} & T_{\mathrm{rb}}\\ T_{\mathrm{br}} & T_{\mathrm{bb}} \end{bmatrix}, \qquad D_H= \begin{bmatrix} T_{\mathrm{rr}} & 0\\ 0 & T_{\mathrm{bb}} \end{bmatrix},

where Trr\mathbf{T}_{rr} and Tbb\mathbf{T}_{bb} are block diagonal. Consequently,

SH=[Trr−1000]⏟PrTH+[000Tbb−1]⏟PbTH.(28)\mathbf{S}_H = \underbrace{\begin{bmatrix} \mathbf{T}_{rr}^{-1} & 0 \\ 0 & 0 \end{bmatrix}}_{\mathbf{P}_r} \mathbf{T}_H + \underbrace{\begin{bmatrix} 0 & 0 \\ 0 & \mathbf{T}_{bb}^{-1} \end{bmatrix}}_{\mathbf{P}_b} \mathbf{T}_H. \tag*{(28)}

Direct calculation shows that Pr\mathbf{P}_r and Pb\mathbf{P}_b are idempotent and self-adjoint in the TH\mathbf{T}_H-inner product. Thus each is a TH\mathbf{T}_H-orthogonal projection. They are not, in general, mutually orthogonal.

Proposition 4.2 (Red-black upper bound). For the two-colorable slab decompositions described above,

λmax⁡(S~H)≤2.\lambda_{\max}(\widetilde{\mathbf{S}}_H) \le2.

Proof. Since Pr\mathbf{P}_r and Pb\mathbf{P}_b are orthogonal projections in the TH\mathbf{T}_H-inner product,

∥Pr∥TH≤1,∥Pb∥TH≤1.\|\mathbf{P}_r\|_{\mathbf{T}_H} \le1,\qquad\|\mathbf{P}_b\|_{\mathbf{T}_H} \le1.

Equation (28) therefore gives

ρ(SH)≤∥SH∥TH≤2.\rho(\mathbf{S}_H) \le\|\mathbf{S}_H\|_{\mathbf{T}_H} \le2.

The matrices SH\mathbf{S}_H and S~H\widetilde{\mathbf{S}}_H have the same positive eigenvalues, so the stated bound follows.

Stable splitting and conditioning

The lower spectral bound requires the following standard stable-splitting estimate.

Assumption 1 (Stable splitting). There exists a constant CssC_{\mathrm{ss}}, independent of the local mesh size and the number of degrees of freedom used in each slab, such that

vTDHv≤CssH−2vTTHv(29)\mathbf{v}^{\mathsf{T}}\mathbf{D}_H\mathbf{v} \le C_{\mathrm{ss}}H^{-2}\mathbf{v}^{\mathsf{T}}\mathbf{T}_H\mathbf{v} \tag*{(29)}

for every interface vector v\mathbf{v}. The constant may depend on the ellipticity constants, the global domain, and the regularity of the slab decomposition.

Assumption 1 is a mild and standard requirement for the compatible discretizations considered here. It holds, in particular, for standard low-order finite-difference discretizations on regular grids and for conforming low-order finite-element discretizations on shape-regular meshes; see, e.g., [32, 34]. At the continuum level, estimates of this type are obtained by multiplying the global energy-minimizing extension by a partition of unity subordinate to the overlapping slabs. The gradients of the cutoff functions scale like H−1H^{-1}, producing the factor H−2H^{-2} in the energy estimate. The corresponding discrete estimates follow from the usual stable-decomposition arguments in additive Schwarz theory. For high-order Galerkin or spectral-element discretizations, uniformity in the polynomial order additionally requires the relevant interpolation and decomposition estimates to be pp-stable.

Theorem 4.3 (Energy and spectral bounds). Assume that A\mathbf{A} is SPD, that the interface graph is two-colorable as above, and that Assumption 1 holds. Then

Css−1H2≤λmin⁡(S~H)≤λmax⁡(S~H)≤2.(30)C_{\mathrm{ss}}^{-1}H^2 \le\lambda_{\min}(\widetilde{\mathbf{S}}_H) \le\lambda_{\max}(\widetilde{\mathbf{S}}_H) \le2. \tag*{(30)}

Consequently,

κDH(SH)=κ2(S~H)≤2CssH−2.(31)\kappa_{\mathbf{D}_H}(\mathbf{S}_H)=\kappa_2(\widetilde{\mathbf{S}}_H)\le2C_{\mathrm{ss}}H^{-2}. \tag*{(31)}

In particular, for fixed physical slab width HH, this bound is independent of the local discretization resolution.

Proof. For any nonzero vector z\mathbf{z}, set v=DH−1/2z\mathbf{v}=\mathbf{D}_H^{-1/2}\mathbf{z}. Then

zTS~HzzTz=vTTHvvTDHv.\frac{\mathbf{z}^{\mathsf{T}}\widetilde{\mathbf{S}}_H\mathbf{z}}{\mathbf{z}^{\mathsf{T}}\mathbf{z}} = \frac{\mathbf{v}^{\mathsf{T}}\mathbf{T}_H\mathbf{v}}{\mathbf{v}^{\mathsf{T}}\mathbf{D}_H\mathbf{v}}.

The stable-splitting estimate (29) gives the lower bound

vTTHvvTDHv≥Css−1H2.\frac{\mathbf{v}^{\mathsf{T}}\mathbf{T}_H\mathbf{v}}{\mathbf{v}^{\mathsf{T}}\mathbf{D}_H\mathbf{v}} \ge C_{\mathrm{ss}}^{-1}H^2.

The upper bound follows from Proposition 4.2. The condition-number estimate is then immediate from (27).

Because SH\mathbf{S}_H and S~H\widetilde{\mathbf{S}}_H are similar, they have the same eigenvalues. Hence the spectral ratio

κρ(SH):=λmax⁡(SH)λmin⁡(SH)=κ2(S~H)≤2CssH−2\kappa_\rho(\mathbf{S}_H) := \frac{\lambda_{\max}(\mathbf{S}_H)}{\lambda_{\min}(\mathbf{S}_H)} = \kappa_2(\widetilde{\mathbf{S}}_H) \leq2C_{\mathrm{ss}}H^{-2}

is also uniform under local refinement. This is a spectral statement and, for a nonnormal matrix, need not equal the Euclidean condition number κ2(SH)\kappa_2(\mathbf{S}_H). The supplementary material reports weighted spectral diagnostics for representative stencil and HPS collocation realizations. Over the tested range, the ratio κ2(SH)/κρ(SH)\kappa_2(\mathbf{S}_H)/\kappa_\rho(\mathbf{S}_H) remains close to one, suggesting that the spectral bound is indicative of the Euclidean conditioning in these examples. These observations are empirical and are not used in the proof of Theorem 4.3.

Collocation and oscillatory problems

Rather than a compatible SPD discretization, the HPS implementation used in many of the numerical experiments is a strong-form collocation method. Its raw matrices are generally nonsymmetric and nonnormal in the Euclidean inner product. We therefore interpret HPS through the continuum approximation framework of § 3; the energy-norm theorem above does not apply directly. The supplementary material reports weighted spectral diagnostics for representative HPS and stencil realizations. In the examples studied, the Euclidean condition number tracks the spectral ratio closely.

For oscillatory problems (where positivity is no longer satisfied), the trace formulation separates two effects. At fixed frequency and fixed slab width, the interface equation is built from local solution operators rather than from a discretized differential operator, so local refinement does not by itself introduce the large singular values associated with discretizing an unbounded operator. Frequency-dependent stability, including proximity to global or local resonances, remains a separate issue. The Helmholtz experiments investigate the corresponding behavior empirically.

Computational complexity

In this section, we analyze the complexity of our proposed solver, and compare it to the “matrix-free” and non-overlapping approach.

In what follows, we restrict our attention to the 3D version of our solver, but the same analysis can be applied to the 2D case. The total computational complexity of our proposed method is dominated by the cost for the construction and factorization of the local stiffness matrices on the double-wide slabs {Ψj}j=1Nds\{\Psi_j\}_{j=1}^{N_{\mathrm{ds}}}. We will denote the selected HBS rank by kk.

We analyze the case of sparse direct solvers for the interior slab solves, assuming that nested dissection is used. We analyze additional costs associated with the use of high order discretizations in Remark 7.

Consider a 3D domain, discretized with NN total DOFs. We assume for simplicity that N=n1n2n3N=n_1n_2n_3, with n1n_1 the number of DOFs in the slab direction, and n2=n3n_2=n_3 the number of DOFs in the yy and zz-axis. There are three primary costs to analyze:

  1. the cost of factorizing each slab volume,

  2. the cost of compressing S\mathbf{S} using rank structure, and

  3. the cost of applying S\mathbf{S} within GMRES iterations to compute the interface solution.

Sparse Factorization of slab volumes. The domain is divided into NdsN_{\mathrm{ds}} subdomains, and we impose that the slabs are thin, such that 2n1Nds≤n2=n3\frac{2n_1}{N_{\mathrm{ds}}} \leq n_2=n_3. Each double-wide slab volume therefore contains 2n1Nds×n2×n3\frac{2n_1}{N_{\mathrm{ds}}}\times n_2\times n_3 points, leading to costs

Factorization: O((n1Nds)3n23),Storage: O((n1Nds)2n22),for each slab.\text{Factorization: }\mathcal{O}\left(\left(\frac{n_1}{N_{\mathrm{ds}}}\right)^3 n_2^3\right),\qquad\text{Storage: }\mathcal{O}\left(\left(\frac{n_1}{N_{\mathrm{ds}}}\right)^2 n_2^2\right),\qquad\text{for each slab.}

These complexities are due to the cost of factorizing and storing (respectively) the largest nested dissection separator (see [29], Ch. 20). The total cost of factorizing and storing all the volumes’ degrees of freedom are

Factorization: O(n13/2Nds2N3/2),Storage: O(n1NdsN),for all slabs.\text{Factorization: }\mathcal{O}\left(\frac{n_1^{3/2}}{N_{\mathrm{ds}}^2}N^{3/2}\right),\qquad\text{Storage: }\mathcal{O}\left(\frac{n_1}{N_{\mathrm{ds}}}N\right),\qquad\text{for all slabs.}

When n1=n2=n3n_1=n_2=n_3, the complexity costs are O(N2Nds2)\mathcal{O}\left(\frac{N^2}{N_{\mathrm{ds}}^2}\right) and O(N4/3Nds)\mathcal{O}\left(\frac{N^{4/3}}{N_{\mathrm{ds}}}\right) for nested dissection, respectively.

Randomized rank-structured compression of S\mathbf{S}. The matrix S\mathbf{S} is block tridiagonal and acts only on the interfaces. There are NdsN_{\mathrm{ds}} interfaces, each of size n2n3=N/n1n_2n_3=N/n_1. Assume the HBS rank of the off-diagonal blocks is kk. Acquiring randomized samples requires O(k)O(k) applications of S\mathbf{S}, equivalently O(k)O(k) solves with the factorized local stiffness matrices (see Algorithm 2.1). Post-processing these samples is linear in the interface size, and hence sublinear in NN. The overall costs are

Sampling cost:O(kn1NdsN),HBS construction:O(k2Ndsn1N).\text{Sampling cost}: O\left(k\frac{n_1}{N_{\mathrm{ds}}}N\right), \qquad\text{HBS construction}: O\left(k^2\frac{N_{\mathrm{ds}}}{n_1}N\right).

For details on the construction, see [26]. When n1=n2=n3n_1=n_2=n_3, these costs scale as O(kN4/3Nds)O\left(k\frac{N^{4/3}}{N_{\mathrm{ds}}}\right) and O(k2NdsN2/3)O\left(k^2N_{\mathrm{ds}}N^{2/3}\right), respectively.

Iteratively solving SuΓ=fΓ\mathbf{S}\mathbf{u}_{\Gamma}=\mathbf{f}_{\Gamma}. Let mm denote the number of Krylov iterations required to reach the prescribed tolerance. For the compatible symmetrically scaled SPD system, Theorem 4.3 gives κ2(S~H)=O(H−2)\kappa_2(\widetilde{\mathbf{S}}_H)=O(H^{-2}); when H≍Nds−1H\asymp N_{\mathrm{ds}}^{-1}, the standard CG estimate therefore gives the upper bound m=O(Nds)m=O(N_{\mathrm{ds}}). For HPS-discretized and Helmholtz systems, we leave mm as iteration count, but let us mention that, for SPD systems discretized using HPS, we observe that m=O(H−1)m=O(H^{-1}) as well, and for Helmholtz-type systems, the iteration count is also independent of the mesh fineness of the local subdomains.

Once the compressed representation of S\mathbf{S} is constructed, one matrix–vector product costs O(kNdsn22)O(kN_{\mathrm{ds}}n_2^2), while orthogonalization in unrestarted GMRES costs O(m2Ndsn22)O(m^2N_{\mathrm{ds}}n_2^2) over the full solve. Consequently,

total solve cost:O((kmNds+m2Nds)n22)=O((kmNdsn1+m2Ndsn1)N).\text{total solve cost}: \quad O\left((kmN_{\mathrm{ds}}+m^2N_{\mathrm{ds}})n_2^2\right)=O\left(\left(k\frac{mN_{\mathrm{ds}}}{n_1}+\frac{m^2N_{\mathrm{ds}}}{n_1}\right)N\right).

In the case where n22n_2^2 or NdsN_{\mathrm{ds}} are prohibitively large, BiCGStab can be used instead of GMRES to avoid the Krylov orthogonalization cost, at the cost of possibly increasing the iteration count.

Remark 6 (Weak scaling in the parallel setting). Algorithm 2.2 shows that the construction of the global equilibrium operator is embarrassingly parallel. Once built, matrix–vector products with S\mathbf{S} can also be parallelized. If the number of processors and interfaces grow proportionally, then the cost of sparse factorization, randomized compression, and application of S\mathbf{S} all reduce by a factor of NdsN_{\mathrm{ds}}.

Remark 7 (Complexity of the Hierarchical Poincaré–Steklov discretization). For a fixed HPS tiling, the degrees of freedom grow as N=O(p3)N=O(p^3). The general complexity analysis above applies to the HPS discretization as well; however, one must also account for the additional cost of factorizing the local differential operators on each subdomain. These additional costs scale as O(p6N)O(p^6N) overall, as described in detail in [25].

Comparison to the matrix-free approach

As outlined in § 2, our compressed overlapping formulation is not the only possible candidate for a slab-based domain decomposition. Two alternatives are:

  1. per double-wide slab, compute the LU-factors of Aj\mathbf{A}_j and apply Sj,j±1\mathbf{S}_{j,j\pm1} using local solves, or

  2. form the compressed T-system based on the same (single) slabs, using a non-overlapping domain decomposition (imposing continuity of Neumann traces).

These are referred to, respectively, as the matrix-free and non-overlapping approach. In this section we compare, in terms of asymptotics, the difference in approach between overlapping matrix-free and using HBS compression for the S\mathbf{S}-system. In § 5.2 we compare the overlapping and non-overlapping approach.

In Table 1 we summarize the contrast between the HBS approach and the matrix-free approach. For simplicity, we restrict our attention to the 3D case with global DOF counts n1=n2=n3=nn_1=n_2=n_3=n and set N=n3N=n^3. We instead write the solve costs in terms of the actual Krylov iteration count mm, but let us mention that, in all our numerical observations, m=O(Nds)m=O(N_{\mathrm{ds}}) The benefit of using HBS approximations for the blocks of S\mathbf{S} is that this limits the memory footprint and enables cheap application of S\mathbf{S}. It also sets the stage for a later direct solver to be constructed (see § 5.3). In contrast, the more usual (see, e.g. [32, 34]) matrix-free approach is cheaper to set up; it requires no sampling and no compression. Note that, at a fixed number of double-wide slabs NdsN_{\mathrm{ds}}, as the grid is refined, the HBS approach becomes attractive. On the other hand, if the global grid is considered fixed and the number of double-wide slabs is increased, the matrix-free approach is more interesting. However, in this case, the number of iterations required to iteratively solve the resulting equilibrium system can grow prohibitively large. For a comparison of these two regimes, see Table 2 and Table 3.

Matrix-free S\mathbf{S}HBS S\mathbf{S}
Setup FLOPsO(N2Nds2)\mathcal{O}\left(\frac{N^{2}}{N_{\mathrm{ds}}^{2}}\right) →Nds\to N_{\mathrm{ds}} local LU factorizationsO(N2Nds2)+O(N4/3(k/Nds+k2Nds))\mathcal{O}\left(\frac{N^{2}}{N_{\mathrm{ds}}^{2}}\right)+\mathcal{O}\left(N^{4/3}(k/N_{\mathrm{ds}}+k^{2}N_{\mathrm{ds}})\right) →Nds\to N_{\mathrm{ds}} local LU factorizations +O(kNds)+\mathcal{O}(kN_{\mathrm{ds}}) local solves +Nds+N_{\mathrm{ds}} HBS compressions
Storage requirementsO(N4/3Nds)→\mathcal{O}\left(\frac{N^{4/3}}{N_{\mathrm{ds}}}\right)\to sparse factors.O(kNdsN2/3)→\mathcal{O}(kN_{\mathrm{ds}}N^{2/3})\to HBS matrices
Matrix-vector timeO(N4/3Nds)→Nds\mathcal{O}\left(\frac{N^{4/3}}{N_{\mathrm{ds}}}\right)\to N_{\mathrm{ds}} local LU solvesO(kNdsN2/3)→Nds\mathcal{O}(kN_{\mathrm{ds}}N^{2/3})\to N_{\mathrm{ds}} HBS matvecs
Solve FLOPsO(mN4/3/Nds+m2NdsN2/3)\mathcal{O}\left(mN^{4/3}/N_{\mathrm{ds}}+m^{2}N_{\mathrm{ds}}N^{2/3}\right)O(kmNdsN2/3+m2NdsN2/3)\mathcal{O}\left(kmN_{\mathrm{ds}}N^{2/3}+m^{2}N_{\mathrm{ds}}N^{2/3}\right)

Table 1. Comparison of the matrix-free and HBS costs for the equilibrium system S\mathbf{S}. The solve costs are expressed in terms of the actual Krylov iteration count mm and include unrestarted GMRES orthogonalization.

NNMemory (GB) LUMemory (GB) HBSConstruction (s) LUConstruction (s) HBS SampleConstruction (s) HBS CompressMatvec (s) LUMatvec (s) HBSSolve (s) LUSolve (s) HBS
1283128^{3}14.762.3812.7361.4830.991.330.03850.501.91
2563256^{3}314.5210.32366.77422.9261.0412.160.054497.794.24
5123512^{3}6036.4838.3710977.613748.96178.80149.560.1575683.2815.78

Table 2. Matrix-free vs. HBS for 3D stencil discretizations with weak admissibility, at fixed H=1/16H=1/16 and fixed rank k=64k=64. For N=5123N=512^{3} the values for the LU-decomposition are extrapolated, based on the single double-wide slab statistics.

HHMemory (GB) LUMemory (GB) HBSConstruction (s) LUConstruction (s) HBS SampleConstruction (s) HBS CompressMatvec (s) LUMatvec (s) HBSSolve (s) LUSolve (s) HBS
1/81/8519.964.42784.87414.8830.6614.210.023261.780.87
1/161/16314.5210.32366.77422.9261.0412.160.054497.794.24
1/321/32170.3222.12155.59505.07139.219.050.111635.8026.84
1/641/6481.3945.7257.81520.32272.168.200.2391179.98147.18

Table 3. Matrix-free vs. HBS, for 3D stencil discretization (order 2563256^{3}) as H→0H\to0, with fixed HBS rank k=64k=64.

Comparison to the non-overlapping approach

§ 4 gives an O(H−2)\mathcal{O}(H^{-2}) bound for the symmetrically scaled compatible SPD system and for the eigenvalue ratio of the raw equilibrium matrix. The supplementary material reports numerical evidence that, for representative stencil and collocation realizations, the Euclidean condition number follows a similar HH-dependence. Motivated by these observations, the experiments below report GMRES iteration counts for the raw systems as an empirical diagnostic. We consider both SPD problems covered by the theorem and nonsymmetric or indefinite problems outside its scope. We restrict ourselves to the 3D case. All tests use a standard seven-point stencil discretization on the unit cube Ω=[0,1]3\Omega= [0,1]^3. We compare unrestarted GMRES applied to

  1. the original sparse system A\mathbf{A},

  2. the nonoverlapping domain decomposition solver TH\mathbf{T}_H, and

  3. the overlapping domain decomposition solver SH\mathbf{S}_H.

The GMRES (relative) tolerance was set to 10−810^{-8}. No H\mathcal{H}-matrix compression was used. For the large-scale experiments, the condition number was estimated using power-iteration, rather than by explicitly computing the SVD.

Table 4 shows the basic test for the Laplace operator −Δ-\Delta. At fixed H=1/8H = 1/8, mesh refinement increases the iteration counts for A\mathbf{A} and TH\mathbf{T}_H, while the SH\mathbf{S}_H iteration count remains constant. The condition number κ2(SH)\kappa_2(\mathbf{S}_H) likewise remains virtually constant.

NNA\mathbf{A} itersTH\mathbf{T}_H itersSH\mathbf{S}_H itersκ2(A)\kappa_2(\mathbf{A})κ2(TH)\kappa_2(\mathbf{T}_H)κ2(SH)\kappa_2(\mathbf{S}_H)
40965347198.94 1018.94\,10^{1}1.41 1021.41\,10^{2}8.93
3276810869193.84 1023.84\,10^{2}2.93 1022.93\,10^{2}8.89
262144213991915.95 10215.95\,10^{2}6.04 1026.04\,10^{2}8.88
20971524131401964.85 10264.85\,10^{2}12.13 10212.13\,10^{2}8.88

Table 4. Finite-difference Poisson problem on the unit cube with eight fixed physical slabs. The table reports unrestarted GMRES iterations for the full matrix A\mathbf{A}, the Schur-complement system TH\mathbf{T}_H, and the scaled equilibrium system SH\mathbf{S}_H.

In Table 5 we compare the number of GMRES iterations for a decreasing slab width HH. The SH\mathbf{S}_H iteration count grows as HH decreases, qualitatively consistent with the HH-dependence of the energy and spectral bounds, while remaining smaller than the alternatives.

HHA\mathbf{A} itersTH\mathbf{T}_H itersSH\mathbf{S}_H itersκ2(A)\kappa_2(\mathbf{A})κ2(TH)\kappa_2(\mathbf{T}_H)κ2(SH)\kappa_2(\mathbf{S}_H)
1/41/421381915.96 10215.96\,10^{2}6.74 1026.74\,10^{2}2.45
1/81/8213991915.96 10215.96\,10^{2}7.03 1027.03\,10^{2}8.88
1/161/162131183815.96 10215.96\,10^{2}8.28 1028.28\,10^{2}34.82

Table 5. Finite-difference Poisson problem at varying HH. The conditioning of A\mathbf{A} and its iteration count are included for comparison. Here N=64×64×64N = 64 \times64 \times64.

Table 6 provides three additional tests at fixed HH: A variable-coefficient SPD diffusion problem, a convection-diffusion problem and a Helmholtz wavenumber sweep. These last two are included to examine empirically whether some of the qualitative behavior observed in the SPD tests persists in nonsymmetric and indefinite cases; they also show that, in these experiments, the growth in SH\mathbf{S}_H-iteration count is modest as the wavenumber increases. The Helmholtz frequency is reported in number of wavelengths NλN_\lambda per unit distance, i.e. Nλ=κ/(2π)N_\lambda= \kappa/(2\pi). Again, the underlying discretizations are 7-point stencils in the unit cube.

problemparameterNNA itersTHT_H itersSHS_H iters
variable-coefficient diffusion-327681367919
variable-coefficient diffusion-26214427511619
variable-coefficient diffusion-209715253816619
convection-diffusion-327681227020
convection-diffusion-26214423010020
convection-diffusion-209715245814120
HelmholtzNλ=1N_\lambda= 1209715256718827
HelmholtzNλ=2N_\lambda= 2209715291538261
HelmholtzNλ=3N_\lambda= 320971521000+891141

Table 6. Finite-difference fixed-slab diagnostics beyond constant-coefficient Poisson. The first two blocks refine the grid at fixed physical coefficients. The final block is a frequency sweep for Helmholtz on a 128×128×128128 \times128 \times128 grid.

For the variable-coefficient SPD problems, the conditioning behavior is consistent with the theory from § 4. The convection-diffusion and Helmholtz results provide empirical indications that similar qualitative behavior is observed in these nonsymmetric and indefinite test problems.

One problem with using a non-overlapping decomposition is that HBS compression with weak admissibility no longer suffices. In Figure 9 we compare, for the overlapping and non-overlapping formulations SHS_H and THT_H, the error of the discrete Poisson BVP solution u^\hat{\mathbf{u}} reached when the interface operators are compressed using weak admissibility.

In summary, the reported experiments show that the non-overlapping approach not only has larger iteration count, but also shows much poorer HBS-compressibility (with weak admissibility) than its overlapping counterpart.

Remark 8. The fact that the overlapping formulation can “get away” with using weak admissibility in 3D (as shown in Figure 9) is a particular feature of our method, and results from the fact that we deliberately sought a formulation that involves integral operators with smooth kernels, cf. (2.3) and (2.4). However, other rank structured formats can easily be used: either simpler single level structures [1], or more complex ones such as H2\mathcal{H}^2-matrices with strong admissibility [23, 6].

Direct solvers

As the above demonstrates, the use of iterative solvers can be disadvantageous whenever H→0H \to0 or the problem becomes highly oscillatory. The benefit of the reduced S-system then is that, in the absence of (numerical) interior resonances, it is a wellposed block tridiagonal system for which various solution strategies exist. These are based on combining block tridiagonal solvers (e.g., the Thomas algorithm or cyclic reduction) with HH-matrix arithmetic. This will be the subject of future work.

Numerical examples

In this section we demonstrate the effectiveness of the proposed method on some challenging 2D and 3D examples. The experiments were performed on a 24 core Intel Xeon Gold 6248R 3GHz CPU machine, using our Python software package SslabLU (available at [11]). The HBS construction timings we will report in Example 6.2 and 6.3 are broken down into:

  1. tAt_A, the total time to construct and factorize all local stiffness matrices

  2. tsamplet_{\mathrm{sample}}, the total time over the double-wide slabs to probe kk random samples needed in the construction of the HBS approximants to Sj,j±1\mathbf{S}_{j,j\pm1}

  3. tHBSt_{\mathrm{HBS}}, the total time to compress the blocks Sj,j′\mathbf{S}_{j,j^\prime} over the double-wide slabs after sampling has been performed.

We note that the number of double slabs NdsN_{\mathrm{ds}} corresponds to the number of interfaces. It is equal to the number of single slabs in the periodic case, and to one less than the number of single slabs in the non-periodic case. We also stress that the timings are for an unparallelized implementation. As outlined in Remark 6, each of these three steps can be parallelized.

Example 1: Variable-coefficient screened diffusion equations

Screened diffusion equations of the form

−∇⋅(D(x,y)∇u(x,y))+α2u(x,y)=f(x,y)in Ω(32)-\nabla\cdot\left(D(x,y)\nabla u(x,y)\right) + \alpha^2 u(x,y) = f(x,y) \qquad\text{in }\Omega \tag*{(32)}
∂u(x,y)∂n=0on ∂Ω(33)\frac{\partial u(x,y)}{\partial n}=0 \qquad\text{on }\partial\Omega \tag*{(33)}

are a powerful tool in the numerical solution of convection-diffusion equations in incompressible flow:

∂u(t;x,y)∂t+v(t;x,y)⋅∇u(t;x,y)=∇⋅(D(x,y)∇u(t;x,y))in [0,tfin]×Ω∂u(t;x,y)∂n=0on ∂Ωu(0;x,y)=U0(x,y)in Ω.\begin{aligned} \frac{\partial u(t;x,y)}{\partial t} + \mathbf{v}(t;x,y)\cdot\nabla u(t;x,y) &= \nabla\cdot\left(D(x,y)\nabla u(t;x,y)\right) && \text{in }[0,t_{\mathrm{fin}}]\times\Omega\\ \frac{\partial u(t;x,y)}{\partial n} &= 0 && \text{on }\partial\Omega\\ u(0;x,y) &= U_0(x,y) && \text{in }\Omega. \end{aligned}

By introducing an implicit-explicit (IMEX) time-stepping discretization, as in [15], (34) can be reduced to a sequence of problems of the form (32). To be explicit:

−∇⋅(D(x,y)∇Un+1(x,y))+1ΔtUn+1(x,y)=1ΔtUn(x,y)−v⋅∇Un(x,y)in Ω(34)-\nabla\cdot\left(D(x,y)\nabla U_{n+1}(x,y)\right)+\frac{1}{\Delta t}U_{n+1}(x,y)=\frac{1}{\Delta t}U_n(x,y)-\mathbf{v}\cdot\nabla U_n(x,y)\qquad\text{in }\Omega \tag*{(34)}

with zero Neumann boundary conditions and Un(x,y)=u(nΔt;x,y)U_n(x,y)=u(n\Delta t;x,y). This is known as elliptic marching, Rothe’s method or the method of lines. For simplicity, we restrict our attention here to a first order IMEX scheme (backward Euler), but more advanced time-stepping schemes and IMEX discretizations can be used. See [15] and [2] for details on spectral correction time-stepping and IMEX methods.

We take Ω=[0,1]2\Omega=[0,1]^2 with periodic boundary conditions in the horizontal direction, representing an infinitely long horizontal channel. We set D(x,y)=D0(1+ε(sy(2y−1)+sxcos⁡(2πx)))D(x,y)=D_0(1+\varepsilon(s_y(2y-1)+s_x\cos(2\pi x))) with D0=0.1D_0=0.1, ε=0.3\varepsilon=0.3, sy=1s_y=1 and sx=0.5s_x=0.5, and v(x,y)=(−2y(1−y),0)\mathbf{v}(x,y)=(-2y(1-y),0). The initial concentration U0U_0 is set to be a smooth bump function.

The system in (34) was discretized using an HPS discretization consisting of 16×1616\times16 square subdomains, carrying a p×pp\times p Chebyshev collocation grid, for p∈{6,…,16}p\in\{6,\ldots,16\}. We study the self-convergence of u(1;x,y)u(1;x,y) at tfin=1t_{\mathrm{fin}}=1, with respect to a reference solution at pref=20p_{\mathrm{ref}}=20. We take Δt=6.94×10−3\Delta t=6.94\times10^{-3}6 Since Δt\Delta t is positive and fixed, the continuum operator on the left-hand side of (34) is always symmetric positive definite. The HPS collocation matrix is in general not SPD in the Euclidean inner product, but the same S-matrix reduction can be reused for all time-steps. Slab separation H=1/16H=1/16 was used for each order. The reference solution was obtained using the matrix-free approach, i.e., without any compression.

Error at $t=1$ and timing of the matrix-free and HBS-compressed S-formulation

Figure 11. Error at t=1t=1 and timing of the matrix-free and HBS-compressed S-formulation for u(1,x,y)u(1,x,y).

The convection-diffusion equation (34) is solved for n=1,…,nfinn=1,\ldots,n_{\mathrm{fin}} such that nfinΔt=1n_{\mathrm{fin}}\Delta t=1. The vector up\mathbf{u}_p denotes the approximation of Unfin(x,y)U_{n_{\mathrm{fin}}}(x,y) using a 16×1616 \times16 HPS grid of order pp at every IMEX time-step. We track the average GMRES solution time per IMEX time-step, as well as the final error at nfinn_{\mathrm{fin}} with respect to a reference solution uref=u20\mathbf{u}_{\mathrm{ref}}=\mathbf{u}_{20}. For both the matrix-free formulation and the HBS compressed formulation, the number of GMRES iterations at each timestep was (at most) 9. The HBS rank was set to k=16k=16 for each N=162p2N=16^2p^2. At this rank, the HBS compression is essentially exact. This is reflected in the top figure; the two error graphs cannot be distinguished.

Figure 11 reports, at various N=162p2N=16^2p^2, the error of the discrete solution interpolated on a fine equispaced grid with respect to a reference solution interpolated on that same grid. It also shows the GMRES solve time for the equilibrium system S averaged over the IMEX time-steps. In Figure 10 the solution Un(x,y)U_n(x,y) (approximated by the reference solution) is plotted for nΔt∈{0,1/2,1}n\Delta t \in\{0,1/2,1\}. The timing results for the construction of the HBS approximation are completely similar to those in § 6.2, hence they are not included here.

Contour plots of the solution $U_n$ to (6.3) at $t=0$, $t=.5$ and $t=1$

Figure 10. Contour plots of the solution UnU_n to (34) at t=0t=0, t=.5t=.5 and t=1t=1.

Example 2: Photonic crystal waveguide

We solve the Helmholtz equation with variable wavenumber:

{−Δu(x,y)−κ2(1−b(x,y))u(x,y)=0,(x,y)∈Ω,u(x,y)=1,(x,y)∈∂Ω,(35)\begin{cases} -\Delta u(x,y)-\kappa^2(1-b(x,y))u(x,y)=0, & (x,y)\in\Omega,\\ u(x,y)=1, & (x,y)\in\partial\Omega, \tag*{(35)} \end{cases}

where Ω=[0,1]2\Omega=[0,1]^2 and 1−b1-b models the relative speed of light imposed by a crystal waveguide, represented as a collection of Gaussian bumps (see Figure 12a).

Numerical solution plots: (a) $1-b(x,y)$, (b) solution at $\kappa=156.703$, and (c) solution at $\kappa=157.017$

Figure 12. Numerical solution, at κ=156.703\kappa= 156.703 and κ=157.017\kappa= 157.017, to the BVP in equation (35).

We set H=1/8H=1/8 and the HPS tiling per double-wide slab to be an 8-by-32 square lattice and study self-convergence of the solution: for p∈{8,10,…,18,20}p\in\{8,10,\ldots,18,20\} we compare, on a fine uniform grid, the interpolated solution up\mathbf{u}_p to an interpolated reference solution u30\mathbf{u}_{30} at p=30p=30 (computed without HBS compression and using a direct solver). We use HBS compression with rank k=25k=25. We use GMRES as an iterative solver, with its tolerance set to 10−1010^{-10}. For reference, we also plot the self-convergence without HBS compression and using a direct solver. In a sense this provides the best convergence we could hope for.

Convergence and computational cost plots

Figure 13. Convergence and computational cost for the solution of equation (35), using our proposed solver. Here Nds=7N_{\mathrm{ds}} = 7 and each double-wide slab uses an 8-by-32 HPS tiling. The polynomial order pp is indicated on top. The accuracy stalls around 6 − 7 digits because the off-diagonal block compression is accurate up to 7 digits. Due to ill-conditioning of the internal solver, convergence for the dense solver slows down at high pp.

We observe the following:

  1. For all pp the number of GMRES iterations required for both wave numbers was 198±1198 \pm1. Thus, for this fixed physical problem and slab geometry, the GMRES iteration count is essentially unchanged as the HPS order pp varies.

  2. Even with HBS compression at rank ‘only’ k=25k = 25, we see that the convergence is essentially optimal, stalling around 10−510^{-5}, the accuracy threshold at this rank. For this 2D problem then, despite its oscillatory nature, HBS compression does not influence convergence, only the maximal accuracy reached.

HBS compression, including sampling, is negligible compared to building and factorizing the local stiffness matrices; both factorization and sampling costs match the predicted asymptotics.

Remark 9. A common approach to solving the Helmholtz equation at high frequency is to construct Impedance-to-impedance maps instead of Dirichlet-to-Neumann or our Dirichlet-to-Dirichlet maps. In Appendix § 9 we investigate the GMRES iteration counts for these three approaches.

Example 3: Twisted square torus

Another source of variable coefficient PDEs is transformed constant coefficient PDEs. Say we wish to solve the 3D Helmholtz equation

−Δu(x,y,z)−κ2u(x,y,z)=0 in Ω(36)-\Delta u(x,y,z) - \kappa^{2}u(x,y,z) = 0 \text{ in } \Omega \tag*{(36)}
u(x,y,z)=1 on ∂Ω(37)u(x,y,z) = 1 \text{ on } \partial\Omega \tag*{(37)}

where Ω\Omega admits transformations

f:[0,1]3→Ωf : [0,1]^{3} \to\Omega
g:Ω→[0,1]3g : \Omega\to[0,1]^{3}

such that g∘f=Idg \circ f = Id and ff and gg are twice continuously differentiable. We consider here Ω\Omega the twisted torus, shown in Figure 14. Because the twisted torus is periodic, we have that gg and ff are periodic. The Helmholtz equation on Ω\Omega is transformed into a (periodic) variable coefficient PDE on [0,1]3[0,1]^{3} using gg and ff. We solve equation (36) at κ=17.66\kappa= 17.66. For the untransformed twisted square torus this makes the original dimensionless wavenumber κ⋅diam⁡(Ω)≈135.46\kappa\cdot\operatorname{diam}(\Omega) \approx135.46. This means Ω\Omega is 21.56 wavelengths across. We again study self-convergence for p∈{4,6,8,10}p \in\{4, 6, 8, 10\}, comparing to a reference solution u12\mathbf{u}_{12}. In all cases we use an HPS discretization in the double slabs Ψj\Psi_j with an 8×16×168 \times16 \times16 HPS tiling. Observe that, for p=12p = 12 each slab has a total number of 3, 538, 944 DOFs before reduction. We set H=1/16H = 1/16 meaning Ω\Omega is discretized using N=28,311,552N = 28, 311, 552 total DOFs. For the approximate solutions up\mathbf{u}_p the HBS rank was set to k=150k = 150, and the GMRES convergence tolerance was set to 10−610^{-6}.

Boundary of the twisted square torus and cross section of the solution

Figure 14. Boundary of the twisted square torus (left) and cross section of the solution at κ=17.66\kappa= 17.66 of the Helmholtz equation (36), obtained using an HPS discretization of order p=12p = 12.

We observe the following:

  1. For all pp the number of GMRES iterations required was 1476. This again demonstrates that the number of iterations is independent of the order pp but it is still quite high; it motivates the development of an efficient direct solver or of a cheap preconditioner.

  1. Again, we see fast convergence of the solution up to the GMRES tolerance and the accuracy of the HBS block compression.

We also see that the predicted asymptotic costs are slight overestimates of the observed computational costs.

Conclusions and future work

This manuscript describes a technique for solving scalar elliptic PDEs, based on an overlapping domain decomposition method built from thin slabs. The method is based on an interface equilibrium equation whose off-diagonal blocks discretize interface solution operators between separated interfaces. This structure explains the strong compressibility observed in the experiments and the favorable behavior in the numerical tests. The non-zero blocks in the equilibrium system approximate integral operators with smooth kernels, making them highly amenable to compression using hierarchical matrix techniques. In our method, these blocks are formed using a randomized compression technique coupled with a local direct solver that exploits that each subdomain is thin. The numerical experiments demonstrate that the formulation can be applied accurately at large scale, including to oscillatory test problems, while also indicating the regimes where additional preconditioning or direct solvers are needed.

Convergence and computational cost

Figure 15. Convergence and computational cost for the solution of equation (36), using our proposed solver, for κ=17.66\kappa= 17.66. Here Nds=16N_{\mathrm{ds}} = 16 and each double-wide slab uses an 8-by-16-by-16 HPS tiling. The polynomial order pp is indicated on top. We see that convergence is slowed down as the error reaches the desired GMRES tolerance and the accuracy of the block compression.

For coercive problems, multigrid methods remain the natural benchmark for one-off low-order full-volume solves. The present formulation has a different cost profile: it is high-order, reusable across right-hand sides, naturally parallel across slabs, and can compute interface traces before any volume reconstruction. These features make time-to-accuracy and multiple-right-hand-side comparisons an important topic for future work.

In this work, the reduced global system is solved using an iterative method that typically converges rapidly. However, it is also possible to construct a linear complexity fully direct solver by exploiting the rank structure in the system to compute an LU factorization in “data sparse” form; work in this direction is in progress. Additionally, the technique is being extended to different boundary conditions (e.g., mixed, impedance, . . . ), and these options will be added to our software as they become available. We are also working on developing an HPC distributed memory implementation of the solver, leveraging that the method we present is highly parallelizeable.

Acknowledgements

The work reported was supported by the Office of Naval Research (N00014-18-1-2354), by the National Science Foundation (DMS-2313434), by the Department of Energy ASCR (DE-SC0025312), and by the Sloan Foundation. The authors would also like to express their gratitude to Joseph Kump for his contributions to the software package BslabLU.

Trace-system iteration comparison for Example 2

We compare three reduced trace systems for the example in 6.2, with κ=157.017\kappa= 157.017 and local HPS order p=8p = 8. All three systems use the same physical slab interfaces for domain decomposition with Nds=7N_{\mathrm{ds}} = 7. The physical solution for this case is shown in Figure 12c. The first system is the standard non-overlapping DtN Schur complement T\mathbf{T} from (2). The second system is an assembled impedance-to-impedance (ItI) trace system RItI\mathbf{R}^{\mathrm{ItI}}, following the construction of [19]. The third system is the overlapping equilibrium system S\mathbf{S} from (3). Table 7 reports unrestarted GMRES iteration counts.

NNT\mathbf{T} itersRItI\mathbf{R}^{\mathrm{ItI}} itersS\mathbf{S} iters
589,824762306191
1,327,104926326191
2,359,2961065333191
9,437,1841497358191

Table 7. Unrestarted GMRES counts (relative tolerance 10−810^{-8}) for the three trace systems in Example 2 under mesh refinement. The slab geometry is fixed at Nds=7N_{\mathrm{ds}} = 7, and the local HPS order is fixed at p=8p = 8.

As shown in Figure 3(b), let T(α)\mathbf{T}^{(\alpha)} and T(β)\mathbf{T}^{(\beta)} denote the local outward-normal DtN maps on the left and right subdomains, respectively, with u\mathbf{u} and g\mathbf{g} denoting the Dirichlet and Neumann data. For impedance parameter η\eta, define on each subdomain the incoming and outgoing Robin traces by

r(α)=g(α)−iηu(α),s(α)=g(α)+iηu(α).\mathbf{r}^{(\alpha)} = \mathbf{g}^{(\alpha)} - i\eta\mathbf{u}^{(\alpha)}, \qquad\mathbf{s}^{(\alpha)} = \mathbf{g}^{(\alpha)} + i\eta\mathbf{u}^{(\alpha)}.

For the Helmholtz experiments in the code we take η=κ\eta= \kappa. The local ItI maps are then defined by the Cayley transform

R(α)=(T(α)+iηI)(T(α)−iηI)−1,\mathbf{R}^{(\alpha)} = \left(\mathbf{T}^{(\alpha)} + i\eta\mathbf{I}\right)\left(\mathbf{T}^{(\alpha)} - i\eta\mathbf{I}\right)^{-1},

which map incoming to outgoing Robin traces, as in [19 eqs. 17–21]. The corresponding traces and ItI map on Ω(β)\Omega^{(\beta)} are defined analogously. For two neighboring subdomains sharing an interface Γj\Gamma_j, if rj(α)\mathbf{r}^{(\alpha)}_j and sj(α)\mathbf{s}^{(\alpha)}_j are the incoming and outgoing traces on the left subdomain, and rj(β)\mathbf{r}^{(\beta)}_j and sj(β)\mathbf{s}^{(\beta)}_j are the corresponding traces on the right subdomain, then the shared interface relations are

rj(α)=−sj(β),sj(α)=−rj(β).\mathbf{r}^{(\alpha)}_j = -\mathbf{s}^{(\beta)}_j, \qquad\mathbf{s}^{(\alpha)}_j = -\mathbf{r}^{(\beta)}_j.

These signs reflect the opposite outward normals on the two sides of Γj\Gamma_j. On the shared interface block, the left and right maps read

sj(α)=Rj,j−1(α)rj−1(α)+Rj,j(α)rj(α),sj(β)=Rj,j(β)rj(β)+Rj,j+1(β)rj+1(β).\mathbf{s}^{(\alpha)}_j = \mathbf{R}^{(\alpha)}_{j,j-1}\mathbf{r}^{(\alpha)}_{j-1} + \mathbf{R}^{(\alpha)}_{j,j}\mathbf{r}^{(\alpha)}_j, \qquad\mathbf{s}^{(\beta)}_j = \mathbf{R}^{(\beta)}_{j,j}\mathbf{r}^{(\beta)}_j + \mathbf{R}^{(\beta)}_{j,j+1}\mathbf{r}^{(\beta)}_{j+1}.

Combining these with the compatibility relations gives

rj(α)=W(Rj,j(β)Rj,j−1(α)rj−1(α)−Rj,j+1(β)rj+1(β)),W=(I−Rj,j(β)Rj,j(α))−1.\mathbf{r}^{(\alpha)}_j = \mathbf{W}\left(\mathbf{R}^{(\beta)}_{j,j}\mathbf{R}^{(\alpha)}_{j,j-1}\mathbf{r}^{(\alpha)}_{j-1} - \mathbf{R}^{(\beta)}_{j,j+1}\mathbf{r}^{(\beta)}_{j+1}\right), \qquad\mathbf{W} = \left(\mathbf{I} - \mathbf{R}^{(\beta)}_{j,j}\mathbf{R}^{(\alpha)}_{j,j}\right)^{-1}.

This is the dense merge solve in [19 eq. 29] written in the left-right notation used here. Applying this merge at each shared slab interface eliminates the duplicate left and right Robin traces. We then keep one Robin trace unknown, denoted by rj\mathbf{r}_j, on each physical interface Γj\Gamma_j. The resulting assembled ItI interface system is block tridiagonal; we denote it by RItI\mathbf{R}^{\mathrm{ItI}} and use it as the ItI system in the comparison below.

Over the refinement range in Table 7, the DtN Schur-complement iteration count increases from 762 to 1497. The ItI count increases more mildly, from 306 to 358. The overlapping system remains at 191 GMRES iterations throughout. Thus, for this high-frequency waveguide example and the physical right-hand side associated with (35), the overlapping formulation is least sensitive to mesh refinement among the three trace systems.

Spectrum of the collocated equilibrium operator

Here we inspect the eigenvalues of S\mathbf{S}, where S\mathbf{S} is a sufficiently fine spectral discretization of the equilibrium operator SS, obtained from various partial differential operators.

In this section and Section B.1 we follow the principle of L2L^2-weighted discretizations for continuous operators (see [35 §43]): we discretize SS to S\mathbf{S} in such a way that ⟨Su,v⟩L2(Γ)≈v∗Su\langle\mathbf{S}u,v\rangle_{L^2(\Gamma)} \approx v^* \mathbf{S}u where u\mathbf{u} and v\mathbf{v} are the discretizations of the interface functions uu and vv respectively and Γ=⋃jΓj\Gamma= \bigcup_j \Gamma_j. For instance, if S~\widetilde{\mathbf{S}} denotes the (unweighted) spectrally collocated equilibrium operator, S\mathbf{S} is obtained by scaling S~\widetilde{\mathbf{S}} by a diagonal matrix W=(INds⊗Dw)\mathbf{W} = (I_{N_{\mathrm{ds}}} \otimes D_w), such that S=WS~W−1\mathbf{S} = \mathbf{W}\widetilde{\mathbf{S}}\mathbf{W}^{-1} with Dw:=diag⁡(w)D_w := \operatorname{diag}(w) and ww containing the square roots of the Clenshaw-Curtis quadrature weights. Any weighted discretization S\mathbf{S} of SS can be used to solve the original unweighted system S~u=b\widetilde{\mathbf{S}}u = b by solving Sy=Wb\mathbf{S}y = \mathbf{W}b and u=W−1yu = \mathbf{W}^{-1}y. In Figure 16 and Figure 18 we plot the eigenvalues of S\mathbf{S} (after correct L2L^2-weighting).

Spectrum of the discretized equilibrium operator S for the Laplace equation

(a) Spectrum of the discretized equilibrium operator S\mathbf{S} for the Laplace equation.

Spectrum of the discretized equilibrium operator S for the Helmholtz equation

(b) Spectrum of the discretized equilibrium operator S\mathbf{S} for the Helmholtz equation.

Figure 16. Spectrum of S\mathbf{S} for the Laplace equation (left) and the Helmholtz equation (right).

Figure 18. Total spectrum (left) and non-real part of the spectrum (right) of the discretized equilibrium operator S\mathbf{S} for a variable-coefficient convection-diffusion equation.

For the Laplace operator and the Helmholtz operator (at κ=10\kappa= 10) we see in Figure 16 that both spectra are purely real. We clearly see that for the Laplace operator the matrix S\mathbf{S} is symmetric positive definite, and for the Helmholtz equation it is self-adjoint. We see that the Fredholm character of S=(I−K)S = (I-K) is preserved by the discretization, i.e. S=I−K\mathbf{S} = I-\mathbf{K}. Indeed, by construction, K\mathbf{K} acts like a discretized Hilbert-Schmidt kernel integral operator. For the Helmholtz equation, the presence of a damping term perturbs the spectrum into the negative half-plane and past 22, which means our analysis in § 4 needs to be refined in this case.

The variable-coefficient case

In Section 4 and the previous section, we essentially rely on the condition number estimate κρ:=ρ(S)ρ(S−1)\kappa_\rho:= \rho(S)\rho(S^{-1}) and show that κρ=O(1/H2)\kappa_\rho= O(1/H^2). In this section we present an analysis of the continuum operator SS underlying S\mathbf{S} and use this to investigate κ2(S)\kappa_2(\mathbf{S}). Our analysis, and the supporting numerical results suggest that κ2(S)=O(κρ)\kappa_2(\mathbf{S}) = O(\kappa_\rho). Intuitively, this means that the measure of non-normality of the matrix S\mathbf{S} is benign.

The outline of our argument is as follows:

  1. We assume that we have a square domain Ω=[0,1]2\Omega= [0,1]^2, and equispaced interfaces {Γj}j=1Nds\{\Gamma_j\}_{j=1}^{N_{\mathrm{ds}}} with separation HH.

  2. We show that, as H→0H \to0, the continuous equilibrium operator SS becomes in a sense ‘sufficiently self-adjoint’.

  3. There we have that, an L2L^2-weighted discretization S\mathbf{S} of SS, this implies that S\mathbf{S} also becomes sufficiently self-adjoint.

For ease of introduction we first assume that we have a positive definite formally self-adjoint PDE operator A\mathcal{A} on Ω\Omega with constant coefficients. Our first task is then to show that in this case the equilibrium operator SS is self-adjoint. It is clear from the continuum form in 2.3 that

[Sj−1,j∗uj−1](x)=∫Γj−1G(j−1)(y,x)‾uj−1(y) dy=∫Γj−1G(j)(x,y)uj−1(y) dy[S^{*}_{j-1,j}u_{j-1}](x)=\int_{\Gamma_{j-1}}\overline{G^{(j-1)}(y,x)}u_{j-1}(y)\,\mathrm{d}y=\int_{\Gamma_{j-1}}G^{(j)}(x,y)u_{j-1}(y)\,\mathrm{d}y

since G(j−1)(x,y)=G(j−1)(y,x)‾G^{(j-1)}(x,y)=\overline{G^{(j-1)}(y,x)} and G(j)=G(j−1)G^{(j)}=G^{(j-1)}. This last claim is true only by virtue of A\mathcal{A} having constant coefficients and the fact that all slabs are chosen isomorphic. Therefore, in the simple case considered, we have that S=S∗S=S^{*}.

For the case of non-constant coefficients the operator SS is no longer self-adjoint. It is not even a normal operator. However, as H→0H\to0 we can still recover that G(j)→G(j−1)G^{(j)}\to G^{(j-1)} and vice versa. The rate at which this happens depends on the smoothness of the coefficients of A\mathcal{A}. As such, for formally self-adjoint PDE operators with sufficiently smooth coefficients, an asymptotic version of self-adjointness can still be recovered. While a full analysis is beyond the scope of this work, we mention that this is essentially because the Green’s function in the case of smooth coefficients varies smoothly with the perturbation of moving from Ψj\Psi_j to Ψj−1\Psi_{j-1}. This can be shown using the techniques from [17], §II (see also [24], §VII.6.5). We will present a numerical study of the asymptotics here.

We use the variable-coefficient convection-diffusion differential operator from (32) in § 6.1 with α=1\alpha=1, but let us mention that the same behavior was observed for any other positive definite elliptic variable-coefficient PDE operator tested. For a given HH, we construct two approximations SH,hS_{H,h} and SH,pS_{H,p} of the corresponding SS; respectively these are built with a fine five-point stencil discretizations (isotropic, with hx=hy=h=1/128h_x=h_y=h=1/128) and with high-order Chebyshev spectral collocation discretizations (with order px=py=p=30p_x=p_y=p=30) for the overlapping slabs. As described above, SH,pS_{H,p} is L2L^2-weighted. The discretization SH,hS_{H,h} does not need to be weighted.

In Figure 17, we investigate for both discretizations three measures of normality. Firstly, we compute ∥Sj,j−1−Sj−1,j∗∥2\lVert S_{j,j-1}-S^{*}_{j-1,j}\rVert_2 with Γj\Gamma_j a fixed interface, as an indicator of the smoothness of the Green’s functions over HH. In our case we chose Γj\Gamma_j to correspond to the interface x=1/2x=1/2, meaning Γj−1\Gamma_{j-1} corresponds to x=1/2−Hx=1/2-H. Secondly, we compute

Three plots showing normality measures as functions of slab width H

Figure 17. (a) ∥Sj,j−1−Sj−1,j∗∥2\lVert S_{j,j-1}-S^{*}_{j-1,j}\rVert_2 as a function of HH. (b) ∥λ−σ∥∞\lVert\lambda-\sigma\rVert_\infty as a function of HH. (c) κ2/κρ−1\kappa_2/\kappa_\rho-1 as a function of HH. The normality measures ∥Sj,j−1−Sj−1,j∗∥2\lVert S_{j,j-1}-S^{*}_{j-1,j}\rVert_2, ∥λ−σ∥∞\lVert\lambda-\sigma\rVert_\infty and κσ/κρ−1\kappa_\sigma/\kappa_\rho-1 as a function of the slab width HH, for both a stencil and spectral discretization.

∥λ−σ∥∞:=max⁡i{∣λi∣−σi}\lVert\lambda-\sigma\rVert_{\infty}:=\max_i\{|\lambda_i|-\sigma_i\}

where ∣λ1∣,∣λ2∣,…|\lambda_1|,|\lambda_2|,\ldots and σ1≥σ2≥⋯\sigma_1\ge\sigma_2\ge\cdots are the moduli of the eigenvalues and the singular values of the discretizations7. Finally, we also plot the measure κ2/κρ−1\kappa_2/\kappa_\rho-1, where κρ:=ρ(SH,h)ρ(SH,h−1)\kappa_\rho:=\rho(S_{H,h})\rho(S_{H,h}^{-1}) (similarly for SH,pS_{H,p}), and κ2\kappa_2 is the ∥⋅∥2\lVert\cdot\rVert_2-condition number.

Figure Figure 17 shows that both discretizations behave completely similarly. This is not surprising, since at each HH they approximate the same continuous Fredholm type operator. We see that the measure of non-normality ∥λ−σ∥∞\lVert\lambda-\sigma\rVert_{\infty} approaches zero as H→0H \to0. In fact we have the stronger observation that ∥λ−σ∥∞=O(H3/2)\lVert\lambda-\sigma\rVert_{\infty} = O(H^{3/2}). This does not show, however, that κρ→κ2\kappa_{\rho} \to\kappa_{2}, since κρ\kappa_{\rho} and κ2\kappa_{2} both diverge as HH approaches zero. However, Figure 17c shows that κ2=cHκρ\kappa_{2} = c_{H}\kappa_{\rho} for the discretizations tested here, with cHc_{H} remarkably close to one. Let us mention again that we observed the same behavior for every symmetric positive elliptic PDE discretization we tested.

The experiments and analysis here therefore support the use of κρ\kappa_{\rho} as an indicator of the actual condition number for the stencil and spectral discretizations tested here, and suggest similar asymptotic behavior for the two discretizations.

In Figure 18 we plot the eigenvalues of SH,p\mathbf{S}_{H,p} at H=1/16H = 1/16. It shows that SH,p\mathbf{S}_{H,p} is no-longer self-adjoint; its spectrum has a small but non-negligible imaginary component. Note that the eigenvalues not only occur in conjugate pairs (as is to be expected), but they are also symmetric around ℜ(z)=1\Re(z) = 1.

Comparison to the non-overlapping domain decomposition

Here we investigate the spectrum of the T\mathbf{T} system. For compactness we restrict our attention to the Laplace equation. We use fine stencil and spectral discretizations and report the results in Figure 19. In both cases the domain Ω=[0,1]2\Omega= [0,1]^2 is the unit square, which was divided into non-overlapping slabs of width H=1/16H = 1/16. For the spectral case we employ the L2L^2-weighting principle outlined in Section B.

Spectrum plots of the matrix $\mathbf{T}$ for stencil and spectral discretizations
Image not extracted

(a) Spectrum of the matrix T\mathbf{T} for the Laplace equation with stencil discretizations at h=2−kh = 2^{-k}, k=6k = 6 (top), k=7k = 7 (middle) and k=8k = 8 (bottom). Note the difference in length scales for the real part of the spectrum.

Image not extracted

(b) Spectrum of the matrix T\mathbf{T} for the Laplace equation with spectral discretizations at p=64p = 64 (top), p=128p = 128 (middle) and p=256p = 256 (bottom). Note the difference in length scales for the real part of the spectrum.

Figure 19. Spectrum of the matrix T\mathbf{T} for the Laplace equation at different discretizations (stencil and spectral). Observe that the spectrum (its bounds and its shape) is discretization dependent. Additionally, there is no beneficial spectral clustering as in the case for the S\mathbf{S}-matrix.

We clearly see that the spectral range is not only much larger than that of the S\mathbf{S}-system, but also that the spectral behavior of the underlying continuum operator T\mathbf{T} is not captured well by both discretizations. In short, the operator T\mathbf{T} behaves like an unbounded pseudo-differential operator, as opposed to the second kind Fredholm behavior of the operator S\mathbf{S}. For the stencil, we see that the largest eigenvalue grows like O(1/h2)O(1/h^2), where similarly the largest eigenvalue for the spectral case scales like O(p2)O(p^2).

References

  1. [1]P. R. Amestoy, A. Buttari, J.-Y. L’Excellent, and T. Mary. Performance and scalability of the block low-rank multifrontal factorization on multicore architectures. ACM Transactions on Mathematical Software (TOMS), 45(1):2, 2019.DOI
  2. [2]U. M. Ascher, S. J. Ruuth, and B. T. R. Wetton. Implicit-explicit methods for time-dependent partial differential equations. SIAM Journal on Numerical Analysis, 32(3):797–823, 1995.DOI
  3. [3]K. E. Atkinson. The numerical solution of integral equations of the second kind. Cambridge University Press, Cambridge, 1997.DOI
  4. [4]J. Ballani and D. Kressner. Matrices with Hierarchical Low-Rank Structures, pages 161–209. Springer International Publishing, Cham, 2016.DOI
  5. [5]M. Bebendorf. Hierarchical matrices, volume 63 of Lecture Notes in Computational Science and Engineering. Springer-Verlag, Berlin, 2008. A means to efficiently solve elliptic boundary value problems.DOI
  6. [6]S. Börm. Efficient numerical methods for non-local operators, volume 14 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Zürich, 2010. ℋ²-matrix compression, algorithms and analysis.
  7. [7]S. Börm and W. Hackbusch. Approximation of boundary element operators by adaptive ℋ²-matrices. In Foundations of computational mathematics: Minneapolis, 2002, volume 312 of London Math. Soc. Lecture Note Ser., pages 58–75. Cambridge Univ. Press, Cambridge, 2004.
  8. [8]G. Ciaramella and T. Vanzan. Spectral coarse spaces for the substructured parallel Schwarz method. Journal of Scientific Computing, 91(3):69, Apr. 2022.DOI
  9. [9]B. Després. Méthodes de décomposition de domaine pour les problèmes de propagation d’ondes en régime harmonique. Le théorème de Borg pour l’équation de Hill vectorielle. Thèse de doctorat, Université Paris IX Dauphine, Paris, France, 1991. UER Mathématiques de la Décision.
  10. [10]S. Dirckx. Efficient Representations of Wavenumber Dependent BEM Matrices: Construction and Analysis for the 3D Scalar Helmholtz Equation. PhD thesis, Numerical Analysis and Applied Mathematics (NUMA), Leuven (Arenberg), Faculty of Engineering Science, Science, Engineering and Technology Group, Jan. 2024. Huybrechs, Daan (supervisor), Meerbergen, Karl (cosupervisor).
  11. [11]S. Dirckx. Slabblu. https://github.com/SimonDirckx/SlabBLU.git, 2025.
  12. [12]G. Dolzmann and S. Müller. Estimates for Green’s matrices of elliptic systems by Lp theory. Manuscripta Mathematica, 88(2):261–273, 1995.DOI
  13. [13]B. Engquist and L. Ying. Sweeping preconditioner for the helmholtz equation: Hierarchical matrix representation. Commun. Pure Appl. Math., 64(5):697–735, May 2011.arxiv.org/abs/1007.4290
  14. [14]B. Engquist and L. Ying. Sweeping preconditioner for the helmholtz equation: Moving perfectly matched layers. Multiscale Modeling & Simulation, 9(2):686–710, 2011.arxiv.org/abs/1007.4291
  15. [15]F. Fryklund, S. Pålsson, and A.-K. Tornberg. An integral equation method for the advection-diffusion equation on time-dependent domains in the plane. Journal of Computational Physics, 475:111856, 2023.DOI
  16. [16]M. J. Gander and H. Zhang. A class of iterative solvers for the helmholtz equation: Factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized schwarz methods. SIAM Review, 61(1):3–76, 2019.arxiv.org/abs/1610.02270
  17. [17]P. R. Garabedian and M. Schiffer. Convexity of domain functionals. Journal d’Analyse Mathématique, 2(2):281–368, 1952.
  18. [18]D. Gilbarg and N. S. Trudinger. Elliptic Partial Differential Equations of Second Order. Springer-Verlag, Berlin, Heidelberg, 1998 rev. and 2nd printing edition, 2001.
  19. [19]A. Gillman, A. Barnett, and P.-G. Martinsson. A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media. BIT Numerical Mathematics, 55(1):141–170, 2015.arxiv.org/abs/1308.5998
  20. [20]A. Gillman and P. Martinsson. A direct solver with o(n) complexity for variable coefficient elliptic pdes discretized via a high-order composite spectral collocation method. SIAM Journal on Scientific Computing, 36(4):A2023–A2046, 2014. arXiv.org report #1307.2665.arxiv.org/abs/1307.2665
  21. [21]A. Gillman, P. Young, and P.-G. Martinsson. A direct solver o(n) complexity for integral equations on one-dimensional domains. Frontiers of Mathematics in China, 7:217–247, 2012. 10.1007/s11464-012-0188-3.
  22. [22]W. Hackbusch. A sparse matrix arithmetic based on H-matrices; Part I: Introduction to H-matrices. Computing, 62:89–108, 1999.DOI
  23. [23]W. Hackbusch, B. Khoromskij, and S. Sauter. On ℋ²-matrices. In Lectures on Applied Mathematics, pages 9–29. Springer Berlin, 2002.
  24. [24]T. Kato. Perturbation Theory for Linear Operators. Springer Berlin, Heidelberg, 2012.
  25. [25]J. Kump, A. Yesypenko, and P.-G. Martinsson. A two-level direct solver for the Hierarchical Poincaré-Steklov method. Computers & Mathematics with Applications, 219:392–410, 2026.arxiv.org/abs/2503.04033
  26. [26]J. Levitt and P.-G. Martinsson. Linear-complexity black-box randomized compression of rank-structured matrices. SIAM Journal on Scientific Computing, 46(3):A1747–A1763, 2024.DOI
  27. [27]P. Martinsson. A direct solver for variable coefficient elliptic pdes discretized via a composite spectral collocation method. Journal of Computational Physics, 242(0):460 – 479, 2013.DOI
  28. [28]P. Martinsson and V. Rokhlin. A fast direct solver for boundary integral equations in two dimensions. J. Comp. Phys., 205(1):1–23, 2005.
  29. [29]P.-G. Martinsson. Fast Direct Solvers for Elliptic PDEs, volume CB96 of CBMS-NSF conference series. SIAM, 2019.DOI
  30. [30]H. Pfeiffer, L. Kidder, M. Scheel, and S. Teukolsky. A multidomain spectral method for solving elliptic equations. Computer physics communications, 152(3):253–273, 2003.DOI
  31. [31]H. A. Schwarz. Ueber einen Grenzübergang durch alternierendes Verfahren. Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich, 15:272–286, May 1870.DOI
  32. [32]B. Smith, P. Bjorstad, and W. Gropp. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, 2004.
  33. [33]B. F. Smith. An optimal domain decomposition preconditioner for the finite element solution of linear elasticity problems. SIAM Journal on Scientific and Statistical Computing, 13(1):364–378, 1992.DOI
  34. [34]A. Toselli and O. Widlund. Domain Decomposition Methods - Algorithms and Theory. Springer Series in Computational Mathematics. Springer Berlin Heidelberg, 2006.DOI
  35. [35]L. Trefethen and M. Embree. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, 2005.
  36. [36]J. Xia. Randomized sparse direct solvers. SIAM Journal on Matrix Analysis and Applications, 34(1):197–227, 2013.DOI
  37. [37]J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li. Fast algorithms for hierarchically semiseparable matrices. Numerical Linear Algebra with Applications, 17(6):953–976, 2010.DOI
  38. [38]J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li. Superfast multifrontal method for large structured linear systems of equations. SIAM J. Matrix Anal. Appl., 31(3):1382–1411, 2010.DOI
  39. [39]A. Yesypenko and P.-G. Martinsson. Gpu optimizations for the hierarchical poincaré-steklov scheme. In International Conference on Domain Decomposition Methods, pages 519–528. Springer, 2022.
  40. [40]A. Yesypenko and P.-G. Martinsson. Slablu: a two-level sparse direct solver for elliptic pdes. Advances in Computational Mathematics, 50(4), 2024.DOI
  41. [41]L. Zepeda-Núñez and L. Demanet. The method of polarized traces for the 2d helmholtz equation. Journal of Computational Physics, 308:347–388, 2016.
  42. [42]L. Zepeda-Núñez, A. Scheuer, R. J. Hewett, and L. Demanet. The method of polarized traces for the 3D helmholtz equation. Geophysics, 84(4):T313–T333, July 2019.

Paper details

vlnc:W_e7ppzrxv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents