Accurate Inverses through Accurate Minors for Structured Matrices
James Demmel, Plamen Koev
Abstract: The following necessary and sufficient conditions for computing inverses and SVDs to high relative accuracy ("accurately") are due to Demmel:
1. Being able to compute |det(A)| is a necessary condition for computing an accurate SVD. 2. Being able to compute n^2+1 minors accurately is sufficient for computing an accurate inverse (Cramer's rule). 3. Being able to compute O(n^3) minors accurately is sufficient for an accurate SVD (Demmel 1997).
In this talk we bridge the gap between necessary and sufficient conditions for computing accurate inverses in O(n^3) time for some classes of structured matrices, such as Cauchy, Vandermonde and certain Generalized Vandermonde matrices.
By computing accurate minors and using the Cramer's rule we are able to obtain algorithms that match the speed (in big-O sense) of the current benchmark Bjorck-Pereyra-type algorithms for accurate inversion of Vandermonde and Cauchy matrices.
Using similar methods (accurate minors and the Cramer's rule) we were able to obtain new results, namely an algorithm for accurate inversion of some Generalized Vandermonde matrices (generalized in a sense that the exponents are increasing integers but are not necessarily 0, 1, 2,..., n-1) in O(n^3) time.
Some of this work extends to the computation of accurate SVDs.