An HSS-Matrix-Based Fast Direct Solver with Randomized Algorithm
Keywords:
Electric field integral equation, HSS matrix, randomized algorithmAbstract
Discretization of the electric field integral equation (EFIE) generally leads to dense impedance matrix. The resulting matrix, however, can be compressed in sparsity based on hierarchical structure and low rank approximation. In this paper, we propose an HSS-matrix-based fast direct solver for surface integral equation (SIE) that has a compression complexity of O(rN2) to analysis the large-scale electromagnetic problems, where r is a modest integer. The proposed solver efficiently compresses the dense matrices using a randomized algorithm and requires modest memory. Efficiency and accuracy is validated by numerical simulations. In addition, being an algebraic method, the HSS-matrix-based fast solver employs Green’s kernels and hence is suitable for other integral equations in electromagnetism.
Downloads
References
R. F. Harrington, Field Computation by Moment Methods. New York: Macmillan, 1968.
R. Coifman, V. Rokhlin, and S. Wandzura, “The fast multipole method for the wave equation: A pedestrian prescription,” IEEE Antennas Propag. Mag., vol. 35, no. 3, pp. 7-12, June 1993.
S. Ambikasaran and E. Darve, “An O(NlogN) fast direct solver for partial hierarchically semi-separable matrices,” Journal of Scientific Computing, vol. 57, no. 3, pp. 477-501, 2013.
J. Xia, S. Chandrasekaran, M. Gu, et al., “Fast algorithms for hierarchically semiseparable matrices,” Numerical Linear Algebra with Applications, vol. 17, no. 6, pp. 953-976, 2010.
W. Hackbusch, “A sparse matrix arithmetic based on -matrix,” Computing, vol. 62, no. 2, pp. 89- 108, 1999.
W. Hackbusch, “Data-sparse approximation by adaptive 2-matrices,”Computing, vol. 69, pp. 1-35, 2002.
S. Chandrasekaran, M. Gu, and T. Pals, “A fast ULV decomposition solver for hierarchically semiseparable representations,” Siam Journal on Matrix Analysis & Applications, vol. 28, no. 3, pp. 603- 622, 2006.
S. Chandrasekaran, M. Gu, and T. Pals, “Fast and stable algorithms for hierarchically semi-separable representations,” Technical Report, University of California: Berkeley, CA, 2004.
S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, X. Sun, AJ van der Veen, and D. White, “Some fast algorithms for sequentially semiseparable representation,” SIAM Journal on Matrix Analysis and Applications, vol. 27, pp. 341-364, 2005.
W. Chai and D. Jiao, “Fast-matrix-based direct integral equation solver with reduced computational cost for large-scale interconnect extraction,” IEEE Transactions on Components Packaging & Manufacturing Technology, vol. 3, no. 2, pp. 289- 298, 2013.
M. Ma and D. Jiao, “Exact-arithmetic HSSinversion algorithm for fast direct solution of electrically large volume integral equations,” International Conference on Electromagnetics in Advanced Applications, IEEE, pp. 597-599, 2016.
A. Manic, A. Smull, F. H. Rouet, et al., “Efficient scalable parallel higher order direct MoM-SIE method with hierarchically semiseparable structures for 3D scattering,” IEEE Transactions on Antennas & Propagation, pp. 99:1-1, 2017.
J. Xia and M. Gu, “Robust approximate Choleksy factorization of rank-structured symmetric positive definite matrices,” SIAM Journal on Matrix Analysis and Applications, vol. 31, pp. 2899-2920, 2010.
S. Li, M. Gu, L. Cheng, X. Chi, and M. Sun, “An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem,” SIAM Journal on Matrix Analysis and Applications, vol. 35, pp. 1038- 1057, 2014.
A. Napov and X. S. Li, “An algebraic multifrontal preconditioner that exploits the low-rank property,” Numerical Linear Algebra with Applications, vo. 23, no. 1, pp. 61-82, 2016.
F. H. Rouet and X. S. Li, et al., “A distributedmemory package for dense hierarchically semiseparable matrix computations using Randomization,” vol. 42, no. 4, p. 27, 2015.
P. G. Martinsson, “A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix,” Siam Journal on Matrix Analysis & Applications, vol. 32, no. 4, pp. 1251-1274, 2011.
P. Rocca and A. F. Morabito, “Optimal synthesis of reconfigurable planar arrays with simplified architectures for monopulse radar applications,” IEEE Transactions on Antennas & Propagation, vol. 63, no. 3, pp. 1048-1058, 2015.
