ITC 2024 Cairo Invited Talk
Fast Algorithms of Computational
Electromagnetics: From Fast Fourier
Transform and Fast Multiple Method to
Hierarchical Matrices and Tensor Trains
Prof. Vladimir Okhmatovsk
Dept. of Electrical and Computer Engineering,
University of Manitoba, Canada
Email: vladimir.okhmatovski@umanitoba.ca
Web: https://umanitoba.ca/engineering/faculty-staff/electrical-and-computer-engineering-faculty-andstaff/vladimir-okhmatovski
Download
Bio and Abstract
Abstract
In the mid-90s the fast algorithms ushered a new era into the field computational science at large and
computational electromagnetics (CEM) in particular. The iterative fast algorithms based on FFT and Fast
Multiple Method (FMM) enabled solution of boundary element radiation and scattering problems of
unprecedented sizes exceeding billions of unknowns, while capturing underlying physics with full-wave
rigour and controlled precision. Such drastic increase in capacity of the pertinent surface and volume
integral equation solvers became possible due to reduction of their computational cost from O(N^2) and
O(N^3) to O(NlogN), earning the FMM the title of ’top 10 algorithms of the 20th century’.
In following two decades, the fast iterative methods made their way into commercial tools providing
engineers worldwide with revolutionary new modeling capabilities. Their extensive use, however, also
revealed significant challenges encountered by the iterative methods due to lack of convergence caused
by the resonant physical wave phenomena as well as the often-poor conditioning of matrix equations
stemming from the underlying integral equation formulations and/or their discretization schemes. To
address the convergence challenges plaguing the iterative fast solvers, the fast direct methods based on
the theory and algorithms of the hierarchical matrices (H-matrices) were developed in the 2000s. These
methods greatly alleviated convergence problems associated with the FMM and FFT methods by offering
robust preconditioners consuming O(NlogN) CPU time and memory comparable to the computational
resources required for fast evaluation of the dense matrix-vector products.
In this talk intended for a broad audience we will give an overview of the above iterative and direct fast
algorithms and demonstrate examples of their use in a broad variety of practical applications of electrical
and computer engineering ranging from transient electromagnetic analysis of power systems, to signal
integrity analysis in high-speed digital interconnects, to solution of large-scale scattering problems. The
recently emerged fast iterative and direct methods based on restructuring of the pertinent dense matrices
of BEMs into multi-dimensional tensors and revealing further data redundancies in them will be presented
to demonstrate the latest revolutionary promise in computational science to further reduce the state-ofthe-art O(NlogN) CPU and memory costs to O(logN).
Bio