The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Communication-optimal Parallel and Sequential QR and LU Factorizations
Open accessAbstract
We present parallel and sequential dense QR factorization algorithms that are both optimal (up to polylogarithmic factors) in the amount of communication they perform and just as stable as Householder QR. We prove optimality by deriving new lower bounds for the number of multiplications done by “non-Strassen-like” QR, and using these in known communication lower bounds that are proportional to the number of multiplications. We not only show that our QR algorithms attain these lower bounds (up to polylogarithmic factors), but that existing LAPACK and ScaLAPACK algorithms perform asymptotically more communication. We derive analogous communication lower bounds for LU factorization and point out recent LU algorithms in the literature that attain at least some of these lower bounds. The sequential and parallel QR algorithms for tall and skinny matrices lead to significant speedups in practice over some of the existing algorithms, including LAPACK and ScaLAPACK, for example, up to 6.7 times over ScaLAPACK. A performance model for the parallel algorithm for general rectangular matrices predicts significant speedups over ScaLAPACK.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Anderson, E., Bai, Z., Bischof, C., Blackford, L. S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., et al. (1999) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719604 · Cited by 4,435
Self-citationThe Symmetric Eigenvalue Problem
Parlett, B. N. (1998) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971163 · Cited by 3,192
Using MPI: Portable parallel programming with the message-passing interface
(1995) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(95)90199-x · Cited by 2,854
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509
Sagan, H. (1994) · Universitext · doi:10.1007/978-1-4612-0871-6 · Cited by 1,336
Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide
Demmel, J. W., Dongarra, J. J., Ruhe, A., van der Vorst, H. A., & Bai, Z. (1987) · Medical Entomology and Zoology · Cited by 1,102
Self-citationA class of parallel tiled linear algebra algorithms for multicore architectures
Buttari, A., Langou, J., Kurzak, J., & Dongarra, J. (2009) · Parallel Computing · doi:10.1016/j.parco.2008.10.002 · Cited by 529
Self-citationI/O complexity: The red-blue pebble game
Hong, J., & Kung, H. T. (1981) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800076.802486 · Cited by 474
Solving linear least squares problems by Gram-Schmidt orthogonalization
Björck, Å. (1967) · BIT · doi:10.1007/bf01934122 · Cited by 470
Gaussian Elimination is not Optimal
Trassen, V. (2005) · Cited by 454
Fast Parallel Matrix Inversion Algorithms
Csanky, L. (1976) · SIAM Journal on Computing · doi:10.1137/0205040 · Cited by 397
A Storage-Efficient $WY$ Representation for Products of Householder Transformations
Schreiber, R., & Van Loan, C. (1989) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0910005 · Cited by 313
Minimizing Communication in Numerical Linear Algebra
Ballard, G., Demmel, J., Holtz, O., & Schwartz, O. (2011) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090769156 · Cited by 276
Self-citationCommunication lower bounds for distributed-memory matrix multiplication
Irony, D., Toledo, S., & Tiskin, A. (2004) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2004.03.021 · Cited by 250
Design and Implementation of the ScaLAPACK LU, QR, and Cholesky Factorization Routines
Choi, J., Dongarra, J. J., Ostrouchov, L. S., Petitet, A. P., Walker, D. W., & Whaley, R. C. (1996) · Scientific Programming · doi:10.1155/1996/483083 · Cited by 220
On the Asymptotic Complexity of Matrix Multiplication
Coppersmith, D., & Winograd, S. (1982) · SIAM Journal on Computing · doi:10.1137/0211038 · Cited by 209
Parallel tiled QR factorization for multicore architectures
Buttari, A., Julien Langou, F., Jakub Kurzak, A., & Dongarra, J. J. (2008) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.1301 · Cited by 178
Locality of Reference in LU Decomposition with Partial Pivoting
Toledo, S. (1997) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479896297744 · Cited by 163
Recursive Blocked Algorithms and Hybrid Data Structures for Dense Matrix Library Software
Elmroth, E., Gustavson, F., Jonsson, I., & Kågström, B. (2004) · SIAM Review · doi:10.1137/s0036144503428693 · Cited by 161
Demmel, J. W., Dumitriu, I., & Holtz, O. (2007) · Cited by 143
Self-citationMinimizing communication in sparse matrix solvers
Mohiyuddin, M., Hoemmen, M. F., Demmel, J. W., & Yelick, K. (2009) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/1654059.1654096 · Cited by 140
Self-citationGetting Up to Speed: The Future of Supercomputing
Graham, S. L., Patterson, C. A., & Snir, M. (2013) · Cited by 136
Applying recursion to serial and parallel QR factorization leads to better performance
Elmroth, E., & Gustavson, F. G. (2000) · IBM Journal of Research and Development · doi:10.1147/rd.444.0605 · Cited by 114
Parallel out-of-core computation and updating of the QR factorization
Gunter, B. C., & Geijn, R. A. (2005) · ACM Transactions on Mathematical Software · doi:10.1145/1055531.1055534 · Cited by 99
CALU: A Communication Optimal LU Factorization Algorithm
Grigori, L., Demmel, J. W., & Xiang, H. (2011) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/100788926 · Cited by 89
Self-citationOn the Complexity of Matrix Product
Raz, R. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702402147 · Cited by 84
Round off error analysis for Gram-Schmidt method and solution of linear least squares problems
Abdelmalek, N. N. (1971) · BIT Numerical Mathematics · doi:10.1007/bf01939404 · Cited by 59
Distributed Orthogonal Factorization: Givens and Householder Algorithms
Pothen, A., & Raghavan, P. (1989) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0910067 · Cited by 55
New serial and parallel recursive QR factorization algorithms for SMP systems
Elmroth, E., & Gustavson, F. G. (1998) · Lecture notes in computer science · doi:10.1007/bfb0095328 · Cited by 50
Scheduling of QR Factorization Algorithms on SMP and Multi-Core Architectures
Quintana‐Ortí, G., Quintana–Ort́ı, E. S., Chan, E., Geijn, R. A., & Zee, F. G. (2008) · Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) · doi:10.1109/pdp.2008.37 · Cited by 49
Some issues in dense linear algebra for multicore and special purpose architecturesPreprint
Baboulin, M., Dongarra, J. J., & Tomov, S. Z. (2008) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · Cited by 45
QR factorization with Morton-ordered quadtree matrices for memory re-use and parallelism
Frens, J. D., & Wise, D. S. (2003) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/781498.781525 · Cited by 36
Performance without pain = productivity: data layout and collective communication in UPC
Nishtala, R., Almasi, G. S., & Caşcaval, C. (2008) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/1345206.1345224 · Cited by 36
Out-of-Core SVD and QR Decompositions.
Rabani, E., & Toledo, S. (2001) · Cited by 30
Cited by
Speeding Up Distributed Machine Learning Using Codes
Lee, K., Lam, M., Pedarsani, R., Papailiopoulos, D., & Ramchandran, K. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2736066 · Cited by 829
Dynamic Mode Decomposition and Its Variants
Schmid, P. J. (2022) · Annual Review of Fluid Mechanics · doi:10.1146/annurev-fluid-030121-015835 · Cited by 640
Communication-Efficient Distributed Statistical Inference
Jordan, M. I., Lee, J. D., & Yang, Y. (2019) · Journal of the American Statistical Association · doi:10.1080/01621459.2018.1429274 · Cited by 442
Randomized numerical linear algebra: Foundations and algorithms
Martinsson, P.-G., & Tropp, J. A. (2020) · Acta Numerica · doi:10.1017/s0962492920000021 · Cited by 300
Minimizing Communication in Numerical Linear Algebra
Ballard, G., Demmel, J., Holtz, O., & Schwartz, O. (2011) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090769156 · Cited by 276
Self-citation
Metadata
- Authors
- Demmel, J., Grigori, L., Hoemmen, M., & Langou, J.
- Venue
- SIAM Journal on Scientific Computing
- Published
- 2012-01
- Volume
- 34
- Issue
- 1
- Pages
- A206-A239
- ISSN
- 1064-8275 (ISSN-L)
- 1095-7197
- OpenAlex
- W2157237396
- Cited by
- 407
- References
- 35
- FWCI
- 31.90
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.