________________________________________________________________________________
3
3
Characteristic Basis Function Method
The limit of method of moments concerns the electrically large dimensions of the problem. The unknowns of the problem are connected to the edge of triangular patch of the mesh and at segment of wires. It follows that if the size of problem is electrically large, more unknowns have the problem, and therefore more can hardly be resolved. The objective of this chapter is to describe an efficient strategy to solve linear systems encountered when method of moments is used for electromagnetic problems. This new approach permits the solution of electrically large problems by decomposing the traditional method of moments matrix into a certain number of blocks. It is based on high level function, the characteristic basic functions (CBFs)[14]. The CBFs are special basis functions defined on macro domains (blocks) that include a relatively large number of conventional sub-domains arising in a triangular or rectangular patch modeling of the objects. These basis functions lead to a significant reduction in the number of unknowns. As a result, the size of the MoM matrix can be reduced to an order, which allows the use of a direct solver.
3.1
Characteristic Basis Function Method
Let us consider a complex 3-D object illuminated by a plane wave. As it has been shown in the previous chapter, in a conventional MoM approach, the whole surface is divided into triangles, rectangles or quadrilaterals, whit size ranging from λ/10 to λ/20. Applying this to the Electric Field Integral Equation (EFIE), we obtain a dense, complex system of the form:
( ) ( ) ( )
Z f J f =V f (3.1)
where Z is the MoM impedance matrix of dimension N×N, J and V are vectors of dimension N×1, N is the number of unknowns needed to describe the current distribution, and f is the frequency. For large and complex problem, the matrix system has to be solved for typically thousands of unknowns, and this poses a high burden CPU in terms of memory and time. The Characteristic Basis Function Method (CBFM) begins by dividing the geometry of the object to be analyzed into a number of Mblocks, as shown in Figure 3.1. There is no limitation on the number and size of blocks. The upper size is bounded by the available RAM
needed to handle the self-blocks that are s
ranges from a few hundred to a few thousand sub
while for 64 bit system the number of unknowns can be several hundred of thousand
Figure 3.1 Geometry of general object divided into K blocks
Let Nm indicate the number of unknowns on the obtain the CBFs [7,15], all blocks are extended by a domains are shown in Figure 3.1
overlapped domains and each of them has consists of extracting the Nme×Nme
each of the M enlarged blocks.
number of unknowns, so after extending operation every block
e e b b
N ×N self-impedance matrix Zii
the extended blocks. Then, the blocks are characterized
Functions (CBFs), constructed by exciting each block with Multiple Plane Waves ( Wave Spectrum - PWS), that is a set of
and φ angles (Figure 3.2). The number of PWs angles overestimated, initially, so that the CBFs would be
block, the shape of the geometry under investigation, and can account for evanescent desired.
blocks that are solved to generate the CBFs. Typically, the block size few thousand sub-domain type of unknowns for 32 bit system, while for 64 bit system the number of unknowns can be several hundred of thousand
Geometry of general object divided into K blocks
indicate the number of unknowns on the th
m domain, with m=1, 2,…,M
, all blocks are extended by a ∆ gap in all directions. The extended 1 in dotted lines. Now, we have M extended and partially overlapped domains and each of them has Nme unknowns, where
e m m
N >N . The next step sub-matrix Zme , from the original
N N
×
MoM matrixenlarged blocks. For simplicity, we assume that each block have the same number of unknowns, so after extending operation every block are described by
ii
Z , where i=1, 2,…,M and e
b
N is the number of unknowns in blocks are characterized through a set of Characteristic , constructed by exciting each block with Multiple Plane Waves (
that is a set of incident plane wave from
N
PWS uniformlyThe number of PWs angles ( NPWS =N Nθ φ )
overestimated, initially, so that the CBFs would be invariant with respect to the size of the geometry under investigation, and can account for evanescent
Typically, the block size for 32 bit system, while for 64 bit system the number of unknowns can be several hundred of thousand.
1, 2, ,
m … M . In order to gap in all directions. The extended extended and partially . The next step MoM matrix Z, for For simplicity, we assume that each block have the same d by the relative is the number of unknowns in haracteristic Basis , constructed by exciting each block with Multiple Plane Waves (or Plane uniformly-spaced
θ
) is deliberately invariant with respect to the size of the geometry under investigation, and can account for evanescent waves, if
Chapter 3 Characteristic Basis Function Method
________________________________________________________________________________
________________________________________________________________________________ 59
Figure 3.2 Plane Wave Spectrum on the blocks
To calculate the CBFs on the generic block i, we must solve the following system: ( ) RWG PWS
ii i i
Z f J =V (3.2)
where ViPWS is a Nbe×NPWS matrix containing the excitation vector used to illuminate the th
i block, JiRWG is a
e b PWS
N ×N matrix containing the RWGs stored column-wise;
Z
ii is the MoMimpedance matrix of the th
i block. In order to extract
Z
ii from the original MoM matrix, amatrix segmentation procedure can be used. To calculate the RWG we have to solve the linear system of equation (3.2), using LU factorization. This factorization has to be processed only one time and then the result can be stored, on hard disk or memory, and used whenever needed for generating the CBFs of the relative domain. Indeed, this new set of basis functions are constructed via the SVD approach. The J is expressed as the product of three matrices: ii
t
=UDV , 1, 2, ,
ii
J i= … M (3.3)
where
U
is an Nbe×NPWS orthogonal matrix,V
is ane PWS b
N ×N orthogonal matrix, and D is an NPWS×NPWS diagonal. As explained in the previous subsection, the elements of the latter matrix are the singular values of Z . At this point, to reduce the number of CBFs, a threshold ii procedure is used on the singular values. This procedure works by defining a ratio between singular values, that is:
max, l 1, 2, , . l PW l R
σ
Nσ
= = … (3.4)The above quantity is then compared with a certain threshold, e.g., 10E−3. Only those greater than threshold are retained. If the number of retained CBFs is K <NPW , we have reduced the number of basis from NPWS to K . This filtering process of eliminating the post-SVD CBFs is
Plane Wave Spectrum on Block Individual Block
important to reduce their redundancy and, consequently, improve the condition number of the reduced matrix. If, for simplicity, we assume that all of the blocks contain the same number of K CBFs after SVD (smaller than N Nθ φ), the solution to the entire problem is expressed as a linear combination of the M×K CBFs, as follows:
( )
1 1 ( ) k( ) M K CBF k m m m k J fα
f J f = = =∑∑
(3.5) In (3.5), CBFk m J is the thk CBF of the block m after SVD. The final step is to generate the reduced KM KM× matrix for the product on (3.1) once that
J
has been replaced by expression (3.5). The reduced coefficient matrix has the form shown in (3.6), where Zmn is the coupling matrix linking the original (not extended) blocksm
andn
, Zmm is the dense self-coupling matrix of these blocks, Jmm is the truncated-CBFs matrix of block after SVD. Note that each of the inner product entries in the above matrix results in a sub-matrix of size K K× , and the MoM matrix reduction involves MK2complex matrix-vector products.
11 11 11 11 12 22 11 1 22 21 11 11 22 22 22 2 1 11 2 22 t t t M MM t t t M MM KM KM t t t MM M MM M MM MM MM J Z J J Z J J Z J J Z J J Z J J Z J Z J Z J J Z J J Z J × = ⋯ ⋯ ⋮ ⋮ ⋱ ⋮ ⋯ (3.6)
Finally, the reduced system is solved for the unknown weight coefficients αmk( )f and the
solution is obtained at frequency f. Once the current density distribution has been derived, the electrical parameters such as RCS, scattered field, etc., can be computed.
The use of CBFs permits us to express the unknown induced current distribution regardless of the nature of the illuminating source. Moreover, their use leads to a reduction in the number of unknowns; thus, the reduced matrix can be handled by using a direct solver, without the need to iterate. Therefore, multiple excitations can be handled very efficiently. Generation of CBFs is one of the time-consuming and memory-demanding task. It requires the filling the self-impedance matrix Zii for the extended block and its factorization in an LU form. Then, the advantages of following this procedure is that it enables us to solve for multiple excitations using the same reduced matrix with a significant time-saving since only the right hand side (RHS) of the reduced system needs to be computed for a new excitation. Moreover, we can store the reduced matrix on the hard disk and reuse it whenever we need to analyze a new
Chapter 3 Characteristic Basis Function Method
________________________________________________________________________________
________________________________________________________________________________ 61
excitation. Furthermore, if the geometry within a particular block is modified, only the CBFs belonging to this block need to be recomputed.
3.2
Memory saving
The CBFM realizes a saving in the CPU running time and RAM requirement with respect to a conventional MoM technique. Indeed, in the conventional MoM the storage requires for solve the problem is related to the square of dimension of entire impedance matrix, while using CBFs the memory requirement is proportional to the square of the self impedance matrix of the extended block. Moreover, we obtain a consistent saving in the execution time, which becomes MO N
(
(
be)
3)
, as estimated by accounting for the largest computational burden. An order of the computational cost can be estimated by:(
3)
be M Cost O N P = (3.7)where P is the number of processors. By choosing smaller blocks, we can reduce the running time. Another quality of the CBFM is that this procedure is a highly parallelizable algorithm, because each block can be analyzed on a stand-alone basis on a parallel platform.
3.3
Singular Value Decomposition
The SVD [16] is a factorization of a real or complex matrix and is the most important single matrix decomposition for numerical methods. It decomposes a matrix into the product of three matrices: two orthogonal matrices and one diagonal matrix. We consider an n p× matrix X. The SVD of matrix leads to the following factorization:
t
X =UDV (3.8)
where
U
is ann k
×
orthogonal matrix,V
is a p×p orthogonal matrix and, is ak k
×
diagonal matrix with nonnegative real numbers on the diagonal, of the form: X
1 2 0 0 0 0 0 0 k
σ
σ
σ
⋯ ⋯ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋯ ⋯ (3.9)where k=min( , )n p . The diagonal entries of can be required to be ordered as . These diagonal elements are the singular values of X and they are usually stored from largest to smallest. Singular values of zero or near zero indicate that the matrix is singular or ill-conditioned.
Some properties of the SVD:
• If r=rank X( ), then σr+1=…=σk =0 •
σ
1= X 2• 2 2 2
1 p X F
σ
+…+σ
=• The minimum norm least squares solution to
Xa
=
b
is given by * † Ta =VD U b, where
†
D is the p×p diagonal matrix with diagonal entries
1 † if 0 0 if 0 i i i i
σ
σ
σ
σ
− > = = (3.10)3.4
Numerical results
In the following sections, it will show some examples of using the CBFM, showing the results obtained by numerical simulations. The fields achieved will be compared with those of a commercial software whenever possible. Furthermore, in the literature there are several examples that guarantee the correctness of the method.
3.4.1
PEC plate with a monopole
A monopole on a simple square PEC plate is presented. The side of the plate is 1 meter long, while the monopole is 0.15 m along the z axis. The wire is considerate very thin, 0.001 m. The geometry was simulated at 800 MHz, then the wavelength
λ
is 0.375 m and the medium edgeD
1 2 k 0
Chapter 3 Characteristic Basis Funct
________________________________________________________________________________
________________________________________________________________________________ of the triangular mesh is of 0.0375 m. The PEC is divided in two identical blocks and the monopole in the left one, as shown in
Figure 3
The number of surface unknowns
next figure, we illustrate the gain, in decibel, compared with FEK Characteristic Basis Function Method
________________________________________________________________________________
________________________________________________________________________________ of the triangular mesh is of 0.0375 m. The PEC is divided in two identical blocks and the
, as shown in Figure 3.3.
3.3 Square PEC plate with a monopole
The number of surface unknowns is 9465 for each blocks, while for the wire it is illustrate the gain, in decibel, compared with FEKO.
a)
________________________________________________________________________________
________________________________________________________________________________ of the triangular mesh is of 0.0375 m. The PEC is divided in two identical blocks and the
b)
Figure 3.4 Gain [dB] of monopole on a PEC square plate on: a) XZ plane; b) YZ plane
3.4.2
Frigate
In this paragraph, the bistatic RCS of a metallic warship (Figure 3.5) will be shown. The vessel is long 44.5 meter, about 44.5
λ
at the frequency of 300 MHz, 7.88 m of maximum width and 13.3 m of maximum height. Since the object is very electrically large, it was divided in 36 blocks. The total number of unknowns is 376251.Chapter 3 Characteristic Basis Function Method
________________________________________________________________________________
________________________________________________________________________________ 65
The simulation was made in parallel on a cluster, employing one node with 8 core and 32 GB of RAM. The simulation took 8 hours. In Figure 3.6 it can seen the bistatic RCS on the planes XZ (continuous green line) and YZ (dotted blue line) in decibel for square meter (dBsm), due to two plane waves incident: a) θ = °0 ,φ = °0 (electric field along x-axis) and b) θ = °0 ,φ =90°
(electric field along y-axis) .
a)
b)