Compression Properties for large Toeplitz-like matrices
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911022405648384 |
|---|---|
| author | Beckermann, Bernhard Kressner, Daniel Wilber, Heather |
| author_facet | Beckermann, Bernhard Kressner, Daniel Wilber, Heather |
| contents | Toeplitz matrices are abundant in computational mathematics, and there is a rich literature on the development of fast and superfast algorithms for solving linear systems involving such matrices. Any Toeplitz matrix can be transformed into a matrix with off-diagonal blocks that are of low numerical rank.This compressibility is relied upon in practice in a number of superfast Toeplitz solvers. In this paper, we show that the compression properties of these matrices can be thoroughly explained using their displacement structure. We provide explicit bounds on the numerical ranks of important submatrices that arise when applying HSS, HODLR and other approximations with hierarchical low-rank structure to transformed Toeplitz and Toeplitz-like matrices. Our results lead to very efficient displacement-based compression strategies that can be used to formulate adaptive superfast rank-structured solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09823 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Compression Properties for large Toeplitz-like matrices Beckermann, Bernhard Kressner, Daniel Wilber, Heather Numerical Analysis 15B05, 15A18, 15A23, 15A06, 65F05, 41A20 Toeplitz matrices are abundant in computational mathematics, and there is a rich literature on the development of fast and superfast algorithms for solving linear systems involving such matrices. Any Toeplitz matrix can be transformed into a matrix with off-diagonal blocks that are of low numerical rank.This compressibility is relied upon in practice in a number of superfast Toeplitz solvers. In this paper, we show that the compression properties of these matrices can be thoroughly explained using their displacement structure. We provide explicit bounds on the numerical ranks of important submatrices that arise when applying HSS, HODLR and other approximations with hierarchical low-rank structure to transformed Toeplitz and Toeplitz-like matrices. Our results lead to very efficient displacement-based compression strategies that can be used to formulate adaptive superfast rank-structured solvers. |
| title | Compression Properties for large Toeplitz-like matrices |
| topic | Numerical Analysis 15B05, 15A18, 15A23, 15A06, 65F05, 41A20 |
| url | https://arxiv.org/abs/2502.09823 |