The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System

Abstract

Vandermonde, Cauchy, and Cauchy--Vandermonde totally positive linear systems can be solved extremely accurately in O(n2 time using Björck--Pereyra-type methods. We prove that Björck--Pereyra-type methods exist not only for the above linear systems but also for any totally positive linear system as long as the initial minors (i.e., contiguous minors that include the first row or column) can be computed accurately. Using this result we design a new O(n2 Björck--Pereyra-type method for solving generalized Vandermonde systems of equations by using a new algorithm for computing the Schur function. We present explicit formulas for the entries of the bidiagonal decomposition, the LDU decomposition, and the inverse of a totally positive generalized Vandermonde matrix, as well as algorithms for computing these entries to high relative accuracy.