- Main
Fast linear algebra is stable
Published Web Location
http://www.springerlink.com/content/63755500n1481543/Abstract
In Demmel et al. (Numer. Math. 106(2), 199-224, 2007) we showed that a large class of fast recursive matrix multiplication algorithms is stable in a normwise sense, and that in fact if multiplication of n-by-n matrices can be done by any algorithm in O(n(omega+eta)) operations for any eta > 0, then it can be done stably in O(n(omega+eta)) operations for any eta > 0. Here we extend this result to show that essentially all standard linear algebra operations, including LU decomposition, QR decomposition, linear equation solving, matrix inversion, solving least squares problems, (generalized) eigenvalue problems and the singular value decomposition can also be done stably (in a normwise sense) in O(n(omega+eta)) operations.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:
-
-
-
-
-
-
-
-
-
-
-
-
-
-