Fast measure modification of orthogonal polynomials via matrices with displacement structure
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909439270846464 |
|---|---|
| author | Gumerov, Karim Rigg, Samantha Slevinsky, Richard Mikael |
| author_facet | Gumerov, Karim Rigg, Samantha Slevinsky, Richard Mikael |
| contents | It is well known that matrices with low Hessenberg-structured displacement rank enjoy fast algorithms for certain matrix factorizations. We show how $n\times n$ principal finite sections of the Gram matrix for the orthogonal polynomial measure modification problem has such a displacement structure, unlocking a collection of fast algorithms for computing connection coefficients (as the upper-triangular Cholesky factor) between a known orthogonal polynomial family and the modified family. In general, the ${\cal O}(n^3)$ complexity is reduced to ${\cal O}(n^2)$, and if the symmetric Gram matrix has upper and lower bandwidth b, then the ${\cal O}(b^2n)$ complexity for a banded Cholesky factorization is reduced to ${\cal O}(b n)$. In the case of modified Chebyshev polynomials, we show that the Gram matrix is a symmetric Toeplitz-plus-Hankel matrix, and if the modified Chebyshev moments decay algebraically, then a hierarchical off-diagonal low-rank structure is observed in the Gram matrix, enabling a further reduction in the complexity of an approximate Cholesky factorization powered by randomized numerical linear algebra. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17663 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast measure modification of orthogonal polynomials via matrices with displacement structure Gumerov, Karim Rigg, Samantha Slevinsky, Richard Mikael Numerical Analysis 33C45, 33C47, 65F45, 15A24, 68W20 It is well known that matrices with low Hessenberg-structured displacement rank enjoy fast algorithms for certain matrix factorizations. We show how $n\times n$ principal finite sections of the Gram matrix for the orthogonal polynomial measure modification problem has such a displacement structure, unlocking a collection of fast algorithms for computing connection coefficients (as the upper-triangular Cholesky factor) between a known orthogonal polynomial family and the modified family. In general, the ${\cal O}(n^3)$ complexity is reduced to ${\cal O}(n^2)$, and if the symmetric Gram matrix has upper and lower bandwidth b, then the ${\cal O}(b^2n)$ complexity for a banded Cholesky factorization is reduced to ${\cal O}(b n)$. In the case of modified Chebyshev polynomials, we show that the Gram matrix is a symmetric Toeplitz-plus-Hankel matrix, and if the modified Chebyshev moments decay algebraically, then a hierarchical off-diagonal low-rank structure is observed in the Gram matrix, enabling a further reduction in the complexity of an approximate Cholesky factorization powered by randomized numerical linear algebra. |
| title | Fast measure modification of orthogonal polynomials via matrices with displacement structure |
| topic | Numerical Analysis 33C45, 33C47, 65F45, 15A24, 68W20 |
| url | https://arxiv.org/abs/2412.17663 |