Randomized LU decomposition

DOI10.1016/j.acha.2016.04.006zbMath1380.65077arXiv1310.7202OpenAlexW2963718636WikidataQ56600873 ScholiaQ56600873MaRDI QIDQ1690696

Yaniv Shmueli, Yariv Aizenbud, Gil Shabat, Amir Z. Averbuch

Publication date: 12 January 2018

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.7202

zbMATH Keywords

numerical examplesingular value decompositionrandom matriceserror boundrandomized algorithmsmatrix factorizationsLU decomposition

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Random matrices (algebraic aspects) (15B52) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (13)

Randomized quaternion QLP decomposition for low-rank approximation ⋮ Randomized generalized singular value decomposition ⋮ Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions ⋮ Pass-efficient randomized LU algorithms for computing low-rank matrix approximation ⋮ The \(\mathcal{L_C}\)-structure-preserving algorithms of quaternion \(LDL^H\) decomposition and Cholesky decomposition ⋮ An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation ⋮ Pass-efficient truncated UTV for low-rank approximations ⋮ The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection ⋮ A randomized singular value decomposition for third-order oriented tensors ⋮ Randomized algorithms for the low multilinear rank approximations of tensors ⋮ Single-pass randomized algorithms for LU decomposition ⋮ Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning ⋮ Single-pass randomized QLP decomposition for low-rank approximation

Uses Software

• SuperLU
• CUDA
• PROPACK
• Blendenpik
• softImpute

Cites Work

• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Rang revealing QR factorizations
• A randomized algorithm for the decomposition of matrices
• A fast randomized algorithm for the approximation of matrices
• Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors
• On the existence and computation of rank-revealing LU factorizations
• Multiscale data sampling and function extension
• Strong rank revealing LU factorizations
• Smallest singular value of random matrices and geometry of random polytopes
• Diffusion maps
• Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
• A fast randomized algorithm for overdetermined linear least-squares regression
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• An Unsymmetric-Pattern Multifrontal Method for Sparse LU Factorization
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Low-Rank Approximation and Regression in Input Sparsity Time
• Average-Case Stability of Gaussian Elimination
• Fast computation of low-rank matrix approximations
• Relative-Error $CUR$ Matrix Decompositions
• Smallest singular value of a random rectangular matrix
• A Supernodal Approach to Sparse Partial Pivoting
• 10.1162/1532443041827934
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Smallest singular value of sparse random matrices
• Numerical linear algebra in the streaming model
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• On the Compression of Low Rank Matrices
• Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication
• Fast monte-carlo algorithms for finding low-rank approximations
• Condition Numbers of Gaussian Random Matrices
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Numerical Inverting of Matrices of High Order. II
• Compressed sensing

This page was built for publication: Randomized LU decomposition