Multilevel Characteristic Basis Function Method with ACA for Accelerated Solution of Electrically Large Scattering Problems

Li Chenlu,Sun Yufa*,Wang Zhonggen,Wang Guohua

1.Key Laboratory of Intelligent Computing&Signal Processing,Ministry of Education,Anhui University,Hefei 230039,P.R.China;

2.College of Electrical and Information Engineering,Anhui University of Science and Technology,Huainan 232001,P.R.China

Abstract:The multilevel characteristic basis function method(MLCBFM)with the adaptive cross approximation(ACA)algorithm for accelerated solution of electrically large scattering problems is studied in this paper.In the conventional MLCBFM based on Foldy-Lax multiple scattering equations,the improvement is only made in the generation of characteristic basis functions(CBFs).However,it does not provide a change in impedance matrix filling and reducing matrix calculation procedure,which is time-consuming.In reality,all the impedance and reduced matrix of each level of the MLCBFM have low-rank property and can be calculated efficiently.Therefore,ACA is used for the efficient generation of two-level CBFs and the fast calculation of reduced matrix in this study.Numerical results are given to demonstrate the accuracy and efficiency of the method.

Key words:multilevel characteristic basis function method(MLCBFM);adaptive cross approximation(ACA);characteristic basis functions(CBFs);electromagnetic scattering

0 Introduction

The method of moments(Mo Ms)has been widely used in solving electrically large radiation and scattering problems.And it is notoriously expensive in terms of computation time and storage requirements because a dense matrix equation needs to be solved.In recent years,many iterative solvers to mitigate this problem have been presented,allowing for ever faster solution of ever larger problems.

A few examples of this approach are the multilevel fast multipole algorithm(MLFMA)[1],the adaptive integral method(AIM)[2],and the multilevel adaptive cross approximation(MLACA)[3].These methods achieved excellent performance of matrix vector production while suffered from the convergence problems of ill-conditioned matrices which caused by the surface integral equation formulation.

A common approach is to substitute the Mo M impedance matrix with a much smaller approximate representation.This category includes the multilevel matrix decomposition algorithm(MLMDA)[4-5]and the adaptive cross approximation(ACA)[6],which compress the matrix using pure algebraic methods.

Another category has been developed for reducing the number of degrees of freedom(DoFs).This reduction can be achieved by using the characteristic basis function method(CBFM)[7].It divides the target into several blocks,and a set of high-level basis functions called CBFs are used in each block.This method has been successfully applied to a wide variety of problems.

Nevertheless,for the electrically large scattering problems,it is unfortunate that the number of unknowns per block is increased in order to keep low number of blocks.It directly makes the generation procedure of CBFs increasingly expensive in time and storage consumption.To mitigate this problem,a multilevel version to the CBFM called the multilevel characteristic basis function method(MLCBFM)was presented in Ref.[8].The creative idea is that the CBFs defined in large blocks are expressed as a linear combination of the previously generated low-level CBFs defined in the relatively small blocks.It makes the MLCBFM achieve a high compression rate of the unknowns.Meanwhile,the ACA algorithm is employed to accelerate the interactions between the first-level CBFs.Considering the further compression,the solution of efficiently calculating the interactions between high-level CBFs is given in Ref.[9].Refs.[8-9]are based on the CBFM with a singular value decomposition(CBFM-SVD)[10].However,for ensuring the calculation precision,these methods need to excite each block by using multiple plane waves(PWs)incident from different angles and considering two polarization modes to construct CBFs for each block.This condition leads to increasing the number of CBFs.Therefore,the limitations of time and storage caused by large number of CBFs and large dimension of reduced matrix are still exist.

For the above reasons,another MLCBFM based on Foldy-Lax multiple scattering equations is presented in Ref.[11].These CBFs are constructed differently by using PWs incident from single angle,in which mutual coupling effects among all scatterers can be included systematically.The CBFs do not need to be regenerated anew for each angle,hence the number of CBFs is reduced.However,the results presented in Ref.[11]only concern dielectric scattering problems,where the domains associated with CBFs are confined to single objects(cubes)in multipleobject and the electrical size is very small.On the other hand,although the method in Ref.[11]improves the computational efficiency,it does not use any accelerated processing technology,thus the impedance matrix filling is so time-consuming that the advantages of the MLCBFM is concealed.To mitigate this problem,electrically large scattering problems are considered in this paper.In addition,the ACA is used in calculating all the interactions among the blocks,with the exception of the diagonal blocks and the interaction between adjacent blocks.

1 Characteristic Basis Function Method

The Mo M formulation yields the following matrix equation

Assuming that the target is dividing into M blocks,each block is subdivided into n cells.Eq.(1)can be transformed as follows

where Zij(i=1,2,3,…,M;j=1,2,3,…,M)represent the interaction impedance and self-impedance matrix;Jiand Eiare the induced surface current density and incident field of the i-th block.The CBFs are obtained by the Foldy-Lax multiple scattering equations[12].It indicates that the final exciting field of the i-th block is equal to the initial incident field plus scattered fields from all other blocks.The primary CBFs for each block only correspond to the incident field,and the secondary CBFs for one block state the mutual coupling effects with other blocks.The unknown induced current can be computed as follows.

(1)The primary CBFs JP

where Ziiand Eiare the self-impedance and incident field of the i-th block,i=1,2,3,…,M.

(2)The secondary CBFs JS1,JS2

The first-order secondary CBFs JS1of the ith block are computed by the scattered fields due to primary CBFs on all other scattered field.Similarly,we can calculate the additional secondary CBFs.

where i=1,2,3,…,M.

(3)The final current Jt

Assuming that the secondary CBFs are only computed to JS2,the final current of the i-th block is represent as

where i=1,2,3,…,M.The primary and secondary CBFs can be derived easily using conventional matrix inversion after Ziiare factorized.When Jiis replaced by Jti,the matrix size in Eq.(2)is now substantially reduced.The number of the unknowns in each scatterer is equal to the number of the coefficients which are employed in Eq.(6).The new matrix elements are in the form ofwith superscript T stands for the transpose operation.Then the coefficients of the final induced current ai,biand ci(i=1,2,3,…,M)can be obtained.

2 Multilevel Characteristic Basis Function Method

The conventional CBFM based on Foldy-Lax multiple scattering equations provides more efficient solution of scattering problems,unfortunately the impedance matrix filling,the CBFs generation and the reduced matrix calculation are still time and storage consuming.The number of DoFs grows with the electrical size of the blocks.This constitutes the main limitation of the CBFM for electrically large problems.To overcome this limitation,the MLCBFM is presented.In the MLCBFM,the target is firstly divided into M blocks,and then each block is subdivided into N subdomains.For instance,Fig.1 shows an example of analysis of a target using a two-level strategy.The target is divided into four(M=4)blocks and each of them is subdivided into the other nine(N=9)subdomains.For the solid dot in Fig.1,3{2}is used in representing the second subdomain of the third block.

Fig.1 Multilevel analysis of a target

Assuming only the first-order secondary CBFs and the second-order secondary CBFs are generated,the unknown induced currents are calculated as follows.

(1)The primary CBFs JP

In Eq.(6),the final current Jtifor the i-th block obtained by the CBFM mentioned in Section 1 is used as the primary CBFs of the i-th block in the MLCBFM.The incident field in the k-th subdomain of the i-th block is denoted as Ei{k}.

where i=1,2,3,…,M;k,h=1,2,3,…,N.

(2)The secondary CBFs JS1,JS2

The initial exciting field of the k-th subdomain in the i-th block is equal to scattered field derived from the primary CBFs on all blocks except the i-th block.The total current for the i-th block is used as the first-order secondary CBF of the i-th block

3 Adaptive Cross Approximation Algorithm

Although the MLCBFM can save much time in generating the CBFs,it is still time consuming because there are numerous vector-matrix-vector products(VMVPs)in the reduced matrix calculation procedure for electrically large scattering problems.And filling the impedance matricesandused in Eqs.(8)—(17)is computationally expensive.To solve this problem,a linear algebra algorithm called ACA is used for accelerating matrix-vector products.The impedance matrix that represents the interaction among non-contacting subdomains is also of low rank and can be compressed by using the ACA algorithm.For example,the impedance matrixcan be well approximated with this algorithm into a product of two full rank matrices,that is

where Ni{k},are the original block dimensions and r≪Ni{k},.r is the rank of the approximation.The iterative thresholdεis introduced to control the iterative process to achieve the ACA goal

where RNi{k}×Ni{h}is the error matrix,and ‖·‖stands for the Frobenius norm.Thus,the memory requirement decreased fromentries toentries.Then,the impedance matrixcan be compressed in the same way.After that,the reduced matrix calculation become fast by usingandi nstead of

4 Numerical Results

The performance of the proposed MLCBFMACA with a threshold of 10-3will be discussed in this section.It is applied in several different test examples for calculating the bistatic RCS.The results have been compared with that obtained by the FEKO software,CBFM-ACA,and MLCBFM without using the ACA algorithm.Simulation are performed on a personal computer equipped with the Intel(R)Core(TM).i7-3820 CPU with 3.6 GHz and 64 GB RAM.All the exciting fields are the uniform plane wave incident along the z axis direction,only have the Excomponent.

First we consider 16 conducting plates uniformly distributed on the same floor,each of them with the electrical size 3.33λ×3.33λat 1 GHz.And the distance between two adjacent plates is 3.33λ.The target is split into four blocks and 16 subdomains which are divided into 30 912 triangular patches,and the number of RWG basis functions is 45 472.The bistatic H-plane RCS is presented in Fig.2 for the FEKO,CBFM-ACA,MLCBFM and the presented method.It is found that the results are in good agreement.

Fig.2 H-plane bistatic RCS of the discrete PEC plates at 1 GHz

Then we consider the RCS of 16 discrete conducting cubes,each of them with the electrical size 1λ×1λ×1λat the frequency of 300 MHz.And the distance between two adjacent cubes is 1λ.The cubes are split into four blocks and 16 subdomains which are divided into 16 576 triangu-lar patches and 24 864 RWG basis functions.The bistatic RCSs calculated by the FEKO software,CBFM-ACA,MLCBFM and the present method are shown in Fig.3.It is found that the results obtained by the MLCBFM-ACA are more accurate than that obtained by the CBFM-ACA.

Fig.3 H-plane bistatic RCS of the PEC discrete cubes at 300 MHz

At last several random discrete targets are considered at the frequency of 300 MHz,which requires 17 160 RWG elements.The radius of each sphere is 0.5λ,the base radius and height of each cone are 0.5λand 1λ,respectively,the radius and height of each cylinder are 0.5λand 1λ,respectively,and the electrical size of each cube is 1λ×1λ×1λ.The distance between two adjacent targets is 1λtoo.These discrete geometries are split into four blocks and 16 subdomains.The bistatic RCS calculated by FEKO software,CBFM-ACA,MLCBFM and the presented method are shown in Fig.4.

Fig.4 H-plane bistatic RCS of PEC random discrete targets at 300 MHz

The CPU time of the CBFM-ACA,MLCBFM and MLCBFM-ACA are shown in Table 1.The calculating time concerns two-level CBFs generation,reduced matrix filling,solving matrix and RCS.MLCBFM and MLCBFM-ACA are more efficient than the conventional CBFM-ACA according to the calculating time.But in the impedance matrix filling procedure,MLCBFM without using any accelerate technique is computationally expensive,thus belying its advantage.As shown in Table 1,the presented method has solved this problem and enhanced the performance of MLCBFM.

Table 1 CPU time of CBFM-ACA,MLCBFM and the presented method

5 Conclusions

The MLCBFM-ACA has been studied for the analysis of electrically large scattering problems.MLCBFM can achieve a higher compression rate of the unknowns and become more efficient than the conventional CBFM for large structures.But it will lead to the growth of the impedance matrix filling time.The MLCBFM-ACA gives a perfect solution of this problem,and then enhances the performance of MLCBFM.The results in previous section are given to demonstrate the accuracy and efficiency of the MLCBFM-ACA.It can be seen that the MLCBFM-ACA shows more advantage for very large scattering problems.

Acknowledgements

This work was supported by the National Natural Science Foundation of China(No.61401003),the Specialized Research Fund for the Doctoral Program of Higher Education of China(No.20123401110006),and the Natural Science Research Project of Anhui Education(No.KJ2015A436).