Bjorck-Pereyra-type methods and total positivity
For researchers in numerical linear algebra, this provides accurate algorithms for structured matrices, though it is an incremental extension of known methods.
This work extends Bjorck-Pereyra-type methods to solve linear systems and other linear algebra problems (eigenvalue, singular value, least squares) with totally positive structured matrices, achieving high relative accuracy. Numerical experiments demonstrate superior performance over structure-ignoring algorithms.
The approach to solving linear systems with structured matrices by means of the bidiagonal factorization of the inverse of the coefficient matrix is first considered, the starting point being the classical Bjorck-Pereyra algorithms for Vandermonde systems, published in 1970 and carefully analyzed by Higham in 1987. The work of Higham showed the crucial role of total positivity for obtaining accurate results, which led to the generalization of this approach to totally positive Cauchy, Cauchy-Vandermonde and generalized Vandermonde matrices. Then, the solution of other linear algebra problems (eigenvalue and singular value computation, least squares problems) is addressed, a fundamental tool being the bidiagonal decomposition of the corresponding matrices. This bidiagonal decomposition is related to the theory of Neville elimination, although for achieving high relative accuracy the algorithm of Neville elimination is not used. Numerical experiments showing the good behaviour of these algorithms when compared with algorithms which ignore the matrix structure are also included.