Speaker
Description
Appearing in a wide variety of applications, often in the context of discretized (fractional) differential and integral operators, Hierarchically Semiseparable (HSS) matrices have a number of attractive properties facilitating the development of fast algorithms [6,4].
For HSS matrices, the rank-structure is numerically preserved if $f(z)$ is well-approximated by a rational function. The underlying reason for this is that if $A$ is HSS, $A^{-1}$ shares the same structure [5]. Recently, Casulli, Kressner and Robol proposed an algorithm for computing matrix functions $f(A)$ where $A$ is HSS and symmetric [3]. This result is based on the equivalence between HSS structure and the existence of telescopic decompositions
$$A=A^{(L)}= D^{(L)}+U^{(L)}A^{(L-1)}{V^{(L)}}^T.$$
In our work we extend the procedure to general (non-symmetric) HSS matrices. The algorithm works recursively, viewing the telescopic decomposition as a sequence of low-rank updates to block-diagonal matrices $D^{(L-i)}$ for $i = 0,\dots,L$. At each step, after some careful permutation of the diagonal blocks, we employ Block Rational Krylov methods [1] to approximate the effect of the low-rank update while keeping the size of the matrices involved small.
Moreover, this technique allows the efficient computation of $f(T)$ where $T$ is a Toeplitz. Up to an FFT, the off-diagonal blocks of a Toeplitz matrix satisfy a displacement equation. The low-rank of the right-hand side is linked to fast singular value decay, which, in turn, implies that $\Omega T\Omega^*$ can be well-approximated by an HSS matrix [2].
[1] B. Beckermann et al., SIAM J. Numer. Anal., 59(3), 2021.
[2] B. Beckermann et al., Numerical Algorithms 100(4), 2025.
[3] A. A. Casulli et al., SIAM J. Matrix Anal. Appl., 45(4), 2024.
[4] S. Chandrasekaran et al., SIAM J. Matrix Anal. Appl., 27(02), 2005.
[5] A. Cortinovis et al., SIAM J. Matrix Anal. Appl., 43(1), 2022.
[6] W. Hackbusch, Hierarchical Matrices: Algorithms and Analysis, 49, 2015.