Supercomputer Modelling of Electromagnetic Wave Scattering with Boundary Integral Equation Method

Abstract

Authors consider the approaches to increase efficiency of calculations in the problem of numerical modelling of electromagnetic wave scattering. To solve such kind of problems authors develop innovative variation of boundary integral equations method based on utilisation of integral equation with hyper singular integrals which can be solved with methods of piece-wise approximations and collocations. From numerical point of view the problem reduces to the solution of the system of linear equations which coefficients present the influence of cells of mesh on collocation points. The specialities of parallel algorithms for diffraction problems are described as for the straight solutions of the appearing linear systems so as for the approach utilising mosaic-skeleton approximation method which allows to solve linear equation system calculating only small part of matrix elements.

1 Introduction

Mathematical modelling of electromagnetic wave scattering by surfaces with complex shapes is actual problem for which solution there are various approaches. If wave length is much less than typical sizes of reflecting objects methods of physical optics and asymptotic methods work well. But in case of wave length comparable to objects sizes it is critical to formulate and numerically solve exterior boundary value problem for electromagnetic field in space outside the bodies. Modern grid and finite-element methods based on discretization of electromagnetic field in space allow to consider complex, including non-homogeneous, structure of the environment and different physical effects [1]. However, the significant problem here is that to fulfil boundary conditions on infinity one have to use calculating domain many times exceeding size of bodies. This leads to the great calculating difficulty of such methods. Herewith the requirement of smallness of space discretization step in comparison to wave length puts the limitation on utilisation of non-uniform meshes.

In case of modelling monochromatic wave processes in homogeneous environment the approach based on the method of boundary integral equations is very efficient [2, 3]. Here the solution of boundary problem is found from the integral representation with the integrals written for the boundary of the problem solution domain (body surfaces). The whole problem reduces to integral equations written on this boundary. With this the boundary conditions on infinity are fulfilled automatically and obtained solutions exactly satisfy the equations in the problem solution domain. For the numerical solution the grid is needed only on body surfaces. The problem of calculation efficiency remains actual here and raises from the necessity to model diffraction on bodies with complex shapes and the requirements to wide the diapason of investigated wave lengths.

Specific of methods of boundary integral equations is that in their discretization appear systems of linear equations with filled matrices which rank is defined by the number of cells in mesh. Here both problems of computation time reduction and element storage in operating memory are of great importance and practice shows that in many cases the memory problem is leading.

In this article two approaches to the solution of high complexity problems are described. First is the application of mosaic-skeleton approximations which allows to approximately solve the linear system calculating only comparably small number of its matrix elements [4]. This leads both to significant gain in computation time and in memory utilisation. Second is parallel computing. The implemented algorithms are based on a variation of numerical method for boundary integral equations developed in [5, 6]. This approach utilize integral equations with strongly singular integrals which can be solved by methods of piece-wise constant approximations and collocations. Authors describe the special aspects of parallel algorithms as for the straight solution of linear equation system so for approximate solution with mosaic-skeleton approximations.

2 Reduction of Problem to Integral Equation

Authors consider a 3D problem of scattering of a monochromatic electromagnetic field by a body or a system of bodies. Each body can be either a solid object bounded by a closed surface or a thin surface (a screen). The surfaces of the bodies are assumed to be ideally conducting, and the ambient medium is assumed to be homogeneous. The described below problem statement is classical [2, 7].

Let $\varSigma$ — total surface of bodies and screens which can be closed (surface of ideally conducting body), opened (ideally conducting screen) or consists of several components of such kind. Let us call $\varOmega$ — space domain outside considered bodies. The problem is to find the electric and magnetic field intensities, which will be sought in the form $\mathbf E_{full} (x)e^{ - i\omega t}$, $\mathbf H_{full} (x)e^{ - i\omega t}$, $x \in \varOmega$, where $\omega$ — circular frequency of electromagnetic field, t — time, $x = (x_1 ,x_2 ,x_3 ) \subset R^3$ — points in space. It is assumed than full electromagnetic field is inducted by primary electromagnetic emission where electric and magnetic field intensities can be represented as $\mathbf E_{ent} (x)e^{ - i\omega t}$ and $\mathbf H_{ent} (x)e^{ - i\omega t}$, respectively. With this full electric and magnetic field intensities we will find in form

$$\begin{aligned} \mathbf E_{full} (x) = \mathbf E_{ent} (x) + \mathbf E(x),\mathbf H_{full} (x) = \mathbf H_{ent} (x) + \mathbf H(x), \end{aligned}$$

(1)

$\mathbf E_{} \,,\mathbf H$ — unknown intensities of electric and magnetic fields which have to satisfy Maxwell equations ([2], p.109):

$$\begin{aligned} rot{} \mathbf E = i\omega \mu \mathbf H, \ \ \ rot{} \mathbf H = - i\omega \varepsilon \mathbf E. \end{aligned}$$

(2)

Here $\varepsilon$ and $\mu$ — dielectric and magnetic conductivity of environment. Either must be fulfilled Sommerfeld radiation conditions at infinity ([2], p.69, 116):

$$\begin{aligned} \left\{ {\frac{{\partial \mathbf E}}{{\partial \tau }} + ik\mathbf E = o\left( {\left| x \right| ^{ - 1} } \right) ,\frac{{\partial \mathbf H}}{{\partial \tau }} + ik\mathbf H = o\left( {\left| x \right| ^{ - 1} } \right) } \right. \left| x \right| \rightarrow \infty , \end{aligned}$$

(3)

where $\partial /\partial \tau$ — derivative in the direction of vector $\mathbf \tau = x/\left| x \right|$, and the condition $\left| {\nabla \mathbf E} \right| \subset L_2^{loc}$, $\left| {\nabla \mathbf H} \right| \subset L_2^{loc}$ ([7], subsection 22).

On the surfaces of irradiated objects $\varSigma$ the condition of equality to zero of tangential component of full electric field must be fulfilled and it may be written in form

$$\begin{aligned} \mathbf n \times \mathbf E_{} = \mathbf f, \end{aligned}$$

(4)

where $\mathbf f = - \mathbf n \times \mathbf E_{ent}$, where $\mathbf n$ — unit normal vector to the surface.

From now on we consider that on closed components of surface $\varSigma$ vector $\mathbf n$ has the direction outside the body, on each opened component it has violent direction but to one side on all surface.

Unknown tension of secondary electric field we’ll find using known integral representation ([2], p.110):

$$\begin{aligned} \mathbf E(x) = \int \nolimits _\varSigma {\mathbf e(\mathbf j(y),x,y)d\sigma _y } ,x \in \varSigma , \end{aligned}$$

(5)

where $\mathbf j\, = \mathbf j(x),\,\,x \in \,\,\varSigma$ — unknown tangential vector field on surface $\varSigma$ (surface currents),

$$\begin{aligned} \mathbf e(\mathbf j,x,y) = \{ grad_x div_x [\mathbf j\varPhi (x - y)] + k^2 \mathbf j\varPhi (x - y)\} \text{ where } \mathbf j \in C^3 ,\,x,y \in \varSigma ,\,x \ne y, \end{aligned}$$

(6)

$k^2 = \omega ^2 \varepsilon \mu$,

$$ \varPhi (x) = \frac{{e^{ikr} }}{{4\pi r}}, \ \ r = \left| x \right| .$$

Herewith Maxwell equations (2) and conditions on infinity (3) are fulfilled automatically.

As it shown in [5], for predefined surface field $\mathbf j = \mathbf j(x),x \in \varSigma$, when special smoothness requirements of this field are completed, vector field $\mathbf E$, defined by (5), has boundary values on each side of surface on surface $\varSigma$ and

$$ \mathbf n \times \mathbf E^ + = \mathbf n \times \mathbf E^ - = \mathbf n \times \mathbf E, $$

where $\mathbf E$ — straight value, got from the expression (5) when placing in it point $x \in \varSigma$. Herewith under integral expression, defined by formula (6) has singularity of order $\mathcal {O} \left( {\left| {x - y} \right| ^{ - 3} } \right)$ and the integral should be understood as hyper singular in the sense of the Hadamard finite value. Placing unknown field $\mathbf E(x)$ in boundary value (4), we get boundary integral equation with hyper singular integral:

$$\begin{aligned} \mathbf n(x) \times \int \limits _\varSigma {\{ grad_x div_x [\mathbf j(y)\varPhi (x - y)] + k^2 \mathbf j(y)\varPhi (x - y)\} d\sigma _y } = \mathbf f(x),\ \ x \in \varSigma . \end{aligned}$$

(7)

3 Numerical Scheme

For the numerical solution of integral Eq. (7) authors use the collocation method with utilisation of rectangle type quadratures basing on values of unknown function in nodes coinciding with collocation points, developed in [5]. Total surface $\varSigma$ is approximated by set of cells $\sigma _i$, $i = 1,...,n$. Authors use surface mesh which is constructed by following method. Surface $\varSigma$ is divided into modules, each of which is approximated by spline surface and comes a mapping of a plane rectangle to 3D space. Then this rectangle is divided to rectangular cells and this partition arises on module of surface $\varSigma$ some set of surface cells, where each has 4 vertices (surface may have poles near which cells have triangle form but considered as quadrangles with 2 coincided vertices).

In work [5] was developed the numerical method for approximation of integral Eq. (7), which uses only information about cell vertices and doesn’t need any other information about surface parametrization. On each cell the collocation point is chosen $x_i$ as the weight center of cell vertices (in the assumption that all vertices have equal masses), and normal ort is constructed $\mathbf n_i$ as a vector orthogonal to the diagonals of the cell. After that on each cell local orthonormal coordinate system is constructed with vectors $\mathbf e_{i1}$ and $\mathbf e_{i2} = \mathbf n_i \times \mathbf e_{i1}$ in plane, orthogonal to vector $\mathbf n_i$). Vector directions $\mathbf e_{i1}$ can be chosen violent in specified plane.

Let $\mathbf j_i$ — approximate value of function $\mathbf j(y)$ in point $x_i \in \sigma _i$, $i = 1,...,n$,

$$\begin{aligned} \mathbf j_i ^* (y) = (\mathbf j_i \times \mathbf n_i ) \times \mathbf n(y), \end{aligned}$$

(8)

$y \in \sigma _i$ — tangential vector field in cell $\sigma _i$, approximating on this cell function $\mathbf j(x)$. Replacing in Eq. (7) on each cell $\sigma _j$ function $\mathbf j(y)$ to function $\mathbf j_j ^*$ and writing this equation in nodes $x_i$, we get system of operator equations:

$$\begin{aligned} \sum \nolimits _{j = 1}^n {A_{ij} \mathbf j_j = \mathbf f(x_i ) }, \ i = 1,...,n, \end{aligned}$$

(9)

$$\begin{aligned} A_{ij} \mathbf j_j = \mathbf n_i \times \int \nolimits _{\sigma _j } {\mathbf e(\mathbf j_j^* (y),x,y)d\sigma _y }. \end{aligned}$$

(10)

Equation system (9) we can rewrite in the form of system of linear algebraic equations in respect to the vector coordinates $\mathbf j_i$, $i = 1,...,n$, in local bases constructed in grid cells:

$$\begin{aligned} \mathbf j_j = j_j^1 \mathbf e_j^1 + j_j^2 \mathbf e_j^2 . \end{aligned}$$

(11)

Placing vector $\mathbf j_j$ in form (11) to Eq. (9) and multiplying each equation on vectors $\mathbf e_i^l$, $l = 1,2$, we get system of linear algebraic equations:

$$\begin{aligned} \sum \limits _{\scriptstyle j = 1,...,n \atop \scriptstyle l = 1,2 } {a_{ij}^{ml} } j_j^l = f_i^m ,i = 1,...,n,m = 1,2, \end{aligned}$$

(12)

where $f_i^m = (\mathbf f_i ,\mathbf e_i^m ),\,\,i = 1,\,\,n\,,\,\,\,m = 1,\,2$, $a_{ij}^{ml} = (A_{ij} \mathbf e_j^l ,\mathbf e_i^m ),m,l = 1,2,i,j = 1,...,n.$

While calculating the coefficients of equation system (12) the integrals (10) are calculated by formulas from work [5] based on extraction of main singularity in explicit form. Herewith the integrals from dominant terms are calculated analytically. The remaining weakly singular integrals can be calculated numerically by method of additional partition of each cell and utilisation of rectangular type formulas with smoothing of singularity by multiplying on smoothing function. The details of calculation of weakly singular integrals are described in works [6].

In the examples below problem of plane wave scattering by ideally conducted bodies is considered. In this case primary field is written as:

$$\begin{aligned} \mathbf E_{ent} (x) = \mathbf E_0 e^{i\mathbf k\mathbf r} ,\mathbf H_{ent} (M) = \frac{{e^{i\mathbf k\mathbf r} }}{{\omega \mu }}\mathbf k \times \mathbf E_0 , \end{aligned}$$

(13)

where $\mathbf k$ — wave vector (herewith $k = \left| {\mathbf k} \right|$), $\mathbf r$ — radius vector of the point x, $\mathbf E_0$ — defined vector orthogonal to vector $\mathbf k$ (vector $\mathbf E_0$ defines wave polarization).

One of the purposes of solving scattering problem is to find directional pattern of secondary field. There patterns characterize dependence of radar-cross section $\sigma$ (RCS) in the direction of pre-set unit vector $\mathbf \tau$ defined by formula:

$$ \sigma (\mathbf \tau ) = \mathop {\lim }\limits _{R \rightarrow \infty } 4\pi R^2 \frac{{\left| {\mathbf E(R\mathbf \tau )} \right| ^2 }}{{\left| {\mathbf E_{ent} } \right| ^2 }} $$

from vector direction $\mathbf \tau$. Directional patterns usually made in form of dependence of values $\sigma$ from some angle, which defines this vector.

If the tension of electric field is represented in form (5), then for value $\sigma (\mathbf \tau )$ the following formula is true:

$$ \sigma (\mathbf \tau ) = \frac{{4\pi }}{{\left| {\mathbf E_{ent} } \right| ^2 }} \left| {\int \limits _\varSigma {\frac{k^2}{{4\pi }}e^{ - ik(\mathbf \tau ,y)} \left( {\mathbf j(y) - \mathbf \tau \left( {\mathbf j(y), \mathbf \tau } \right) } \right) d\sigma _y } } \right| ^2. $$

In numerical solution the last integral is calculated numerically with rectangle quadrature formula on the base of calculated approximate values $\mathbf j_i$, $i = 1,...,n$ of function $\mathbf j(y)$ on the cells of surface mesh.

4 Numerical Complexity of the Algorithm, Parallel Algorithm

Main calculation costs in numerical implementation of the algorithm are related to the solution of the system of linear equations (12), which consists of 2n complex equations, where n — number of cells. As it was mentioned above the number of cells is defined by the requirement of utilising small cells in comparison to body sizes and to wave length. So the calculation difficulty grows with increase of frequency of falling field.

In practice it is possible to save out following 2 classes of problems. First is to investigate characteristics of electromagnetic field in space and to construct directional pattern of secondary field for known primary field. Second class is to calculate inverse RCS which characterize intensity of secondary field in the direction back to the direction of falling field of predefined frequency, (with condition that $\mathbf \tau = - \mathbf k$), depending on the direction of vector $\mathbf k$. In first case the system (12) is solved single-fold and afterwards the result processing is done. In second case the system (12) is solved many times with the same matrix (matrix depends only on parameter k which is constant if frequency doesn’t change) and different right-hand sides.

Authors have implemented three different algorithms of linear system solution: with LU decomposition, with GMRES iteration algorithm [8] and with mosaic-skeleton matrix approximation [4] and GMRES algorithm.

In the first and second variants of algorithms parallel calculation of matrix elements is done and all elements are stored in RAM memory (own block for each processor) and afterwards the solution itself for one or several right-hand sides is done. The solution is implemented using standard Scalapack procedures for LU factorization or with GMRES iterative method. It is notable that GMRES does not give any advantages in time or in memory in this case because of very slow convergence (more than 1000 iterations) and implementations with restart do not converge at all. Herewith authors didn’t find any preconditioners that are able to achieve better convergence.

It was pointed out from practical calculations that problems of outstanding interest usually require meshes with 50000 and more cells. So it becomes clear that the main deficit resource is RAM and the algorithms of first interest are those that allow to calculate and store only small part of matrix elements.

The software was tested on supercomputer “Chebyshev” in Lomonosov Moscow State University supercomputer center and on INM RAS computer cluster. In first case 150 processors and 225 Gb of RAM were used in second case 16 processors and 180 Gb of RAM were used. In both cases different problems with grids up to $50\,000$ cells were successfully calculated. Significant increase of cell number required the increase in operational memory (as predicted). So successful calculations for the problem with 100000 cells were made on “Lomonosov” supercomputer in Lomonosov Moscow State University supercomputer center. About 400 Gb of RAM was used in calculations.

Further increase of cell number is limited by the lack of RAM memory to store matrix elements. So authors used mosaic-skeleton method in combination with GMRES method to solve the linear system. Mosaic-skeleton method allows to calculate and store about one percent of matrix elements and to use GMRES for system solution. In spite of slow convergence of iteration method taking into account significant memory economy for matrix storage this approach allows to reduce significantly the required RAM size and to increase the size of initial problem. Its implementation in described below.

5 Utilisation of Mosaic-Skeleton Approximations to the Solution of Diffraction Problems

To increase the calculation efficiency of the algorithm for linear system (12) solution the method of mosaic-skeleton approximations described in [4, 9,10,11,12] was implemented. The overview of recent methods of matrix compression can be found in works [13, 14]. The advantage of this method in comparison to others is generality and automatic precision control (the iteration nature of mosaic-skeleton approximations algorithm lead to precision increase on each step). The lack is implementation difficulty comparing to multipole methods, for example. Implementing this algorithm authors used great groundwork made in INM RAS.

Mosaic-skeleton approximation method is based on hierarchical decomposition of mesh cells into clusters basing on binary tree. Possessing a pair of cluster trees corresponding to pair of meshes representing our discretization we decompose matrix to a list of blocks of different sizes where each block represents interaction of a group of points-emitters $x_j$ (in our case center of each cell) with group of collocation points $x_i$. Blocks that representing interaction of geometrically distant clusters can be approximated with low-rank matrix (Fig. 1). On Fig. 1 grey color marks dense blocks, those for which all their elements should be calculated. Other blocks assumed to be low-rank. Using incomplete crest approximation algorithm [4] such blocks can be presented in form $B = U\cdot V^T$, where for block B of size $m\times n$ matrices U and V have sizes $m \times r$ and $n \times r$ respectively, $r \ll \min (m,n)$ — rank of block B. In such a way instead of storing $\mathcal {O}(mn)$ block elements it is possible to store only $\mathcal {O}((m+n)r)$ complex numbers.

Mosaic-skeleton approximations allow to compress matrix. To solve the system authors use GMRES [8] adapted to work with compressed matrices. This algorithm is based on parallel procedure of matrix-vector multiplication, where matrix is presented in skeleton format. No other operations are needed to solve the system.

To use GMRES for linear systems with multiple right-hand sizes authors made some modifications. Among right-hand sides let’s choose vector with residual with maximal norm. Let’s solve the system with GMRES method for this right-hand side and construct bases of subspace where the residual minimizes. Then we calculate the residual of remaining right-hand sides and again choose vector with maximal residual and repeat GMRES for this right-hand side with this widening the set of basic vectors. Using in such manner bases from previous iterations for new right-hand side we do much less steps for this right-hand side. So we solve the system for vectors from right-hand side until on the total base we got the maximal residual of remaining vectors is not achieved, which gives us the solution of desired accuracy. Finally the number of sorted out right-hand sides decreases in times.

The main time-consuming operation in matrix approximation is calculation of block approximations. The advantage of mosaic-skeleton method in that each block-approximation is independent from others and so can be paralleled into multiple processors by distributing blocks on different processors. Each processor has to calculate, construct and store approximations only for its own blocks. Processor intercommunication occurs only during the system solution step while matrix-vector multiplication is done. In iteration algorithm of system solution each processor multiplies only its blocks on vector and the results from different processors are summed.

Mosaic-skeleton method requires $\mathcal {O}((m+n)r)$ to approximate block $m\times n$ of rank r. If r is known, then block number can be distributed to processors before the block approximation itself. Calculating experiments made for different integrands show that value r is equal to $\mathcal {O}(\log ^\gamma (m+n))$, where $\gamma$ depends on integrand. For integral equation used in the described problem the calculation shows that $\gamma$ is approximately equal to 3 / 2. Notable that 3 / 2 does not depend on wave number.

Fig. 1.

Domain partition on clusters, partition tree and matrix partition on blocks: (a) 1 level; (b) 2 levels; (c) 3 levels; (d) 4 levels.

6 Numerical Results and Discussion

As an example calculation results and calculation costs are shown for the problem of plane wave scattering by a circular cylinder of finite length. Calculations were made on processors Intel Xeon E5-2670v3 2.30 GHz of INM RAS cluster (http://cluster2.inm.ras.ru/). Intel Fortran Compiler 9.0 for Linux (9.0.033) and OpenMPI Scalapack 2.0.2–4.3 was used.

Figure 2 shows the cylinder form and an example of grid on its surface. Calculations were made for frequencies 4 GHz (wave length $\lambda$ = 7.5 cm = H / 3.3), 8 GHz ($\lambda$ = 3.75 cm = H / 6.6) and 16 GHz ($\lambda$ = 1.875 cm = H / 13.2), where H — cylinder height.

Fig. 2.

Geometry and grid of the object.

Table 1. Required storage for matrix.

Table 2. Acceleration of matrix calculations for various number of processors. Number of cells 273600. Frequency 16 GHz.

Table 3. Acceleration of system solution for various number of processors. Number of cells 273600. Frequency 16 GHz.

Fig. 3.

4 GHz (a) 13482 cells; (b) 21760 cells; (c) 45784 cells.

Fig. 4.

8 GHz (a) 13482 cells; (b) 21760 cells; (c) 45784 cells.

Fig. 5.

16 GHz (a) 13482 cells; (b) 21760 cells; (c) 45784 cells; (d) 273600 cells.

Table 1 shows required storage for matrix of linear equation system compressed with accuracy $10^{-3}$ from the number of cells in mesh and emission frequency. Last column shows memory required to store full matrices. In brackets there is compression coefficient which is calculated as relation of memory required to store compressed matrix to memory required to store full matrix. Easy to mention that compression coefficient decreases with matrix size growth and increases with frequency growth.

Tables 2 and 3 show parallel acceleration rate for matrix compress operation and for linear system solution with GMRES method on multiple processors. Parallel acceleration rate shows the relation of times required to make the same calculations on one and $n_p$ processors. Note that computation time on 64 processors needed for matrix compression was 5 min 55 s and for solving system of linear equations was about 26 h.

Finally Figs. 3, 4 and 5 show RCS diagrams obtained from calculations. The correspondence of RCS represented in decibels $\tilde{\sigma }= 10\log \sigma$ in the direction of vector $\mathbf \tau = -\mathbf k$ from angle $\varphi$ defining the direction of vector $\mathbf k$ – see Fig. 2. Herewith considered vertical polarization of falling wave so vector $E_0$ in the expression (13) is orthogonal to plane Oxy. Calculation results (gray line) are compared to experimental data (black line) received from ITAE RAS. It can be seen that for frequency 4 GHz ($\lambda$ = 7.5 cm) the mesh of 13482 cells (maximal size of cell side is h = 0.375 cm) is enough for good agreement of calculation with experiment. It was shown that for frequency 8 GHz ($\lambda$ = 3.75 cm) the same mesh is also more or less enough for calculations. Local runs on graphs with calculation results disappear on mesh with 45784 cells (h = 0.2 cm). For the frequency 16 GHz ($\lambda$ = 1.875 cm) good agreement with experiment (without parasite local runs on the curve) was achieved on the mesh with 273600 cells ($h = 0.1$ cm). Note that all data were presented for vertical polarization because in horizontal polarization (vector $\mathbf E_0$ in the expression (13) lies in plane Oxy) for all frequencies coarser meshes were enough to achieve good agreement with experiment.

Hence, the calculation difficulty of the scattering problems grows with primary field frequency increase. This is caused by several reasons: the need to cut the mesh in correspondence to wave length; wave number k growth leads to increase of compress coefficient of matrix of linear equations system (12). Besides that iteration method convergence speed falls with growth of wave number k. So even for bodies with simple geometries parallel technologies are required when wave length is less than body size by an order or more.