Tutorial 3
Tensor Train Acceleration of Volume Integral Equation Solutions for EM Analysis of Interconnects

Vladimir I. Okhmatovski, University of Manitoba

Method of Moments (MoM) discretization of the Integral Equations (IEs) of electromagnetics results in dense matrix equation. Such matrix equations require prohibitively large computational resources when the number of basis functions used in discretization reaches hundreds of thousands and higher. Tensor Train (TT) decomposition of the MoM dense matrix equations has been recently proposed [1] to drastically reduce both the memory use for matrix storage and the CPU time required for its multiplication with a vector. Toeplitz matrix resulting from MoM discretization of Volume Integral Equation (VIE) can be represented as a multi-dimensional matrix and stored as a product of smaller dimensional matrices (tensors). Such product of smaller dimensional matrices, also known as the tensor train (TT), can reduce the matrix storage and matrix-vector multiplication complexities. In order to accelerate MoM solution of practical scattering problems we developed iterative Conjugate-Gradient- Tensor-Train (CG-TT) [2] and Precorrected-Tensor-Train (P-TT) [3] algorithms as well as direct AMEn-TT algorithm.

The CG-TT method works analogously with the well-established CG-FFT method [4]. Specifically, the VIE is MoM discretized with regular mesh of square elements and scattered field is cast into the form to discrete convolution. The Toeplitz matrix of the convolution is stored in TT-format. It is then used for fast evaluation of the pertinent matrix-vector products in the CG or GMRES iterative matrix solvers. To enable flexible meshing of the object with unstructured elements such as triangles, tetrahedrons, and others we developed the pre-corrected version of the algorithm. The latter projects onto a regular grid the basis and testing functions of the MoM defined on the unstructured elements similarly, with the Precorrected-FFT algorithm [5]. The point-to-point interactions forming the Toeplitz matrix are subsequently stored in the TT format, hence, enabling drastic reduction of memory and CPU time required for evaluation of the matrix-vector products during the iterative matrix solution.

In the non-iterative AMEn-TT algorithm we separately tensorize the Toeplitz matrix of interactions on the regular grid and the diagonal matrix describing spatial distribution of the material properties enabling definition of the arbitrarily shaped objects. The subsequent product of these matrices followed by the addition of the tensorized identity matrix produces resultant MoM matrix in TT format amenable to direct AMEn based solution.

Various numerical examples demonstrating O(logN) performance of the recently developed TT-based algorithms with over billion unknowns in the dense matrix equations resulting from full-wave MoM discretions of arbitrarily shaped geometries will be presented in this EPEPS Tutorial.

[1] I. V. Oseledets and E. Tyrtyshnikov, “TT-cross approximation for multidimensional arrays,” Linear Algebra and Its Applications, 432.1 (2010), pp. 70-88.

[2] Z. Chen, S. Zheng, and V. Okhmatovski, “Tensor train accelerated solution of volume integral equation for 2D scattering problems and magneto-quasi-static characterization of multi-conductor transmission lines,” IEEE Trans. Microwave Theory Tech., vol. 67, no. 6, pp. 2181-2196, June 2019.

[3] Z. Chen, L. Gomez, S. Zheng, A. Yucel, Z. Zhang, and V. Okhmatovski, “Sparsity-aware Precorrected Tensor Train algorithm for fast solution of 2-D scattering problems and current flow modeling on unstructured meshes,” EEE Trans. Microwave Theory Tech., vol. 67, no. 12, pp. 4833-4847, Dec. 2019.

[4] M. F. Catedra, R. F. Torres, J. Basterrechea, and E. Gago, The CG-FFT Method: Application of Signal Processing Techniques to Electromagnetics, Boston, MA, Artech House, 1995.

[5] J. R. Phillips and J. White, “A precorrected-FFT method for capacitance extraction of complicated 3-D structures,” Proc. Int. Conf. Computer-Aided Design (ICCAD), pp. 268 - 271, 1994.

Vladimir I. Okhmatovski received the M.S. degree in Radiophysics and Ph.D. degree in Antennas and Microwave Circuits from the Moscow Power Engineering Institute, Moscow, Russia, in 1996 and 1997, respectively. He was a Post-Doctoral Research Associate with the National Technical University of Athens from 1998 to 1999 and with the University of Illinois at Urbana-Champaign from 1999 to 2003. From 2003 to 2004, he was with the Department of Custom Integrated Circuits, Cadence Design Systems, as a Senior Member of Technical Staff. In 2004, he joined the Department of Electrical and Computer Engineering at the University of Manitoba, where is currently a Full Professor. His research interests are in the fast algorithms of electromagnetics, high-performance computing, modeling of interconnects, and inverse problems. Dr. Okhmatovski was a recipient of the 2017 Intel Corporate Research Council Outstanding Researcher Award. He was also a recipient of Outstanding ACES Journal Paper Award in 2007, Best Paper Award at the 3rd Electronic Packaging Technology Conference in 2001, and 1996 Best Young Scientist Report of the VI International Conference on Mathematical Methods in Electromagnetic Theory. He is a Registered Professional Engineer in the Province of Manitoba, Canada and a Fellow of Applied Computational Electromagnetics Society.