×
Heavner, N.; Igual, F. D.; Quintana-Ortí, G.; Martinsson, P. G.

Algorithm 1022: efficient algorithms for computing a rank-revealing UTV factorization on parallel computing architectures. (English) Zbl 07666978

ACM Trans. Math. Softw. 48, No. 2, Article No. 21, 42 p. (2022).

Cited in 1 Document

MSC:

65-XX Numerical analysis

Keywords:

numerical linear algebra; rank-revealing matrix factorization; singular value decomposition; high performance; randomized methods; block algorithm; algorithm-by-blocks; randomized SVD

Software:

BLAS; Algorithm 1022; Algorithm 679; POOCLAPACK; FLAME; SuperMatrix; ScaLAPACK; randUTV; Algorithm 656; libflame; LAPACK
Cite Review PDF
Full Text: DOI arXiv Link

References:

[1] Anderson, E., Bai, Z., Bischof, C., Blackford, L. S., Demmel, J., Dongarra, Jack J., Croz, J. Du, Hammarling, S., Greenbaum, A., McKenney, A., and Sorensen, D.. 1999. LAPACK Users’ Guide (3rd ed.). SIAM, Philadelphia, PA. · Zbl 0934.65030
[2] Anderson, Ed, Benzoni, A., Dongarra, J., Moulton, S., Ostrouchov, S., Tourancheau, Bernard, and Geijn, Robert van de. 1991. Basic linear algebra communication subprograms. In Proceedings of 6th Distributed Memory Computing Conference. IEEE, 287-290.
[3] Barlow, Jesse L.. 2002. Modification and maintenance of ULV decompositions. In Applied Mathematics and Scientific Computing. Springer, 31-62. · Zbl 1017.65036
[4] Benner, Peter, Quintana-Ortí, Enrique S., and Quintana-Ortí, Gregorio. 2008. Solving linear-quadratic optimal control problems on parallel computers. Optimization Methods and Software23, 6 (2008), 879-909. DOI: · Zbl 1154.65317
[5] Bientinesi, Paolo, Quintana-Ortí, Enrique S., and Geijn, Robert A.. 2005. Representing linear algebra algorithms in code: The FLAME application program interfaces. ACM Transactions on Mathematical Software31, 1 (2005), 27-59. · Zbl 1073.65037
[6] Blackford, L. Susan, Choi, Jaeyoung, Cleary, Andy, D’Azevedo, Eduardo, Demmel, James, Dhillon, Inderjit, Dongarra, Jack, Hammarling, Sven, Henry, Greg, Petitet, Antoine, et al. 1997. ScaLAPACK Users’ Guide. SIAM. · Zbl 0886.65022
[7] Chan, Ernie, Quintana-Orti, Enrique S., Quintana-Orti, Gregorio, and Geijn, Robert Van De. 2007. Supermatrix out-of-order scheduling of matrix operations for SMP and multi-core architectures. In Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures. ACM, 116-125.
[8] Chan, Ernie, Zee, Field G. Van, Bientinesi, Paolo, Quintana-Orti, Enrique S., Quintana-Orti, Gregorio, and Geijn, Robert van de. 2008. SuperMatrix: A multithreaded runtime scheduling system for algorithms-by-blocks. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’08). ACM, New York, NY, 123-132. DOI: · Zbl 1364.65105
[9] Choi, Jaeyoung, Demmel, James, Dhillon, Inderjiit, Dongarra, Jack, Ostrouchov, Susan, Petitet, Antoine, Stanley, Ken, Walker, David, and Whaley, R. Clinton. 1996. ScaLAPACK: A portable linear algebra library for distributed memory computers? Design issues and performance. Computer Physics Communications97, 1-2 (1996), 1-15. · Zbl 0926.65148
[10] Choi, Jaeyoung, Dongarra, Jack J., Ostrouchov, L. Susan, Petitet, Antoine P., Walker, David W., and Whaley, R. Clint. 1996. Design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines. Scientific Programming5, 3 (1996), 173-184.
[11] Choi, Jaeyoung, Dongarra, Jack J., Pozo, Roldan, and Walker, David W.. 1992. ScaLAPACK: A scalable linear algebra library for distributed memory concurrent computers. In 4th Symposium on the Frontiers of Massively Parallel Computation. IEEE, 120-127.
[12] Dongarra, Jack J., Cruz, Jermey Du, Hammarling, Sven, and Duff, Iain S.. 1990. Algorithm 679: A set of level 3 basic linear algebra subprograms: Model implementation and test programs. ACM Transactions on Mathematical Software16, 1 (1990), 18-28. · Zbl 0900.65116
[13] Dongarra, Jack J., Croz, Jeremy Du, Hammarling, Sven, and Hanson, Richard J.. 1988. Algorithm 656: An extended set of basic linear algebra subprograms: Model implementation and test programs. ACM Transactions on Mathematical Software14, 1 (1988), 18-32. · Zbl 0639.65017
[14] Eckart, Carl and Young, Gale. 1936. The approximation of one matrix by another of lower rank. Psychometrika1, 3 (1936), 211-218. · JFM 62.1075.02
[15] Erbay, Hasan, Barlow, Jesse L., and Zhang, Zhenyue. 2002. A modified Gram-Schmidt-based downdating technique for ULV decompositions with applications to recursive TLS problems. Computational Statistics & Data Analysis41, 1 (2002), 195-209. · Zbl 1018.65052
[16] Quintana, A. M. Vidal and G.. 1992. Parallel algorithms for QR factorization on shared memory multiprocessors. In Proceedings of the European Workshop on Parallel Computing’92, Parallel Computing: From Theory to Sound Practice, Joosen, E. Milgrom W. (Ed.). IOS Press, 72-75.
[17] Golub, Gene H. and Loan, Charles F. Van. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press, Baltimore, MD. · Zbl 0865.65009
[18] Gunnels, John A., Gustavson, Fred G., Henry, Greg M., and Geijn, Robert A. Van De. 2001. FLAME: Formal linear algebra methods environment. ACM Transactions on Mathematical Software27, 4 (2001), 422-455. · Zbl 1070.65522
[19] Gunter, Brian C. and Geijn, Robert A. Van De. 2005. Parallel out-of-core computation and updating of the QR factorization. ACM Transactions on Mathematical Software31, 1 (2005), 60-78. · Zbl 1073.65023
[20] Halko, Nathan, Martinsson, Per-Gunnar, and Tropp, Joel A.. 2011. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review53, 2 (2011), 217-288. · Zbl 1269.65043
[21] Igual, Francisco D., Chan, Ernie, Quintana-Ortí, Enrique S., Quintana-Ortí, Gregorio, Geijn, Robert A. Van De, and Zee, Field G. Van. 2012. The FLAME approach: From dense linear algebra algorithms to high-performance multi-accelerator implementations. Journal of Parallel and Distributed Computing72, 9 (2012), 1134-1143. · Zbl 1364.65105
[22] Quintana, A. M. Vidal, J. M. Badía, and G.. 1994. Efficient parallel QR decomposition on a network of transputers. In Proceedings of Transputers’94, Advanced Research and Industrial Applications. IOS Press, 247-265.
[23] Lawson, Chuck L., Hanson, Richard J., Kincaid, David R., and Krogh, Fred T.. 1979. Basic linear algebra subprograms for Fortran usage. ACM Transactions on Mathematical Software5, 3 (1979), 308-323. · Zbl 0412.65022
[24] Martinsson, P. G., Quintana-Ortí, G., and Heavner, N.. 2019. RandUTV: A blocked randomized algorithm for computing a rank-revealing UTV factorization. ACM Transactions on Mathematical Software45, 1, Article Article 4 (March2019), 26 pages. DOI: · Zbl 1471.65031
[25] Martinsson, Per-Gunnar, Rokhlin, Vladimir, and Tygert, Mark. 2006. A Randomized Algorithm for the Approximation of Matrices. Technical Report. Yale CS Research Report YALEU/DCS/RR-1361. Yale University, Computer Science Department, New Haven, CT. · Zbl 1111.65010
[26] Martinsson, Per-Gunnar, Rokhlin, Vladimir, and Tygert, Mark. 2011. A randomized algorithm for the decomposition of matrices. Applied and Computational Harmonic Analysis30, 1 (2011), 47-68. DOI: · Zbl 1210.65095
[27] Martinsson, Per-Gunnar and Tropp, Joel. 2020. Randomized numerical linear algebra: foundations & algorithms. (2020). . · Zbl 07674565
[28] Mirsky, Leon. 1960. Symmetric gauge functions and unitarily invariant norms. The Quarterly Journal of Mathematics11, 1 (1960), 50-59. · Zbl 0105.01101
[29] Park, Haesun and Eldén, Lars. 1995. Downdating the rank-revealing URV decomposition. SIAM SIAM Journal on Matrix Analysis and Applications16, 1 (1995), 138-155. · Zbl 0821.65025
[30] Quintana-Ortí, Gregorio, Igual, Francisco D., Marqués, Mercedes, Quintana-Ortí, Enrique S., and Geijn, Robert A. Van de. 2012. A runtime system for programming out-of-core matrix algorithms-by-tiles on multithreaded architectures. ACM Transactions on Mathematical Software38, 4 (2012), 25. · Zbl 1365.65114
[31] Quintana-Ortí, Gregorio, Quintana-Ortí, Enrique S., Geijn, Robert A. Van De, Zee, Field G. Van, and Chan, Ernie. 2009. Programming matrix algorithms-by-blocks for thread-level parallelism. Transactions on Mathematical Software36, 3, Article 14 (July2009), 26 pages. DOI: · Zbl 1364.65105
[32] Rokhlin, Vladimir, Szlam, Arthur, and Tygert, Mark. 2009. A randomized algorithm for principal component analysis. SIAM Journal on Matrix Analysis and Applications31, 3 (2009), 1100-1124. · Zbl 1198.65035
[33] Schreiber, Robert and Loan, Charles Van. 1989. A storage-efficient WY representation for products of Householder transformations. SIAM Journal on Scientific and Statistical Computing10, 1 (1989), 53-57. · Zbl 0664.65025
[34] Stewart, G. W.. 1998. Matrix Algorithms Volume 1: Basic Decompositions. SIAM, Philadelphia, PA. · Zbl 0910.65012
[35] Stewart, G. W.. 1992. An updating algorithm for subspace tracking. IEEE Transactions on Signal Processing40, 6 (Jun1992), 1535-1541. DOI:
[36] Stewart, Gilbert W.. 1993. Updating a rank-revealing ULV decomposition. SIAM Journal on Matrix Analysis and Applications14, 2 (1993), 494-499. · Zbl 0771.65021
[37] Trefethen, Lloyd N. and III, David Bau. 1997. Numerical Linear Algebra, Volume 50. SIAM, Philadelphia, PA. · Zbl 0874.65013
[38] Zee, Field G. Van. 2012. libflame: The Complete Reference. www.lulu.com. Retrieved April 6, 2022 from http://www.cs.utexas.edu/users/flame/web/FLAMEPublications.html.
[39] Zee, Field G. Van, Chan, Ernie, Geijn, Robert van de, Quintana-Ortí, Enrique S., and Quintana-Ortí, Gregorio. 2009. The libflame library for dense matrix computations. IEEE Computation in Science & Engineering11, 6 (2009), 56-62. · Zbl 1364.65105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.