Computing the inertia of Bézout and Hankel matrices (Q1201962)

This paper is concerned with a sequential algorithm for computing the diagonal matrix \(D\) in the block \(LDL^ T\) factorization which evaluates the inertia of real Hankel and Bézout matrices \(A\) (i.e., the numbers of eigenvalues of \(A\) with positive, zero, and negative real parts). The algorithm is \(O(n\log^ 3n)\), better than any other known sequential algorithm for this problem. This improvement stems from relations between the polynomial remainder sequences generated by the Euclidean scheme when applied to two polynomials, and by Bézout and Hankel matrix computations developed by \textit{D. Bini}, the author, and \textit{V. Pan} [Improved parallel computations with matrices and polynomials; Proc. 18th EATCS International Colloquium on Automata, Languages and Programming, Lect. Notes Comput. Sci. 510 (Springer 1991)].