2018/11/20 by José‐Javier Martínez, Martinez, Jose-Javier
Computer Science · Mathematics · #15A23 #15B05 #15B48 #65F05 #65F15 #65F20 #65F35 #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Random Matrices and Applications #advanced mathematical theories
paper · pdf · doi:10.48550/arxiv.1811.08406
openalex publication_date 2018/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.