swMATH ID: 30518
Software Authors: Martinsson, P. G.; Quintana-Ortí, G.; Heavner, N.
Description: randUTV: a blocked randomized algorithm for computing a rank-revealing UTV factorization. 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.
Homepage: https://dl.acm.org/citation.cfm?doid=3314951.3242670
Source Code:  https://github.com/flame/randutv
Keywords: numerical linear algebra; high performance; randomized methods; rank-revealing matrix factorization; singular value decomposition
Related Software: rsvd; libflame; LAPACK; FLAME; RandNLA; UTV; Algorithm 1022; Algorithm 656; SuperMatrix; Algorithm 679; ScaLAPACK; TensorToolbox.jl; BSDS; tproduct; GitHub; Algorithm 971; LSRN; Blendenpik; RSVDPACK
Cited in: 6 Documents

Citations by Year