Simple, Fast and Practicable Algorithms for Cholesky, LU and QR Decomposition Using Fast Rectangular Matrix Multiplication

2018/12/05 by Cristóbal Camarero, Camarero, Cristóbal
Computer Science · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1812.02056

openalex publication_date 2018/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This note presents fast Cholesky/LU/QR decomposition algorithms with O(n^2.529) time complexity when using the fastest known matrix multiplication. The algorithms have potential application, since a quickly made implementation using Strassen multiplication has lesser execution time than the employed by the GNU Scientific Library for the same task in at least a few examples. The underlaying ideas are very simple. Despite this, I have been unable to find these methods in the literature.

Related

• Differentiation of the Cholesky decomposition
• Communication-avoiding Cholesky-QR2 for rectangular matrices
• Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices
• CholeskyQR with Randomization and Pivoting for Tall Matrices (CQRRPT)
• A block Cholesky-LU-based QR factorization for rectangular matrices