Effective computations with dense structured matrices and applications to polynomial evaluation and interpolation

In recent years the research has demonstrated the power of combining the technique of algebraic and numerical computing. In the past, numerical algorithms for matrix computations and algebraic algorithms for polynomial computations were developed and implemented independently of each other with very little interaction.; In this study, we attempt to take some topics from both areas and show various correlations between them, in particular, via the study of computations with dense structured matrices (e.g. Toeplitz, Hankel, Vandermonde and Cauchy matrices) and of their applications to computations with both polynomial and general matrices. The main objective is to find a numerically stable as well as arithmetically fast algorithms for some selected fundamental problems of algebraic and numerical computations.; The computational cost is very high if n is large in many applications of n x n matrices. Hence it becomes important to develope algorithms that will reduce the burden on the computational resources of time and space. Since the applied problems often impose some structure on the matrices, the structure can be used to reduce the complexity bound for some major computations with structured matrices dramatically. This is usually achieved by means of direct methods, based on matrix factorizations, but there are also some alternative iterative methods. Here we use two different iterative methods to accomplish our goal.