Project Topics
Get Complete Project Material File(s) Now! »
Verifying the inversion formula
We now illustrate the closed form inversion formula (2.4.4) for the local multi-trace formulation by a numerical experiment. We consider a three dimensional version of the geometrical setting described at the beginning in Figure 2.1. Here Ω1 ∶= B(0, 0.5) is the open ball centered at 0 with radius 0.5, Ω2 ∶= ℝ3\[−1, +1]3, and Ω0 ∶= ℝ3 ⧵ Ω1 ∪ Ω2, see Figure 2.2.
For our numerical results, we discretize both MTFloc given by (2.3.7) leading to a matrix we denote by [MTFloc], and MTF−1 loc given by (2.4.4) leading to a matrix denoted by [MTF−1 loc]. Our discretization using the code bemtool1 is based on a Galerkin method where both Dirichlet and Neumann traces are approximated by means of continuous piece-wise linear functions on the same mesh. We use a triangulation with a mesh width ℎ = 0.35, and generated the mesh using Gmsh, see [GR09].
Preconditioner efficiency
Let us consider the operator P ∶= MTF−1 loc, obtained by choosing σ = − 1 2 and considering a constant wave number κ0 = 1 for all operators in equation (2.4.4). In this section, we evaluate the performance of P for preconditioning the local-MTF operator corresponding to a composite scattering problem in heterogenous media. We use the same domain as in section 2.5.1 and consider the problem of finding the solution 𝑢 of the following operator equation, M(κ0, κ1, κ2)𝑢 = 𝑏, (2.5.1) where 𝑏 is a constant 1-valued function and M(κ0, κ1, κ2) denotes the local-MTF operator considering the wave numbers different in each domain and given as κ0 = 1, κ1 and κ2 respectively in Ω0, Ω1 and Ω2. Next, we use P for preconditioning (2.5.1). Then, we discretize the problem to obtain a linear system which we solve using GMRES with a restart value of 40 and a tolerance of 10−8.
In figures 2.4 and 2.5 we present representative numerical tests which show that P is an efficient operator preconditioner for the local-MTF operator, and its effect is more notorious when the wave numbers are close to each other, which is in agreement with the theory. We compare our preconditioning technique against the classical block diagonal preconditioning operator D, which was used in the paper introducing local-MTF [HJH12, Sec. 5.3].
Stability of local MTF
In this section, we establish a generalized Gårding inequality for the local Multi-Trace formulation on
the unit sphere, by means of separation of variables. First of all, let us derive an expression of the norm on H−1/2(div, Γ) in vector spherical harmonics. Such an expression can be obtained by noting that the dissipative counterpart of the EFIE operator (i.e. associated to a purely imaginary wave number) is continuous and coercive on H−1/2(div, Γ) so that the corresponding bilinear form (𝑢, 𝑣)−1/2,div ∶= ∫ Γ×Γ 𝒢𝚤(𝑥 − 𝑦) (divΓ𝑢(𝑥)divΓ𝑣(𝑦) + 𝑢(𝑥) ⋅ 𝑣(𝑦))𝑑σ(𝑥, 𝑦), (3.7.1) yields a scalar product. Here 𝒢𝚤(𝑥) = exp(−|𝑥|)/(4π|𝑥|) and 𝚤 = √−1 is the imaginary unit. The vector fields X∥ 𝑛,𝑚 and X×𝑛 ,𝑚 form an orthogonal family with respect to this scalar product. As a consequence, to obtain an expression of a norm over H−1/2(div, Γ), one can rely on the decomposition of the dissipative EFIE on vector spherical harmonics. First observe that (𝑢, 𝑣)−1/2,div = ∫Γ(𝑛0 × γ0 t ⋅ SLκ(𝑢)) ⋅ 𝑣𝑑σ. As a consequence, using (3.4.4) we obtain (𝑢, 𝑣)−1/2,div = 𝑣⊤ ⋅ D𝑛 ⋅ 𝑢.
Low-rank Approximation using Subspace Iteration
Methods based on subspace iteration [GVL96, Ch. 7, 8] have shown to produce good rank-𝑘 approximation with cost between 𝒪(𝑚𝑛 log(𝑘)) and 𝒪(𝑚𝑛𝑘), see for example [DG17, HMT11, MRT06]. Algorithm 6 presents the basic subspace iteration method. This algorithm is well known in the literature and versions of it have been presented by different authors, see for example [Gu15, HMT11]. It takes as input an 𝑚 × 𝑛 matrix A, a small integer 𝑞 (that is usually taken as 𝑞 = 1 or 𝑞 = 2), and a random matrix Ω ∈ ℝ𝑛×𝑙 ; for the scope of this thesis, we create Ω using normal or uniform distributions, e.g. using,
respectively, routines randn or rand from MATLAB. Algorithm 6 iteratively computes Y = (AAT)𝑞AΩ and then gets its orthogonal basis Q ∈ ℝ𝑚×𝑙 , returning the low-rank matrix QB𝑘 , where B𝑘 is the rank 𝑘 truncated SVD of QTA.
Table of contents :
1 Introduction
1.1 Context of this work
1.2 Multi-Trace formulations
1.3 Matrix-compression and low-rank approximations
1.4 Summary and Contributions
I Muti-trace formulations
2 Local Multi-Trace formulation
2.1 Preliminaries
2.2 Functional and trace spaces
2.2.1 Trace spaces
2.3 Local Multi-Trace operator
2.4 Inverse of the Local Multi-Trace Operator
2.5 Numerical Experiments
2.5.1 Verifying the inversion formula
2.5.2 Preconditioner efficiency
2.6 Conclusions of the chapter
3 Stability of Local-MTF for Maxwell equation
3.1 Preliminaries
3.2 Problem setting
3.3 Local multi-trace operator for Maxwell equation
3.4 Separation of variables
3.5 Computation of accumulation points
3.6 Numerical results
3.7 Stability of local MTF
3.8 Conclusions of the chapter
II Low-rank approximations
4 Introduction to Low-Rank approximations
4.1 Preliminaries
4.2 Best Low-rank Approximation
4.3 Low-Rank Approximation using Pivoted QR Factorization
4.4 Low-rank Approximation using Subspace Iteration
4.5 Conclusions of the chapter
5 Affine low-rank approximations
5.1 Preliminaries
5.2 Affine Low-rank Approximation
5.2.1 Low-Rank Approximation as Projection of Rows and Columns
5.2.2 Getting an Affine Low-Rank Approximation
5.3 Correlation of Matrices Using their Gravity Center
5.3.1 Matrices with Exponentially Decreasing Singular Values
5.3.2 Characterization of Matrices using their Gravity Center
5.3.3 Measuring the Correlation of Matrices
5.3.4 Matrices with High Correlation
5.4 Numerical Experiments
5.4.1 Low-rank Approximation of Challenging Matrices
5.4.2 Approximation of the Matrix Norm
5.4.3 Analyzing the Correlation Coefficient
5.5 Conclusions of the chapter
6 Liner-time CUR approximations for BEM matrices
6.1 Preliminaries
6.2 CUR approximations
6.3 Linear-time CUR approximation via Geometric Sampling
6.3.1 Geometrical sampling
6.3.2 Bound on the error of CUR approximation with geometric sampling
6.3.3 Discussion on geometric sampling technique
6.4 Numerical Experiments
6.4.1 BEM matrix from Laplacian kernel
6.4.2 BEM matrix from Exponential kernel
6.4.3 BEM matrix from Gravity kernel
6.4.4 When ACA with partial pivoting fails
6.4.5 Approximating a Hierarchical matrix
6.5 Conclusions of the chapter
7 Conclusion
Bibliography
A CALRQR: Communication avoiding low-rank QR approximation
A.1 Communication avoiding algorithm low-rank QR
A.1.1 TSQR: Tall-Skinny QR factorization
A.1.2 Tournament pivoting
A.1.3 CALRQR: Communication avoiding low-rank QR factorization
A.2 Numerical Results
B Extra proofs and algorithms
B.1 Best Fitting Line Analysis
B.2 Proof of Lemma 4.1
B.3 Algorithms
B.3.1 CUR via Geometric sampling
