Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
randUTV: a blocked randomized algorithm for computing a rank-revealing UTV factorization
Martinsson P., Quintana-Ortí G., Heavner N. ACM Transactions on Mathematical Software45 (1):1-26,2019.Type:Article
Date Reviewed: Jul 12 2021

Matrix singular value decomposition (SVD) has broad applications in both computational linear algebra and data analysis. Robust SVD algorithms and sophisticated software implementations have been available in the literature for decades. However, efficiently calculating SVD for large-sized matrices through parallel processing remains a challenge due to computational dependency. Nevertheless, with the rise of big data, professionals and practitioners often need to process datasets with millions of rows and columns in real-world applications. There is a strong demand for alternative algorithms that are able to efficiently find numerical solutions with high accuracy for SVD applications of large matrices.

To meet the needs, the authors of this work propose a randomized matrix for computing UTV factorization (randUTV) as an alternative to SVD. That is to factor a matrix A as A = UTV* instead of A = UΣ V*, “where U and V have orthonormal columns, T is triangular,” and Σ consists of singular values as a diagonal matrix. The randUTV algorithm “builds a UTV factorization in an incremental ... and noniterative way.” With a specified tolerance, the factorization process is able to execute concurrently. Computational experiments show that the randUTV algorithm can improve computational efficiency when compared with other known alternatives. Much more significantly, the randUTV alternative is able to produce far more accurate numerical solutions, that is, very close to that of SVD. This work compares the accuracy of randUTV with another economic alternative: column-pivoted QR. The authors clearly explain the improvement in efficiency. However, they do not provide theoretical justifications for the high accuracy in terms of closeness to singular values.

I strongly recommend this paper to professionals and practitioners, especially those who deal with large-sized matrices in computational linear algebra and data science. Although the paper does not provide a rigorous proof to justify the achieved high accuracy mathematically, likely due to the randomness, the presented computational results demonstrate the usefulness of randUTV, which is an effective alternative to SVD with very high accuracy and efficiency.

Reviewer:  Chenyi Hu Review #: CR147305 (2109-0242)
Bookmark and Share
  Featured Reviewer  
 
General (G.0 )
 
 
Mathematical Software (G.4 )
 
 
Numerical Analysis (G.1 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date

Type: Journal
Feb 1 1986
Science, computers, and people: from the tree of mathematics
Ulam S., Birkhäuser Boston Inc., Cambridge, MA, 1986. Type: Book (9789780817632762)
May 1 1988
Computer science: a mathematical introduction
Lew A., Prentice-Hall, Inc., Upper Saddle River, NJ, 1985. Type: Book (9789780131642522)
Jul 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy