Details

Autor(en) / Beteiligte

• Martinsson, P. G.
• Quintana-Ortí, G.
• Heavner, N.

Titel

randUTV: A Blocked Randomized Algorithm for Computing a Rank-Revealing UTV Factorization

Ist Teil von

• ACM transactions on mathematical software, 2019-03, Vol.45 (1), p.1-26

Erscheinungsjahr

2019

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• A randomized algorithm for computing a so-called UTV factorization efficiently is presented. Given a matrix A , the algorithm “randUTV” computes a factorization A = UTV * , where U and V have orthonormal columns, and T is triangular (either upper or lower, whichever is preferred). The algorithm randUTV is developed primarily to be a fast and easily parallelized alternative to algorithms for computing the Singular Value Decomposition (SVD). randUTV provides accuracy very close to that of the SVD for problems such as low-rank approximation, solving ill-conditioned linear systems, and determining bases for various subspaces associated with the matrix. Moreover, randUTV produces highly accurate approximations to the singular values of A . Unlike the SVD, the randomized algorithm proposed builds a UTV factorization in an incremental, single-stage, and noniterative way, making it possible to halt the factorization process once a specified tolerance has been met. Numerical experiments comparing the accuracy and speed of randUTV to the SVD are presented. Other experiments also demonstrate that in comparison to column-pivoted QR, which is another factorization that is often used as a relatively economic alternative to the SVD, randUTV compares favorably in terms of speed while providing far higher accuracy.