An $O(n{\log }^{2}n)$ Algorithm for Computing Hankel Determinants up to Order $n$

Abstract

Given the rational power series $h(x)={\sum }_{i\ge 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}{)}_{1\le i,j\le n}$. 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.

11 pages, comments are welcome