Scientific Computing and Numerics (SCAN) Seminar

Heather WilberCornell University, CAM
Compression properties in rank-structured Toeplitz solvers

Monday, April 22, 2019 - 1:25pm
Gates 406

Abstract: 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.