Fast algorithms of Björck-Pereyra type for solving Cauchy-Vandermonde linear systems (Q1382293)

Vandermonde matrices arise most naturally when a given function is approximated by a polynomial using collocation in a number of points. Similarly, Cauchy matrices arise when the approximation is by linear combinations of functions of the form \({1\over x- d_j}\), where the numbers \(d_j\) are poles that are known a priori. So Cauchy-Vandermonde matrices arise when both function types are combined; they have the form \(V= (A| B)\), where the first \(l\) columns form a Cauchy matrix and the last \(n- l\) columns form a Vandermonde matrix. The interpolation problem requires the solution of problems of the form \(Va= b\) while the construction of formulae for numerical integration or differentiation of interpolatory type requires the solution of \(V^Ta= b\). The authors present fast algorithms for both tasks; ``fast'' means \(O(n^2)\) instead of the \(O(n^3)\) that is typical for dense systems. These methods generalize the methods for Vandermonde matrices referred to in the title of the paper. The authors further analyze the total positivity of Cauchy-Vandermonde matrices and discuss the importance of this issue for Computer Aided Geometric Design (shape preserving representation). This paper is nicely written and very readable; it also contains a good bibliography of relevant earlier work.