Remarks on complexity of polynomial and special matrix computations (Q1824347)

The asymptotic order of complexity of the problems of polynomial and rational interpolation, polynomial evaluation and inversion of Löwner and Toeplitz or Hankel matrices is studied. The main result is that the solution of a Löwner matrix has not a larger order than the combination of rational interpolation and polynomial evaluation. There are other inequalities. The author emphasizes that there remains the open problem whether the whole group of the problems has the same order of complexity or not.