Skip to main content
eScholarship
Open Access Publications from the University of California

Fast linear algebra is stable

  • Author(s): Demmel, James
  • Holtz, Olga
  • Dumitriu, Ioana
  • et al.
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 Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View