Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
From MaRDI portal
Publication:2350005
DOI10.1016/j.laa.2015.04.021zbMath1317.65080arXiv1406.5802OpenAlexW1557763977WikidataQ113869483 ScholiaQ113869483MaRDI QIDQ2350005
Guoliang Qian, Xiaodong Yan, Pan, Victor Y.
Publication date: 18 June 2015
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.5802
random matricesGaussian eliminationpivotinglow-rank approximationblock Gaussian eliminationrandom multipliersrandom circulant matricesSRFT matricesToeplitz multiplier
Random matrices (algebraic aspects) (15B52) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
Numerically safe Gaussian elimination with no pivoting, New studies of randomized augmentation and additive preprocessing, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, Low-Rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions, How Bad Are Vandermonde Matrices?, Sublinear Cost Low Rank Approximation via Subspace Sampling, CUR LRA at Sublinear Cost Based on Volume Maximization, Fast approximate computations with Cauchy matrices and polynomials, Real polynomial root-finding by means of matrix and polynomial iterations
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- Solving linear systems of equations with randomization, augmentation and aggregation
- Matrix computations and polynomial root-finding with preprocessing
- Additive preconditioning for matrix computations
- Randomized preprocessing of homogeneous linear systems of equations
- Condition numbers of random matrices
- A probabilistic remark on algebraic program testing
- On perturbation bounds for the QR factorization
- On the existence and computation of rank-revealing LU factorizations
- Preconditioning techniques for large linear systems: A survey
- Randomized preprocessing versus pivoting
- Generalized inverses of certain Toeplitz matrices
- Schur aggregation for linear systems and determinants
- Estimating the norms of random circulant and Toeplitz matrices and their inverses
- How Bad Are Vandermonde Matrices?
- IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Stability of Methods for Solving Toeplitz Systems of Equations
- The Probability That a Numerical Analysis Problem is Difficult
- Eigenvalues and Condition Numbers of Random Matrices
- Iterative Refinement Implies Numerical Stability for Gaussian Elimination
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- Iterative Solution Methods
- Stable and Efficient Algorithms for Structured Systems of Linear Equations
- Communication lower bounds and optimal algorithms for numerical linear algebra
- Accuracy and Stability of Numerical Algorithms
- Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Randomized preconditioning of the MBA algorithm
- Tails of Condition Number Distributions
- Condition Numbers of Gaussian Random Matrices
