Algorithms for solving rational interpolation problems related to fast and superfast solvers for Toeplitz systems

Linearized rational interpolation problems at roots of unity play a crucial role in the fast and superfast Toeplitz solvers that we have developed. Our interpolation algorithm is a sequential algorithm in which a matrix polynomial that satisfies already some of the interpolation conditions is updated to satisfy two additional interpolation conditions. In the algorithm that we have used so far, the updating matrix, which is a matrix polynomial of degree one, is constructed in a two-step process that resembles Gaussian elimination. We briefly recall this approach and then consider two other approaches. The first one is a completely new approach based on an updating matrix that is unitary with respect to a discrete inner product that is based on roots of unity. The second one is an application of an algorithm for solving discrete least squares problems on the unit circle, a problem that has linearized rational interpolation at roots of unity as its limiting case. We conduct a number of numerical experiments to compare the three strategies.