An $O(n\log^2n)$ Algorithm for Computing Hankel Determinants up to Order $n$
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_ | 1866916558958231552 |
|---|---|
| author | Liu, Feihu Xin, Guoce Zhang, Zihao |
| author_facet | Liu, Feihu Xin, Guoce Zhang, Zihao |
| contents | Given the rational power series $h(x) = \sum_{i \geq 0} h_i x^i \in \mathbb{C}[[x]]$, the Hankel determinant of order $n$ is defined as $H_n(h(x)) := \det (h_{i+j})_{0 \leq i,j \leq n-1}$. We explore the relationship between the Hankel continued fraction and the generalized Sturm sequence. This connection inspires the development of a novel algorithm for computing the Hankel determinants $\{H_i(h(x))\}_{i=0}^{n-1}$ using $O(n \log^2 n)$ arithmetic operations. We also explore the connection between the generalized Sturm sequences and the signature of Hankel matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05182 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An $O(n\log^2n)$ Algorithm for Computing Hankel Determinants up to Order $n$ Liu, Feihu Xin, Guoce Zhang, Zihao Combinatorics Given the rational power series $h(x) = \sum_{i \geq 0} h_i x^i \in \mathbb{C}[[x]]$, the Hankel determinant of order $n$ is defined as $H_n(h(x)) := \det (h_{i+j})_{0 \leq i,j \leq n-1}$. We explore the relationship between the Hankel continued fraction and the generalized Sturm sequence. This connection inspires the development of a novel algorithm for computing the Hankel determinants $\{H_i(h(x))\}_{i=0}^{n-1}$ using $O(n \log^2 n)$ arithmetic operations. We also explore the connection between the generalized Sturm sequences and the signature of Hankel matrices. |
| title | An $O(n\log^2n)$ Algorithm for Computing Hankel Determinants up to Order $n$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.05182 |