Fast linear algebra is stable (Q2461610): Difference between revisions

This is an important development of the work by \textit{J. Demmel}, \textit{I. Dumitriu}, \textit{O. Holtz} and \textit{R. Kleinberg} [Numer. Math. 106, No. 2, 199--224 (2007; Zbl 1134.65030)]. It is shown that essentially all standard linear algebra operations, including LU decomposition, QR decomposition, linear equation solving, matrix inversion, solving least squares problems, eigenvalue problems and the singular value decomposition can be done stably by fast algorithms. Briefly, the vein of this work is: By considering known divide-and-conquer algorithms the complexity of matrix inversion is reduced to the complexity of matrix multiplication. A divide-and-conquer algorithm for QR decomposition is analysed, and is in turn used to solve linear systems, least squares problems, and to compute determinants equally fast and stable. The same idea is applied to LU decomposition. The results on QR decomposition are then applied to analyse the RRURV decomposition of a matrix, to compute the Schur form and the singular value decomposition.