C. Brunie & P. Saux-Picart


Titre: "Fast algorithms on Hermitian Toeplitz matices."


Résumé: In this article we explore new fast ways to inverse a Hermitian \textsc{Toeplitz} matrix and compute its signature. It is well-known that to every complex polynomial $P$, we can associate via Bezoutian, an Hermitian matrix ${\mathbf{K}}(P)$ whose signature computes the number of roots of the polynomial $P$ in the unit disk (the so-called \textsc{Schur-Cohn algorithm}) ; this matrix is equivalent to a Hermitian \textsc{Toeplitz} one. We prove that the converse is also true : to every Hermitian \textsc{Toepliz} matrix $\mathbf{T}$, we can associate a polynomial $P$ such that ${\mathbf{K}}(P)$ and $\mathbf{T}$ are equivalent. We then use the fast version of the \textsc{Schur-Cohn} algorithm we devised in previous articles, to obtain, via the FFT, algorithms solving the linear system $\mathbf{T}X=b$ and computing the signature of ${\mathbf{T}}$ in a complexity of ${\mathcal{O}}(d \log^2 d)$ operations in $\C$ ($d$ denotes the dimension of ${\mathbf{T}}$). These algorithms, except for the very last step, use exact divisions and are well adapted to computer algebra.

---

Sommaire