Tensor compression algorithms, fast direct volume integral equation solvers, and other optimal-complexity solvers

Background. Formulating an electromagnetic problem as a boundary or volume integral equation reduces the number of unknowns, yields operators with bounded condition numbers, and eases the handling of geometric complexity. The price is a dense system matrix whose storage and solution cost grow quadratically with the number of unknowns unless the matrix is compressed. Fast multipole and fast Fourier transform methods provide compression for a single solve, but uncertainty quantification, optimization, and broadband analysis require many related solves, and the redundancy across them is left unused.

Objective. Develop matrix compression and fast direct solution techniques whose complexity is optimal, or close to it, for integral equation solvers and for the collections of related simulations that arise in uncertainty quantification and design.

Approach. We exploit tensor and hierarchical low-rank structure: tensor-train compression of the Toeplitz matrices of volume integral equations; Tucker decomposition of the translation operators of fast multipole and fast Fourier transform accelerated surface integral equation solvers; a hierarchical off-diagonal butterfly approximate inverse used as a preconditioner and fast direct solver; and Tucker-enhanced, fast-Fourier-transform-accelerated inductance extraction for voxelized superconducting structures. Quantized tensor train surrogates provide fast uncertainty quantification for rough-surface and geometric variability.

Main results. Tensor-train compression stores the Toeplitz matrix of a volume integral equation in logarithmic memory for the Laplace kernel and near-linear memory for the Helmholtz kernel. The hierarchical off-diagonal butterfly inverse has O(N log² N) setup and O(N^1.5 log N) inversion cost for N unknowns and enables broad-permittivity, large-scale volume integral equation analysis. Tucker compression of translation operators often reduces their storage by about 90%.

Significance. These optimal-complexity building blocks are reused throughout the lab’s work: in the low-rank solvers for coil placement optimization, in the hierarchical-matrix bidomain neuron solvers, and in the scalable solvers for layered media and chip packaging.

Publications.

S. B. Sayed, Y. Liu, L. J. Gomez, and A. C. Yucel, "A Butterfly-Accelerated Volume Integral Equation Solver for Broad Permittivity and Large-Scale Electromagnetic Analysis," IEEE Transactions on Antennas and Propagation, vol. 70, no. 5, pp. 3549-3559, 2022. link

M. Wang, C. Qian, E. Di Lorenzo, L. J. Gomez, V. Okhmatovski, and A. C. Yucel, "SuperVoxHenry: Tucker Enhanced and FFT Accelerated Inductance Extraction for Voxelized Superconducting Structures," IEEE Transactions on Applied Superconductivity, vol. 31, 2021. link

Z. Chen, L. J. Gomez, S. Zheng, A. C. Yucel, Z. Zhang, and V. I. Okhmatovski, "Sparsity-Aware Precorrected Tensor Train Algorithm for Fast Solution of 2-D Scattering Problems and Current Flow Modeling on Unstructured Meshes," IEEE Transactions on Microwave Theory and Techniques, vol. 67, no. 12, pp. 4833-4847, 2019. link

A. C. Yucel, L. J. Gomez, and E. Michielssen, "Compression of Translation Operator Tensors in FMM-FFT Accelerated SIE Solvers via Tucker Decomposition," IEEE Antennas and Wireless Propagation Letters, vol. 16, pp. 2667-2670, 2017. link

A. C. Yucel, L. J. Gomez, W. Sheng, H. Bagci, and E. Michielssen, "Recent Trends in Uncertainty Quantification for Large-scale Electromagnetic Analysis: From Tensor Product Cubature Rules to Spectral Quantic Tensor Train Approximation," in New Trends in Computational Electromagnetics (O. Ergül, ed.), Institution of Engineering and Technology, pp. 1-31, 2019. link

L. J. Gomez, A. C. Yucel, W. Sheng, and E. Michielssen, "Fast Surrogate Model-Assisted Uncertainty Quantification via Quantized Tensor Train Decompositions," IEEE International Symposium on Antennas and Propagation and USNC-URSI Radio Science Meeting, July 2019.