Compression properties in rank-structured Toeplitz solvers

Heather Wilber (CAM, Cornell University)

Toeplitz matrices are abundant in computational mathematics, and since they are also data sparse, it is natural to consider fast and superfast methods for solving linear systems involving them. If a matrix T is circulant in addition to being Toeplitz, then T is diagonalized by the discrete Fourier transform. If T is not circulant, then applying the discrete Fourier transform results in a matrix with off-diagonal blocks that are well-approximated by low rank matrices. Surprisingly little is known about the compressibility of these highly structured matrices in a theoretical sense, even though this compressibility is relied upon in practice in a number of solvers. In this talk, we show that the compression properties of these matrices can be thoroughly explained as a consequence of their displacement structure. Our results lead to extremely efficient displacement-based compression strategies that can be used to formulate fully adaptive superfast rank-structured Toeplitz solvers, as well as superfast solvers for related linear systems.