Fast Direct LDL′ Solver for Method of Moments Electric Field Integral Equation Solution

作者

  • Yoginder Kumar Negi Supercomputer Education and Research Center Indian Institute of Science, Bangalore 560012, India
  • N. Balakrishnan Supercomputer Education and Research Center Indian Institute of Science, Bangalore 560012, India
  • Sadasiva M. Rao Naval Research Laboratory Washington DC 20375, USA

##plugins.pubIds.doi.readerDisplayName##:

https://doi.org/10.13052/2024.ACES.J.400401

关键词:

Adaptive Cross Approximation (ACA), Electric Field Integral Equation (EFIE), electromagnetics scattering, fast direct solver, matrix compression, Method of Moments (MoM)

摘要

This paper proposes a new fast direct solver using the block diagonalization method. In our proposed method, the symmetric half single-level compressed block matrix is factorized using the diagonalization method into block diagonal and upper triangle block LDL′ format where, due to symmetric property, L is a transpose of L′. The far-field blocks in the upper triangle row block are merged and compressed using Adaptive Cross Approximation (ACA) and QR factorization. The solution consists of solving the diagonal block matrix and matrix-vector multiplication of the compressed row blocks of the upper triangle matrices. Our results show that the factorization cost and memory scales to O(N1.5) and the solution process scales to O(N). The method generates an efficient solution process for solving large-scale electromagnetics problems.

##plugins.generic.usageStats.downloads##

##plugins.generic.usageStats.noStats##

##submission.authorBiographies##

##submission.authorWithAffiliation##

Yoginder Kumar Negi obtained the B.Tech. degree in Electronics and Communication Engineering from Guru Gobind Singh Indraprastha University, New Delhi, India, in 2005, M.Tech. degree in Microwave Electronics from Delhi University, New Delhi, India, in 2007, and the Ph.D. degree in engineering from Indian Institute of Science (IISc), Bangalore, India, in 2018. Negi joined Supercomputer Education Research Center (SERC), IISc Bangalore, in 2008 as a Scientific Officer. He is currently working as a Senior Scientific Officer in SERC IISc Bangalore. His current research interests include numerical electromagnetics, fast techniques for electromagnetic application, bio-electromagnetics, high-performance computing, and antenna design and analysis.

##submission.authorWithAffiliation##

N. Balakrishnan received the B.E. degree (Hons.) in Electronics and Communication from the University of Madras, Chennai, India, in 1972, and the Ph.D. degree from the Indian Institute of Science, Bengaluru, India, in 1979. He joined the Department of Aerospace Engi-neering, Indian Institute of Science, as an Assistant Professor, in 1981, where he became a Full Professor in 1991, served as Associate Director from 2005 to 2014, and is currently an INSA Senior Scientist at the Supercomputer Education and Research Centre. He has authored over 200 publications in international journals and international conferences. His current research interests include numerical electromagnetics, high-performance computing and networks, polarimetric radars and aerospace electronic systems, information security, and digital library. N. Balakrishnan is a fellow of The World Academy of Sciences (TWAS), the National Academy of Science, the Indian Academy of Sciences, the Indian National Academy of Engineering, the National Academy of Sciences, and the Institution of Electronics and Telecommunication Engineers.

##submission.authorWithAffiliation##

Sadasiva M. Rao obtained his Bachelors, Masters, and Doctoral degrees in electrical engineering from Osmania University, Hyderabad, India, Indian Institute of Science, Bangalore, India, and University of Mississippi, USA, in 1974, 1976, and 1980, respectively. He is well known in the electromagnetic engineering community and included in Thomson Scientifics’ Highly Cited Researchers List. Rao has been teaching electromagnetic theory, communication systems, electrical circuits, and other related courses at the undergraduate and graduate level for the past 30 years at various institutions. At present, he is working at the Naval Research Laboratories, USA. He has published/presented over 200 papers in various journals/conferences. He is an elected Fellow of IEEE.

参考

R. F. Harrington, Field Computation by Moment Methods. Malabar, Florida: Krieger Publishing Co., 1982.

J.-M. Jin, The Finite Element Method in Electromagnetics. Hoboken, New Jersey: John Wiley & Sons, 2015.

A. Taflove and S. C. Hagness, Computational Electrodynamics: The Finite-Difference Time-Domain Method. Norwood, MA: Artech House, 1995.

W. C. Chew, J.-M. Jin, E. Michielssen, and J. Song, Fast and Efficient Algorithms in Computational Electromagnetics. Norwood, MA: Artech House, 2000.

E. Bleszynski, M. Bleszynski, and T. Jaroszewicz, “AIM: Adaptive integral method for solving largescale electromagnetic scattering and radiation problems,” Radio Science, vol. 31, no. 5, pp. 1225-1251, Dec. 1996.

J. R. Phillips and J. K. White, “A pre-corrected FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, no. 10, pp. 1059-1072, Oct. 1997.

M. Bebendorf, “Approximation of boundary element matrices,” Numerische Math., vol. 86, no. 4, pp. 565-589, June 2000.

S. Kurz, O. Rain, and S. Rjasanow, “The adaptive cross-approximation technique for the 3D boundary-element method,” IEEE Transaction on Magnetics, vol. 38, no. 2, pp. 421-424, Mar. 2002.

S. Kapur and D. E. Long, “IES3: Efficient electrostatic and electromagnetic solution,” IEEE Computer Science and Engineering, vol. 5, no. 4, pp. 60-66, Dec. 1998.

W. Hackbusch, “A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices,” Computing, vol. 62, no. 2, pp. 89-108, Apr. 1999.

W. Hackbusch and B. N. Khoromskij, “A sparse H-Matrix arithmetic. Part II: Application to multidimensional problems,” Computing, vol. 64, pp. 21-47, Feb. 2000.

Y. K. Negi, “Memory reduced half hierarchal matrix (H-Matrix) for electrodynamic electric field integral equation,” Progress in Electromagnetics Research Letters, vol. 96, pp. 91-96, Feb. 2021.

A. F. Peterson, “The ‘interior resonance’ problem associated with surface integral equations of elec-tromagnetics: Numerical consequences and a survey of remedies,” Electromagnetics, vol. 10, no. 3, pp. 293-312, July 1990.

R. E. Hodges and Y. Rahmat-Samii, “The evaluation of MFIE integrals with the use of vector triangle basis functions,” Microwave and Optical Technology Letters, vol. 14, no. 1, pp. 9-14, Jan. 1997.

P. Yla-Oijala and M. Taskinen, “Application of combined field integral equation for electromagnetic scattering by dielectric and composite objects,” IEEE Transactions on Antennas and Propagation, vol. 53, no. 3, pp. 1168-1173, Mar. 2005.

Y. Saad, “ILUT: A dual threshold incomplete LU factorization,” Numerical Linear Algebra Application, vol. 1, no. 4, pp. 387-402, 1994.

Y. K. Negi, N. Balakrishnan, Sadasiva M. Rao, and Dipanjan Gope, “Null-field preconditioner with selected far-field contribution for 3-D full-wave EFIE,” IEEE Transactions on Antennas and Propagation, vol. 64, no. 11, pp. 4923-4928, Aug. 2016.

Y. K. Negi, N. Balakrishnan, and Sadasiva M. Rao, “Symmetric near-field Schur’s complement preconditioner for hierarchal electric field integral equation solver,” IET Microwaves, Antennas & Propagation, vol. 14, no. 14, pp. 1846-1856, Nov. 2020.

D. Gope, I. Chowdhury, and V. Jandhyala, “DiMES: Multilevel fast direct solver based on multipole expansions for parasitic extraction of massively coupled 3D microelectronic structures,” in Proceedings of the 42nd annual Design Automation Conference, Anaheim, CA, USA, pp. 159-162, June 2005.

D. Sushnikova, L. Greengard, M. O’Neil, and M. Rachh, “FMM-LU: A fast direct solver for multiscale boundary integral equations in three dimensions,” Multiscale Modeling & Simulation, vol. 21, no. 4, pp. 1570-1601, Dec. 2023.

L. Greengard, D. Gueyffier, P.-G. Martinsson, and V. Rokhlin, “Fast direct solvers for integral equations in complex three-dimensional domains,” Acta Numerica, vol. 18, pp. 243-275, May 2009.

M. Ma and D. Jiao, “Accuracy directly controlled fast direct solution of general H∧2-Matrices and its application to solving electrodynamic volume integral equations,” IEEE Transactions on Microwave Theory and Techniques, vol. 66, no. 1, pp. 35-48, Jan. 2018.

Y. K. Negi, N. Balakrishnan, and S. M. Rao, “Fast power series solution of large 3-D electrodynamic integral equation for PEC scatterers,” Applied Computational Electromagnetics Society (ACES) Journal, vol. 36, no. 10, pp 1301-1311, Oct. 2021.

Y. K. Negi, N. Balakrishnan, and S. M. Rao, “Multilevel power series solution for large surface and volume electric field integral equation,” Applied Computational Electromagnetics Society (ACES) Journal, vol. 38, no. 5, pp. 297-303, Sep. 2023.

S. Huang and Y. J. Liu, “A new fast direct solver for the boundary element method,” Computational Mechanics, vol. 60, pp. 379-392, Sep. 2017.

Z. Rong, M. Jiang, Y. Chen, L. Lei, X. Li, and Z. Nie, “Fast direct solution of integral equations with modified HODLR structure for analyzing electromagnetic scattering problems,” IEEE Transactions on Antennas and Propagation, vol. 67, no. 5, pp. 3288-3296, May 2019.

A. Heldring, J. M. Rius, J. M. Tamayo, J. Parron, and E. Ubeda, “Fast direct solution of Method of Moments linear system,” IEEE Transactions on Antennas and Propagation, vol. 55, no. 11, pp. 3220-3228, Nov. 2007.

J. Shaeffer, “Direct solve of electrically large integral equations for problem sizes to 1 M unknowns,” IEEE Transactions on Antennas and Propagation, vol. 56, no. 8, pp. 2306-2313, Aug. 2008.

W. C. Gibson, “Efficient solution of electromagnetic scattering problems using multilevel adaptive cross approximation and LU factorization,” IEEE Transactions on Antennas and Propagation, vol. 68, no. 5, pp. 3815-3823, May 2020.

S. M. Rao, D. R. Wilton, and A. W. Glisson, “Electromagnetic scattering by surfaces of arbitrary shape,” IEEE Transactions on Antennas and Propagation, vol. 30, no. 3, pp. 409-418, May 1982.

Y. K. Negi, V. P. Padhy, and N. Balakrishnan, “Re-compressed H-Matrices for fast electric field integral equation,” in IEEE-International Conference on Computational Electromagnetics (ICCEM 2020), Singapore, pp. 24-26, Aug. 2020.

M. Neumann, “On the Schur complement and the LU-factorization of a matrix,” Linear and Multilinear Algebra, vol. 9, no. 4, pp. 241-254, Jan. 1981.

S. M. Rao, “A true domain decomposition procedure based on Method of Moments to handle electrically large bodies,” IEEE Transactions on Antennas and Propagation, vol. 60, no. 9, pp. 4233-4238, Sep. 2012.

Y. K. Negi, N. Balakrishnan, and S. M. Rao, “Schur decomposition fast direct solver for volume surface integral equation,” in 2024 IEEE International Symposium on Antennas and Propagation and INC/USNC-URSI Radio Science Meeting (APS/INC-USNC-URSI), Firenze, Italy, pp. 973-974, July 2024.

J. Shaeffer, “Low-rank matrix algebra for the Method of Moments,” Applied Computational Electromagnetics Society (ACES) Journal, vol. 33, no. 10, pp. 1052-1059, Oct. 2018.

K. L. Virga and Y. Rahmat-Samii, “RCS characterization of a finite ground plane with perforated apertures: Simulations and measurements,” IEEE Transactions on Antennas and Propagation, vol. 42, no. 11, pp. 1491-1501, Nov. 1994.

A. C. Woo, H. T. G. Wang, M. J. Schuh, and M. L. Sanders, “EM programmer’s notebook-benchmark radar targets for the validation of computational electromagnetics programs,” IEEE Antennas and Propagation Magazine, vol. 35, no. 1, pp. 84-89, Feb. 1993.

L. Y. Zhuan, ButterflyPACK [Online]. Available: https://github.com/liuyangzhuan/ButterflyPACK2

##submission.downloads##

已出版

2025-04-30

##submission.howToCite##

[1]
Y. K. . Negi, N. . Balakrishnan, 和 S. M. . Rao, 《Fast Direct LDL′ Solver for Method of Moments Electric Field Integral Equation Solution》, ACES Journal, 卷 40, 期 04, 页 268–278, 4月 2025.

期

2025: Vol 40 Iss 4

栏目

General Submission

##category.category##