Lawrence Berkeley National Laboratory

A novel fast scalable parallel algorithm is proposed for the solution of large 3-D scattering problems based on: 1) the double (geometrical and current-approximation) higher order (DHO) method of moments (MoM) in the surface integral equation (SIE) formulation and 2) a direct solver for dense linear systems utilizing hierarchically semiseparable (HSS) structures. Namely, an HSS matrix representation is used for compression, factorization, and solution of the system matrix. In addition, a rank-revealing QR decomposition for memory compression is used, with a stopping criterion in terms of the relative rank tolerance value. A method for geometrical preprocessing of the scatterers based on the cobblestone distance sorting technique is employed in order to enhance the HSS algorithm accuracy and parallelization. Numerical examples show how the accuracy of the DHO HSS-MoM-SIE method is easily controllable by using the relative tolerance for the matrix compression. Moreover, the examples demonstrate low memory consumption, as well as much faster simulation time, when compared to the direct LU decomposition. The method enables dramatically faster monostatic scattering computations than iterative solvers and reduced number of unknowns when compared to low-order discretizations. Finally, great scalability of the algorithm is demonstrated on more than one thousand processes.