ETD

• data-sparsity
• functions of Toeplitz matrices
• HSS
• Low-Rank
• matrix function

The thesis develops a method for computing functions of Toeplitz matrices, with an emphasis on efficient evaluation of expressions of the form f(T)v. Toeplitz matrices appear in applications such as discretized differential and integral equations, signal processing, and time series analysis, and are computationally attractive because they are defined by few parameters.
Chapter 1 recalls the tools used throughout the work: low-rank approximations based on QR, SVD, and interpolative decomposition, including randomized variants, and displacement theory, which characterizes structured matrices via Sylvester equations. Through the Fourier transform, Toeplitz matrices are mapped into Cauchy-like matrices. These have off-diagonal blocks with rapidly decaying singular values, a property quantified using Zolotarev numbers, which provides rank bounds used later for compression.
Chapter 2 introduces hierarchical matrix formats, in particular HODLR and HSS matrices, which reduce storage and computation by exploiting low-rank structure. The HSS format is described in terms of its binary tree representation and nested bases. The chapter compares deterministic and randomized compression schemes and develops a specialized method for Cauchy-like matrices based on interpolative decomposition combined with the fast ADI iteration. The method reduces cost by reusing basis information across blocks.
Chapter 3 presents the main contribution of the thesis: an algorithm for computing functions of matrices in telescopic (nested low-rank) form, which corresponds to the HSS structure. After introducing block rational Krylov subspaces, the chapter combines them with results on low-rank updates of matrix functions to build a recursive procedure that constructs a telescopic representation of f(H). This extends a recent algorithm by Casulli, Kressner, and Robol to nonsymmetric matrices.
Chapter 4 contains numerical tests. It first confirms the singular value decay predicted in Chapter 1 for Cauchy-like matrices derived from Toeplitz matrices. It then compares several HSS compression strategies. The proposed algorithm for matrix functions is tested on hierarchical matrices and finally applied to the computation of exp(T)v for a Toeplitz matrix from a convection–diffusion problem. The results are compared with those obtained using Higham’s expmv routine.
In Chapter 5 we provide a brief review of our thesis and draw some conclusions about the work presented. Finally, we discuss several themes that deserve further investigations.