A Calderón multiplicative preconditioner for the electromagnetic Poincaré-Steklov operator of a heterogeneous domain with scattering applications

In the context of hybrid formulations, the Poincare-Steklov operator acting on traces of solutions to the vector Helmholtz equation in a heterogeneous interior domain with a smooth boundary is regularized by a well-known boundary integral operator related to the homogeneous exterior domain. For the first time, this property allows us to simultaneously construct a Calderon multiplicative preconditioner for the discretized operator and for a 3-D hybrid finite/boundary element method formulation, applicable to electromagnetic scattering problems. Numerical examples demonstrate the effectiveness of this novel preconditioning scheme, even for heterogeneous domains with non-smooth boundaries.

Related papers:

title: On the efficiency and quality of numerical solutions in CFD problems using the interface strip preconditioner for domain decomposition methods
abstract: In this paper, some pathologies found for simple tests solved by means of preconditioned full iterative schemes are presented. According to these results (Sections 4 and 5), the accuracy deterioration observed should be considered as a warning for the final application given to these solutions. Even though it is well known that full iterative solvers are not the best selection for comparison, they were chosen because they are widely used by the computational fluid dynamic (CFD) community for a diversity of complex fluid dynamics applications. FEM simulated solutions are compared with analytical solutions or measured data for problems that have been considered as 'benchmarks' in the CFD literature. For this purpose, the study of the solution obtained via parallelized iterative methods that have been extensively used (e.g. conjugate gradients (CG), GMRes global iteration and its variants, 'overlapping' and 'non-overlapping' additive Schwarz domain decomposition schemes) in CFD computations and those obtained with the new interface strip preconditioner ( 2003;  Engng 2005; 62(13):1873-1894) for the Schur complement method is carried out. The idea is to present the new solver as an alternative to obtain more accurate and faster solutions in the context of monolithic and non-monolithic schemes applied to a internal/external viscous compressible/incompressible flows around bodies of complex shapes. Therefore, the target of this work is to show how the reliability of CFD codes is affected by the solver selection and why domain decomposition methods should be viewed not only as a more efficient strategy, but also to guarantee the solution quality.

title: The Poincaré–Steklov Operator in Hybrid Finite Element-Boundary Integral Equation Formulations
abstract: The Poincaré-Steklov operator provides a direct relation between the tangential electric and magnetic field at the boundary of a simply connected domain, and a discrete equivalent of the operator can be constructed from the sparse finite element (FE) matrix of that domain by forming the Schur complement to eliminate the interior unknowns. Identifying the FE system matrix as a discretized version of the Poincaré-Steklov operator allows us to describe and analyze FE and hybrid finite element-boundary integral equation (FE-BIE) formulations from an operator point of view. We show how this operator notation provides substantial theoretical insight into the analysis of spurious solutions in hybrid FE-BIE methods, and we apply the theory on a TM scattering example to predict the breakdown frequencies of different hybrid formulations.

title: ON THE COMPLEX SYMMETRY OF THE POINCARÉ-STEKLOV OPERATOR
abstract: Employing Lorentz reciprocity and the Stratton-Chu formalism it is shown that the Poincaré-Steklov or admittance operator can be interpreted as a complex symmetric operator mapping the tangential electric field (instead of the equivalent magnetic current) onto the equivalent electric current. We show that the pertinent block Calderón projectors can be reformulated as operators with a block Hamiltonian structure. This leads to an explicitly complex symmetric Schur complement expression for both the interior and exterior admittance operators.

title: A stable well-conditioned integral equation for electromagnetism scattering
abstract: Finding a formulation for electromagnetic scattering of surfaces which is both well-posed and produces a well-conditioned linear system is still a challenging problem. We here propose one such formulation valid in the high-frequency regime. The mathematical analysis is provided and numerical results on rather complex geometries show the performance of the method.

title: Theory and Application of Steklov-Poincaré Operators for Boundary-Value Problems
abstract: This paper deals with interface operators in boundary value problems: how to define them, which is their meaning in both mathematical and physical sense, how to use them to derive numerical approximations based on domain decomposition approaches. When matching partial differential equations set in adjacent subregions of a domain Ω of ℝn, the interface operators ensure the fulfillement of transmission conditions between the different solutions. From the mathematical side, they make it possible to reduce the overall boundary value problem into a subproblem depending solely on the trace of the solution upon the interface. Once the solution of such a problem is available, the original solution can be reconstructed through the solution of independent boundary value problems within each subregion. The above independency feature is very likely behind the increasing interest for the use in the recent years of interface operators in scientific computing. Indeed, the subdomain approach yields a problem to be solved for the interface gridvalues only, then a family of reduced problems are left to solve simultaneously, hopefully by a multiprocessor architecture.

title: Domain decomposition methods : algorithms and theory
abstract: The purpose of this text is to offer a comprehensive and self-contained presentation of some of the most successful and popular domain decomposition preconditioners for finite and spectral element approximations of partial differential equations. Strong emphasis is placed on both algorithmic and mathematical aspects. Some important methods such FETI and balancing Neumann-Neumann methods and algorithms for spectral element methods, not treated previously in any monograph, are covered in detail.
Winner of the 2005 Award for Excellence in Professional and Scholarly Publishing - Mathematics/Statistics - of the Association of American Publishers

title: Adaptive FEM--BEM coupling with a Schur complement error indicator
abstract: In this paper an a-posteriori error estimate for non-linear coupled FEM-BEM equations is derived by using the Steklov-Poincare operator and hierarchical basis techniques. We obtain ''local'' error indicators which are based on two-level subspace decompositions with the additive Schwarz operator. We present an algorithm for adaptive error control which is driven by these error indicators and numerical results are included.

title: Boundary integral equations
abstract: This book is devoted to the basic mathematical properties of solutions to boundary integral equations and presents a systematic approach to the variational methods for the boundary integral equations arising in elasticity, fluid mechanics, and acoustic scattering theory. It may also serve as the mathematical foundation of the boundary element methods. The latter have recently become extremely popular and efficient computational tools in applications. The authors are well known for their fundamental work on boundary integral equations and related topics. This book is a major scholarly contribution to the modern theory of boundary integral equations and should be accessible and useful to a large community of mathematical analysts, applied mathematicians, engineers and scientists.

title: A preconditioner for the Schur complement matrix
abstract: A preconditioner for iterative solution of the interface problem in Schur Complement Domain Decomposition Methods is presented. This preconditioner is based on solving a global problem in a narrow strip around the interface. It requires much less memory and computing time than classical Neumann–Neumann preconditioner and its variants, and handles correctly the flux splitting among subdomains that share the interface. The aim of this work is to present a theoretical basis (regarding the behavior of Schur complement matrix spectra) and some simple numerical experiments conducted in a sequential environment as a motivation for adopting the proposed preconditioner. Efficiency, scalability, and implementation details on a production parallel finite element code [Sonzogni V, Yommi A, Nigro N, Storti M. A parallel finite element program on a Beowulf cluster.  a general purpose, parallel, multi-physics FEM program, 1999–2006] can be found in works [Paz R, Storti M. An interface strip preconditioner for domain decomposition methods: application to hydrology.  Eng 2005;62(13):1873–94; Paz R, Nigro N, Storti M. On the efficiency and quality of numerical solutions in cfd problems using the interface strip preconditioner for domain decomposition methods. ].

title: A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media
abstract: This paper presents a direct solution technique for the scattering of time-harmonic waves from a bounded region of the plane in which the wavenumber varies smoothly in space. The method constructs the interior Dirichlet-to-Neumann (DtN) map for the bounded region via bottom-up recursive merges of (discretization of) certain boundary operators on a quadtree of boxes. These operators take the form of impedance-to-impedance (ItI) maps. Since ItI maps are unitary, this formulation is inherently numerically stable, and is immune to problems of artificial internal resonances. The ItI maps on the smallest (leaf) boxes are built by spectral collocation on tensor-product grids of Chebyshev nodes. At the top level the DtN map is recovered from the ItI map and coupled to a boundary integral formulation of the free space exterior problem, to give a provably second kind equation. Numerical results indicate that the scheme can solve challenging problems 70 wavelengths on a side to 9-digit accuracy with 4 million unknowns, in under 5 min on a desktop workstation. Each additional solve corresponding to a different incident wave (right-hand side) then requires only 0.04 s.

title: A Calderón preconditioner for the EFIE operator without barycentric refinement of the mesh
abstract: Among the techniques to solve the ill-conditioning of the electric field integral equation (EFIE), multiplicative approaches based on Calderón identities are peculiarly effective. They rely on the use of a dual basis, like the Buffa-Christiansen (BC) or Chen-Wilton (CW) basis functions, to stably discretize the Hdiv-1/2-Hcurl-1/2 duality. These dual basis functions, unfortunately, require a barycentric refinement of the mesh resulting in an increase of the memory consumption. This work presents a multiplicative preconditioner for the EFIE operator that, differently from other Calderón preconditioning approaches, does not require the barycentric refinement of the mesh. The new preconditioner is obtained by chaining two standard system matrices (discretized on the standard, non-refined, mesh) with a suitably designed Gram matrix and appropriately chosen pre- and post-smoothers. A theoretical analysis proves the effectiveness of the proposed preconditioner and numerical results from realistic application scenarios corroborate the presented theory.

title: Well-conditioned boundary integral equation formulations for the solution of high-frequency electromagnetic scattering problems
abstract: We present several versions of Regularized Combined Field Integral Equation (CFIER) formulations for the solution of three dimensional frequency domain electromagnetic scattering problems with Perfectly Electric Conducting (PEC) boundary conditions. Just as in the Combined Field Integral Equations (CFIE), we seek the scattered fields in the form of a combined magnetic and electric dipole layer potentials that involves a composition of the latter type of boundary layers with regularizing operators. The regularizing operators are of two types: (1) modified versions of electric field integral operators with complex wavenumbers, and (2) principal symbols of those operators in the sense of pseudodifferential operators. We show that the boundary integral operators that enter these CFIER formulations are Fredholm of the second kind, and invertible with bounded inverses in the classical trace spaces of electromagnetic scattering problems. We present a spectral analysis of CFIER operators with regularizing operators that have purely imaginary wavenumbers for spherical geometries—we refer to these operators as Calderon–Ikawa CFIER. Under certain assumptions on the coupling constants and the absolute values of the imaginary wavenumbers of the regularizing operators, we show that the ensuing Calderon–Ikawa CFIER operators are coercive for spherical geometries. These properties allow us to derive wavenumber explicit bounds on the condition numbers of Calderon–Ikawa CFIER operators. When regularizing operators with complex wavenumbers with non-zero real parts are used—we refer to these operators as Calderon-Complex CFIER, we show numerical evidence that those complex wavenumbers can be selected in a manner that leads to CFIER formulations whose condition numbers can be bounded independently of frequency for spherical geometries. In addition, the Calderon-Complex CFIER operators possess excellent spectral properties in the high-frequency regime for both convex and non-convex scatterers. We provide numerical evidence that our solvers based on fast, high-order Nystrom discretization of these equations converge in very small numbers of GMRES iterations, and the iteration counts are virtually independent of frequency for several smooth scatterers with slowly varying curvatures.

title: A dual finite element complex on the barycentric refinement
abstract: A simplicial mesh on an oriented two-dimensional surface gives rise to a complex X • of finite element spaces centered on divergence conforming Raviart–Thomas vector fields and naturally isomorphic to the simplicial cochain complex. On the barycentric refinement of such a mesh, we construct finite element spaces forming a complex Y • , centered around curl conforming vector fields, naturally isomorphic to the simplicial chain complex on the original mesh and such that Y 2 − i is in L 2 duality with X i . In terms of differential forms this provides a finite element analogue of Hodge duality. To cite this article: A. Buffa, S.H. Christiansen, C. R. Acad. Sci. Paris, Ser. I 340 (2005).

title: Solution to 3-D electromagnetic problems discretized by a hybrid FEM/MOM method
abstract: A hybrid finite-element method/method of moments (FEM/MOM) is used to solve 3-D electromagnetic problems. We are focused on the solution to the resulting system of linear equations. Because of the hybrid nature of the FEM/MOM method, the coefficient matrix of the linear system has a very special structure with sparse but indefinite sub-matrices generated by the FEM and dense sub-matrices generated by the MOM. Preconditioned Krylov subspace methods are employed to solve the linear systems. Three preconditioners are considered and analyzed regarding the special structure of the coefficient matrix. Numerical results obtained from scattering and radiation problems show that the BICGSTAB method accelerated by a preconditioner, which employs several GMRES iterations to approximate the Schur complement, is reliable and efficient for the solution of the linear system.

title: A direct hierarchical multilevel preconditioner for the solution of finite element-boundary integral equations
abstract: Boundary integral (BI) equations in combination with fast solvers such as the multilevel fast multipole method are very well suited for solving electromagnetic scattering and radiation problems. In order to consider dielectric objects, the BI approach can be extended to the hybrid finite element-boundary integral (FE-BI) method. By using hierarchical higher order basis functions for the expansion of the unknowns, very accurate results can be obtained. To accelerate the convergence of iterative solvers, the usage of preconditioning methods is indispensable. In this work, a very efficient multilevel preconditioner is presented which is based on a factorization of the submatrices containing the interactions of the zeroth order divergence-conforming basis functions in the BI formulation and the corresponding lowest order curl-conforming basis of the FE method. Moreover, it is shown that the number of fill-ins can be effectively reduced by exploiting advanced reordering algorithms.

title: A fast algorithm for particle simulations
abstract: An algorithm is presented for the rapid evaluation of the potential and force fields in systems involving large numbers of particles whose interactions are Coulombic or gravitational in nature. For a system ofNparticles, an amount of work of the orderO(N2) has traditionally been required to evaluate all pairwise interactions, unless some approximation or truncation method is used. The algorithm of the present paper requires an amount of work proportional toNto evaluate all interactions to within roundoff error, making it considerably more practical for large-scale problems encountered in plasma physics, fluid dynamics, molecular dynamics, and celestial mechanics.

title: Rapid Solution of Integral Equations of Scattering Theory
abstract: The present paper describes an algorithm for rapid solution of boundary value problems for the Helmholtz equation in two dimensions based on iteratively solving integral equations of scattering theory. CPU time requirements of previously published algorithms of this type are of the order n 2 , where n is the number of nodes in the discretization of the boundary of the scatterer. The CPU time requirements of the algorithm of the present paper are n 4 3 , and can be further reduced, making it considerably more practical for large scale problems.

title: Fast and Efficient Algorithms in Computational Electromagnetics
abstract: From the Publisher: 
Here's a cutting-edge resource that brings you up-to-date with all the recent advances in computational electromagnetics. You get the most-current information available on the multilevel fast multipole algorithm in both the time and frequency domains, as well as the latest developments in fast algorithms for low frequencies and specialized structures, such as the planar and layered media. These algorithms solve large electromagnetics problems with shorter turn around time, using less computer memory. 
 
Complex problems that once required a supercomputer to solve, can now be solved on a workstation or personal computer with the innovative methods taught in this resource. The book introduces you to new advances in the perfectly matched layer absorbing boundary conditions, and offers you a thorough understanding of error analysis of numerical methods, fast-forward and inverse solvers for inverse problems, hybridization in computational electromagnetics, and asymptotic waveform evaluation.

title: A wideband fast multipole method for the Helmholtz equation in three dimensions
abstract: We describe a wideband version of the Fast Multipole Method for the Helmholtz equation in three dimensions. It unifies previously existing versions of the FMM for high and low frequencies into an algorithm which is accurate and efficient for any frequency, having a CPU time of O(N) if low-frequency computations dominate, or O(NlogN) if high-frequency computations dominate. The performance of the algorithm is illustrated with numerical examples.

title: On a Well-Conditioned Electric Field Integral Operator for Multiply Connected Geometries
abstract: All known integral equation techniques for simulating scattering and radiation from arbitrarily shaped, perfect electrically conducting objects suffer from one or more of the following shortcomings: (i) they give rise to ill-conditioned systems when the frequency is low (ii) and/or when the discretization density is high, (iii) their applicability is limited to the quasi-static regime, (iv) they require a search for global topological loops, (v) they suffer from numerical cancellations in the solution when the frequency is very low. This work presents an equation that does not suffer from any of the above drawbacks when applied to smooth and closed objects. The new formulation is obtained starting from a Helmholtz decomposition of two discretizations of the electric field integral operator obtained by using RWGs and dual bases respectively. The new decomposition does not leverage Loop and Star/Tree basis functions, but projectors that derive from them. Following the decomposition, the two discretizations are combined in a Calderon-like fashion resulting in a new overall equation that is shown to exhibit self-regularizing properties without suffering from the limitations of existing formulations. Numerical results show the usefulness of the proposed method both for closed and open structures.

title: Acoustic and Electromagnetic Equations : Integral Representations for Harmonic Problems
abstract: Preface.- Some wave equations.- Harmonic Helmholtz equation.- Integral representations and Integral equations.- Singular integral operators.- Maxwell equations and electromagnetic waves.- References.

title: Galerkin Boundary Element Methods for Electromagnetic Scattering
abstract: Methods based on boundary integral equations are widely used in die numerical simulation of electromagnetic scattering in the frequency domain. This article examines a particular class of these methods, namely the Galerkin boundary element approach, from a theoretical point of view. Emphasis is put on the fundamental differences between acoustic and electromagnetic scattering. The derivation of various boundary integral equations is presented, properties of their discretised counterparts are discussed, and a-priori convergence estimates for the boundary element solutions are rigorously established.

title: Operator Theory for Electromagnetics: An Introduction
abstract: I. BASIC THEORY Chapter 1: Electromagnetic Fundamentals / Chapter 2: Introductory Functional Analysis / Chapter 3: Introductory Linear Operator Theory / Chapter 4: Spectral Theory of Linear Operators / Chapter 5: Sturm-Liouville Operators II. APPLICATIONS IN ELECTROMAGNETICS Chapter 6: Poisson's and Laplace's Boundary-Value Problems: Potential Theory / Chapter 7: Transmission Line Analysis / Chapter 8: Planarly-Layered Media Problems / Chapter 9: Cylindrical Waveguide Problems / Chapter 10: Electromagnetic Cavities

title: Solving the EFIE at Low Frequencies With a Conditioning That Grows Only Logarithmically With the Number of Unknowns
abstract: A detailed analysis of the electric field integral equation (EFIE) at low frequencies is presented. The analysis, that is based on the Sobolev space mapping properties of the EFIE, explains the conditioning growth of the majority of currently available quasi-Helmholtz decomposition methods (such as Loop-Tree/Star, Loop-Rearranged Trees, etc.) that cure the EFIE low-frequency breakdown. It is shown that these methods have a conditioning that grows polynomially with the number of unknowns. To solve this problem, in this work we present a quasi-Helmholtz decomposition method that leads to an EFIE whose conditioning grows only logaritmically with the number of unknowns. This result is obtained by properly regularizing both the solenoidal and non-solenoidal part of the EFIE. The regularization is obtained by introducing a new set of loop hierarchical basis functions. Numerical tests are provided to confirm the results obtained by the theory.

title: Calculation of unbounded field problems in free space by a 3D FEM/BEM-hybrid approach
abstract: In recent times electromagnetic scattering calculations are often done by local methods such as Finite Elements or Finite Differences with approximate local absorbing boundary conditions because of their computational efficiency. The exact formulation of the field problem by combining a local with a global method (boundary integral) has the drawback that fully populated matrices have to be handled, making the method often computationally intensive. But there are many cases in which such hybrid-techniques have advantages as compared with pure local methods. We present an FEM/BEM-hybrid approach and show its application to scattering problems with several separated finite inhomogeneous regions and to combined scattering/radiation problems. The calculation of radiation problems (e. g. antennas nearby inhomogeneous bodies) is especially attractive because radiation structures can be modeled by well-established integral equation techniques. Particular attention is paid to the evaluation of the coupling integra...

title: Boundary integral formulations for homogeneous material bodies
abstract: There are many boundary integral formulations for the problem of electromagnetic scattering from and transmission into a homogeneous material body. The only formulations which give a unique solution at all frequencies are those which involve both electric and magnetic equivalent currents, and satisfy boundary conditions on both tangential E and tangential H. Formulations which involve only electric (or magnetic) equivalent currents, and those which involve boundary conditions on only tangential E (or tangential H) are singular at frequencies corresponding to the resonant frequencies of a resonator formed by a perfect conductor covering the surface of the body and filled with the material exterior to the body in the original problem.

title: A Transpose-Free Quasi-Minimal Residual Algorithm for Non-Hermitian Linear Systems
abstract: The biconjugate gradient method (BCG) for solving general non-Hermitian linear systems $Ax = b$ and its transpose-free variant, the conjugate gradients squared algorithm (CGS), both typically exhib...

title: A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling
abstract: In this paper, we analyze the main features and discuss the tuning of the algorithms for the direct solution of sparse linear systems on distributed memory computers developed in the context of a long term European research project. The algorithms use a multifrontal approach and are especially designed to cover a large class of problems. The problems can be symmetric positive definite, general symmetric, or unsymmetric matrices, both possibly rank deficient, and they can be provided by the user in several formats. The algorithms achieve high performance by exploiting parallelism coming from the sparsity in the problem and that available for dense matrices. The algorithms use a dynamic distributed task scheduling technique to accommodate numerical pivoting and to allow the migration of computational tasks to lightly loaded processors. Large computational tasks are divided into subtasks to enhance parallelism. Asynchronous communication is used throughout the solution process to efficiently overlap communication with computation. 
We illustrate our design choices by experimental results obtained on an SGI Origin 2000 and an IBM SP2 for test matrices provided by industrial partners in the PARASOL project.

title: libMesh: a C++ library for parallel adaptive mesh refinement/coarsening simulations
abstract: In this paper we describe the libMesh (http://libmesh.sourceforge.net) framework for parallel adaptive finite element applications. libMesh is an open-source software library that has been developed to facilitate serial and parallel simulation of multiscale, multiphysics applications using adaptive mesh refinement and coarsening strategies. The main software development is being carried out in the CFDLab (http://cfdlab.ae.utexas.edu) at the University of Texas, but as with other open-source software projects; contributions are being made elsewhere in the US and abroad. The main goals of this article are: (1) to provide a basic reference source that describes libMesh and the underlying philosophy and software design approach; (2) to give sufficient detail and references on the adaptive mesh refinement and coarsening (AMR/C) scheme for applications analysts and developers; and (3) to describe the parallel implementation and data structures with supporting discussion of domain decomposition, message passing, and details related to dynamic repartitioning for parallel AMR/C. Other aspects related to C++ programming paradigms, reusability for diverse applications, adaptive modeling, physics-independent error indicators, and similar concepts are briefly discussed. Finally, results from some applications using the library are presented and areas of future research are discussed.

title: Gmsh: A 3-D finite element mesh generator with built-in pre- and post-processing facilities
abstract: Gmsh is an open-source 3-D finite element grid generator with a build-in CAD engine and post-processor. Its design goal is to provide a fast, light and user-friendly meshing tool with parametric input and advanced visualization capabilities. This paper presents the overall philosophy, the main design choices and some of the original algorithms implemented in Gmsh.