Lawrence Berkeley National Laboratory

Abstract. This paper presents a multilevel tensor compression algorithm called tensor butterfly algorithm for efficiently representing large-scale and high-dimensional oscillatory integral operators, including Green’s functions for wave equations and integral transforms such as Radon transforms and Fourier transforms. The proposed algorithm leverages a tensor extension of the so-called complementary low-rank property of existing matrix butterfly algorithms. The algorithm partitions the discretized integral operator tensor into subtensors of multiple levels and factorizes each subtensor at the middle level as a Tucker-type interpolative decomposition, whose factor matrices are formed in a multilevel fashion. For a [Formula: see text]-dimensional ([Formula: see text]) integral operator discretized into a [Formula: see text]-mode tensor with [Formula: see text] entries, the overall CPU time and memory requirement scale as [Formula: see text], in stark contrast to the [Formula: see text] complexity of existing matrix algorithms such as matrix butterfly algorithms and fast Fourier transforms (FFTs), where [Formula: see text] is the number of points per direction. When comparing with other tensor algorithms such as quantized tensor train (QTT), the proposed algorithm also shows superior CPU and memory performance for tensor contraction. Remarkably, the tensor butterfly algorithm can efficiently model high-frequency Green’s function interactions between two unit cubes, each spanning 512 wavelengths per direction, which represents problems of scale over [Formula: see text] larger than that existing butterfly algorithms can handle, with the same amount of computation resources. On the other hand, for a problem representing 64 wavelengths per direction, which is the largest size existing algebraic matrix algorithms can handle, our tensor butterfly algorithm exhibits 200x speedups and [Formula: see text] memory reduction compared with existing ones. Moreover, the tensor butterfly algorithm also permits [Formula: see text]-complexity FFTs and Radon transforms up to [Formula: see text] dimensions.