A hierarchical FFT algorithm (HIL-FFT) for the fast analysis of transient electromagnetic scattering phenomena

Ali E. Yilmaz; Daniel S. Weile; Jian Ming Jin; Eric Michielssen

doi:10.1109/TAP.2002.802094

A hierarchical FFT algorithm (HIL-FFT) for the fast analysis of transient electromagnetic scattering phenomena

Ali E. Yilmaz, Daniel S. Weile, Jian Ming Jin, Eric Michielssen

Research output: Contribution to journal › Article › peer-review

Abstract

A fast algorithm for accelerating the time-marching solution of time-domain integral equations pertinent to the analysis of free-space electromagnetic scattering from perfectly conducting, platelike, and uniformly meshed structures is presented. The matrix-vector multiplications required by the time-marching scheme are accelerated by use of the fast Fourier transform (FFT). This acceleration is achieved in a multilevel fashion by hierarchically grouping sparse interactions to extract denser pieces that are efficiently evaluated by the FFT. The total computational cost and storage requirements of this algorithm scale as O(N_tN_s log² N_s) and O(N_s^1.5), respectively, as opposed to O(N_tN_s²) and O(N_s²) for classical time-marching methods (N_s and N_t denote the total number of spatial unknowns and time steps, respectively). Simulation results demonstrate the accuracy and efficiency of the algorithm.

Original language	English (US)
Pages (from-to)	971-982
Number of pages	12
Journal	IEEE Transactions on Antennas and Propagation
Volume	50
Issue number	7
DOIs	https://doi.org/10.1109/TAP.2002.802094
State	Published - Jul 2002

Keywords

Algorithms
Electromagnetic transient scattering
Integral equations
Time-domain analysis
Volterra integral equations

ASJC Scopus subject areas

Electrical and Electronic Engineering

Online availability

10.1109/TAP.2002.802094

Library availability

Discover UIUC Full Text

Cite this

@article{f8192bab693640eb98aa7098b223b48e,

title = "A hierarchical FFT algorithm (HIL-FFT) for the fast analysis of transient electromagnetic scattering phenomena",

abstract = "A fast algorithm for accelerating the time-marching solution of time-domain integral equations pertinent to the analysis of free-space electromagnetic scattering from perfectly conducting, platelike, and uniformly meshed structures is presented. The matrix-vector multiplications required by the time-marching scheme are accelerated by use of the fast Fourier transform (FFT). This acceleration is achieved in a multilevel fashion by hierarchically grouping sparse interactions to extract denser pieces that are efficiently evaluated by the FFT. The total computational cost and storage requirements of this algorithm scale as O(NtNs log2 Ns) and O(Ns1.5), respectively, as opposed to O(NtNs2) and O(Ns2) for classical time-marching methods (Ns and Nt denote the total number of spatial unknowns and time steps, respectively). Simulation results demonstrate the accuracy and efficiency of the algorithm.",

keywords = "Algorithms, Electromagnetic transient scattering, Integral equations, Time-domain analysis, Volterra integral equations",

author = "Yilmaz, {Ali E.} and Weile, {Daniel S.} and Jin, {Jian Ming} and Eric Michielssen",

note = "Funding Information: Manuscript received February 14, 2001; revised July 6, 2001. This work was supported in part by a grant from AFOSR via the MURI Program under Contract No. F49620-96-1-0025, and in part by the National Computational Science Alliance under DDM99003N and utilized the NCSA SGI/CRAY Origin 2000.",

year = "2002",

month = jul,

doi = "10.1109/TAP.2002.802094",

language = "English (US)",

volume = "50",

pages = "971--982",

journal = "IEEE Transactions on Antennas and Propagation",

issn = "0018-926X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "7",

}

TY - JOUR

T1 - A hierarchical FFT algorithm (HIL-FFT) for the fast analysis of transient electromagnetic scattering phenomena

AU - Yilmaz, Ali E.

AU - Weile, Daniel S.

AU - Jin, Jian Ming

AU - Michielssen, Eric

N1 - Funding Information: Manuscript received February 14, 2001; revised July 6, 2001. This work was supported in part by a grant from AFOSR via the MURI Program under Contract No. F49620-96-1-0025, and in part by the National Computational Science Alliance under DDM99003N and utilized the NCSA SGI/CRAY Origin 2000.

PY - 2002/7

Y1 - 2002/7

N2 - A fast algorithm for accelerating the time-marching solution of time-domain integral equations pertinent to the analysis of free-space electromagnetic scattering from perfectly conducting, platelike, and uniformly meshed structures is presented. The matrix-vector multiplications required by the time-marching scheme are accelerated by use of the fast Fourier transform (FFT). This acceleration is achieved in a multilevel fashion by hierarchically grouping sparse interactions to extract denser pieces that are efficiently evaluated by the FFT. The total computational cost and storage requirements of this algorithm scale as O(NtNs log2 Ns) and O(Ns1.5), respectively, as opposed to O(NtNs2) and O(Ns2) for classical time-marching methods (Ns and Nt denote the total number of spatial unknowns and time steps, respectively). Simulation results demonstrate the accuracy and efficiency of the algorithm.

AB - A fast algorithm for accelerating the time-marching solution of time-domain integral equations pertinent to the analysis of free-space electromagnetic scattering from perfectly conducting, platelike, and uniformly meshed structures is presented. The matrix-vector multiplications required by the time-marching scheme are accelerated by use of the fast Fourier transform (FFT). This acceleration is achieved in a multilevel fashion by hierarchically grouping sparse interactions to extract denser pieces that are efficiently evaluated by the FFT. The total computational cost and storage requirements of this algorithm scale as O(NtNs log2 Ns) and O(Ns1.5), respectively, as opposed to O(NtNs2) and O(Ns2) for classical time-marching methods (Ns and Nt denote the total number of spatial unknowns and time steps, respectively). Simulation results demonstrate the accuracy and efficiency of the algorithm.

KW - Algorithms

KW - Electromagnetic transient scattering

KW - Integral equations

KW - Time-domain analysis

KW - Volterra integral equations

UR - http://www.scopus.com/inward/record.url?scp=0036630226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036630226&partnerID=8YFLogxK

U2 - 10.1109/TAP.2002.802094

DO - 10.1109/TAP.2002.802094

M3 - Article

AN - SCOPUS:0036630226

SN - 0018-926X

VL - 50

SP - 971

EP - 982

JO - IEEE Transactions on Antennas and Propagation

JF - IEEE Transactions on Antennas and Propagation

IS - 7

ER -

A hierarchical FFT algorithm (HIL-FFT) for the fast analysis of transient electromagnetic scattering phenomena

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this