The aim of this work is to develop a fast algorithm for approximating the matrix function f(A) of a square matrix A that is symmetric and has hierarchically semiseparable (HSS) structure. Appearing in a wide variety of applications, often in the context of discretized (fractional) differential and integral operators, HSS matrices have a number of attractive properties facilitating the development of fast algorithms. In this work, we use an unconventional telescopic decomposition of A, inspired by recent work of Levitt and Martinsson on approximating an HSS matrix from matrixvector products with a few random vectors. This telescopic decomposition allows us to approximate f(A) by recursively performing low-rank updates with rational Krylov subspaces while keeping the size of the matrices involved in the rational Krylov subspaces small. In particular, no large-scale linear system needs to be solved, which yields favorable complexity estimates and reduced execution times compared to existing methods, including an existing divide-and-conquer strategy. The advantages of our newly proposed algorithms are demonstrated for a number of examples from the literature, featuring the exponential, the inverse square root, and the sign function of a matrix. For the special case of matrix inversion, our algorithm reduces to a procedure previously proposed by Gillman, Young, and Martinsson [Front. Math. China, 7 (2012), pp. 217-247].

Computing Functions of Symmetric Hierarchically Semiseparable Matrices

Casulli, Angelo A.
;
Robol, Leonardo
2024-01-01

Abstract

The aim of this work is to develop a fast algorithm for approximating the matrix function f(A) of a square matrix A that is symmetric and has hierarchically semiseparable (HSS) structure. Appearing in a wide variety of applications, often in the context of discretized (fractional) differential and integral operators, HSS matrices have a number of attractive properties facilitating the development of fast algorithms. In this work, we use an unconventional telescopic decomposition of A, inspired by recent work of Levitt and Martinsson on approximating an HSS matrix from matrixvector products with a few random vectors. This telescopic decomposition allows us to approximate f(A) by recursively performing low-rank updates with rational Krylov subspaces while keeping the size of the matrices involved in the rational Krylov subspaces small. In particular, no large-scale linear system needs to be solved, which yields favorable complexity estimates and reduced execution times compared to existing methods, including an existing divide-and-conquer strategy. The advantages of our newly proposed algorithms are demonstrated for a number of examples from the literature, featuring the exponential, the inverse square root, and the sign function of a matrix. For the special case of matrix inversion, our algorithm reduces to a procedure previously proposed by Gillman, Young, and Martinsson [Front. Math. China, 7 (2012), pp. 217-247].
2024
Casulli, Angelo A.; Kressner, Daniel; Robol, Leonardo
File in questo prodotto:
File Dimensione Formato  
24m1642354.pdf

non disponibili

Descrizione: Versione finale editoriale
Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - accesso privato/ristretto
Dimensione 1.22 MB
Formato Adobe PDF
1.22 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
HSS_matfun.pdf

accesso aperto

Descrizione: post-print
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 464.64 kB
Formato Adobe PDF
464.64 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1293575
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact