Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
From MaRDI portal
Publication:4891737
DOI10.1137/0917055zbMath0858.65044OpenAlexW2119233169MaRDI QIDQ4891737
Publication date: 25 March 1997
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Full work available at URL: https://zenodo.org/record/1236138
algorithmssingular value decompositioncondition estimationQR factorizationsubspace trackingnumerical rankrank-revealing factorizationrank determinationnonsymmetric eigenproblemsleast squares computationslinear dependency analysis
Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical computation of matrix norms, conditioning, scaling (65F35) Orthogonalization in numerical linear algebra (65F25)
Related Items
Low-Rank Tucker Approximation of a Tensor from Streaming Data, Higher-Order QR with Tournament Pivoting for Tensor Compression, Randomized numerical linear algebra: Foundations and algorithms, Accurate solution of polynomial equations using Macaulay resultant matrices, Theoretical and Computable Optimal Subspace Expansions for Matrix Eigenvalue Problems, Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation, Subspaces Analysis for Random Projection UTV Framework, Randomized QR with Column Pivoting, Seq-SVF: an unsupervised data-driven method for automatically identifying hidden governing equations, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions, FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions, A literature survey of matrix methods for data science, Pass-efficient randomized LU algorithms for computing low-rank matrix approximation, Polynomial time \(\rho\)-locally maximum volume search, An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation, Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver, Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time, A fast solver for the narrow capture and narrow escape problems in the sphere, Lower bounds for column matrix approximations, The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Unnamed Item, SNS: A Solution-Based Nonlinear Subspace Method for Time-Dependent Model Order Reduction, Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction, An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations, Polyhedral homotopies in Cox coordinates, On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix, Unnamed Item, Literature survey on low rank approximation of matrices, Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting, Multipreconditioned Gmres for Shifted Systems, Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations, Analytical Low-Rank Compression via Proxy Point Selection, Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection, Effectively Subsampled Quadratures for Least Squares Polynomial Approximations, Introduction to Communication Avoiding Algorithms for Direct Methods of Factorization in Linear Algebra, Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices, Adaptively Compressed Polarizability Operator for Accelerating Large Scale Ab Initio Phonon Calculations, A Recursive Skeletonization Factorization Based on Strong Admissibility, Householder QR Factorization With Randomization for Column Pivoting (HQRRP), Estimation of atmospheric PSF parameters for hyperspectral imaging, An algebraic multifrontal preconditioner that exploits the low‐rank property, Compressing Rank-Structured Matrices via Randomized Sampling, Communication lower bounds and optimal algorithms for numerical linear algebra, A Newton method for rigid body frictional impact with multiple simultaneous impact points, Disentanglement via Entanglement: A Unified Method for Wannier Localization, Block Basis Factorization for Scalable Kernel Evaluation, Fast Coulomb Matrix Construction via Compressing the Interactions Between Continuous Charge Distributions, Interpolative Decomposition via Proxy Points for Kernel Matrices, Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition, Allocation Strategies for High Fidelity Models in the Multifidelity Regime, Fast Low-Rank Kernel Matrix Factorization Using Skeletonized Interpolation, Numerical algorithms for high-performance computational science, Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction, Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark, Functional Tucker Approximation Using Chebyshev Interpolation, Unnamed Item, Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds, Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning, Estimating Leverage Scores via Rank Revealing Methods and Randomization, Subspace Iteration Randomization and Singular Value Problems, Conjectures and Computations about Veronese Syzygies, Unnamed Item, CUR LRA at Sublinear Cost Based on Volume Maximization, Data-Driven Algorithms for Signal Processing with Trigonometric Rational Functions, A Nonlinear QR Algorithm for Banded Nonlinear Eigenvalue Problems, Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format, Strong rank revealing LU factorizations, Pass-efficient methods for compression of high-dimensional turbulent flow data, Efficient algorithms for CUR and interpolative matrix decompositions, Effective matrix-free preconditioning for the augmented immersed interface method, A fast block low-rank dense solver with applications to finite-element matrices, The Discrete Empirical Interpolation Method: Canonical Structure and Formulation in Weighted Inner Product Spaces, Column subset selection problem is UG-hard, New studies of randomized augmentation and additive preprocessing, An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, Improved bound for rank revealing LU factorizations, A fast direct solver for quasi-periodic scattering problems, Far-field compression for fast kernel summation methods in high dimensions, Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging, Gram-Schmidt orthogonalization: 100 years and more, Algorithms and error bounds for noisy phase retrieval with low-redundancy frames, A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems, An Accelerated Divide-and-Conquer Algorithm for the Bidiagonal SVD Problem, Universal quadratures for boundary integral equations on two-dimensional domains with corners, Error analysis of an accelerated interpolative decomposition for 3D Laplace problems, Randomized QLP decomposition, Pseudo-skeleton approximations with better accuracy estimates, SCDM-k: localized orbitals for solids via selected columns of the density matrix, Feature selection for linear SVM with provable guarantees, A randomized algorithm for the decomposition of matrices, A low-rank control variate for multilevel Monte Carlo simulation of high-dimensional uncertain systems, A new class of highly accurate solvers for ordinary differential equations, Efficient uncertainty propagation for network multiphysics systems, Randomized LU decomposition, New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem, Exponential inapproximability of selecting a maximum volume sub-matrix, A fast direct solver for the integral equations of scattering theory on planar curves with corners, A fast direct solver for boundary value problems on locally perturbed geometries, Parallel cross interpolation for high-precision calculation of high-dimensional integrals, Constructing nested bases approximations from the entries of non-local operators, An adaptive fast direct solver for boundary integral equations in two dimensions, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, Reduction of multivariate mixtures and its applications, Regularized greedy column subset selection, A note on sparse least-squares regression, Fast and accurate pseudoinverse with sparse matrix reordering and incremental approach, An equi-directional generalization of adaptive cross approximation for higher-order tensors, On the Nyström discretization of integral equations on planar curves with corners, Bi-fidelity approximation for uncertainty quantification and sensitivity analysis of irradiated particle-laden turbulence, Regression-aware decompositions, Fast linear algebra is stable, Parameter identification for nonlinear elliptic-parabolic systems with application in lithium-ion battery modeling, Randomized algorithms for the low-rank approximation of matrices, Sparse polynomial chaos expansions via compressed sensing and D-optimal design, Rank revealing Gaussian elimination by the maximum volume concept, A fast randomized algorithm for the approximation of matrices, A fast solver for Poisson problems on infinite regular lattices, Using low-rank approximation of the Jacobian matrix in the Newton-Raphson method to solve certain singular equations, A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains, Power-law solutions of anisotropic multi-material elasticity problems, An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths, Convergence to diagonal form of block Jacobi-type methods, Efficient methods for grouping vectors into low-rank clusters, Randomized LU decomposition using sparse projections, On growth factors of the modified Gram-Schmidt algorithm, An algorithm for the rapid evaluation of special function transforms, Efficient discretization of Laplace boundary integral equations on polygonal domains, Diffusion wavelets, Unnamed Item, A fast direct solver for boundary integral equations in two dimensions, Fast randomized matrix and tensor interpolative decomposition using countsketch, Minimum Sobolev norm interpolation of scattered derivative data, Fast algorithms for spherical harmonic expansions. III, Fast multipole preconditioners for sparse matrices arising from elliptic equations, A Fast Memory Efficient Construction Algorithm for Hierarchically Semi-Separable Representations, Randomized interpolative decomposition of separated representations, On the accuracy of cross and column low-rank maxvol approximations in average, Linear-time CUR approximation of BEM matrices, Summarization and Search Over Geometric Spaces, A DEIM Induced CUR Factorization, Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations, Split representation of adaptively compressed polarizability operator, HOID: Higher Order Interpolatory Decomposition for Tensors Based on Tucker Representation, A Fast Algorithm for Simulating Multiphase Flows Through Periodic Geometries of Arbitrary Shape, Reduced order models for Lagrangian hydrodynamics, Fast direct solvers for integral equations in complex three-dimensional domains, Numerical methods for accurate computation of the eigenvalues of Hermitian matrices and the singular values of general matrices, On the Stability of Some Hierarchical Rank Structured Matrix Algorithms, ALORA: affine low-rank approximations, An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling, A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices, Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems, ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations, Column subset selection via sparse approximation of SVD, On selecting a maximum volume sub-matrix of a matrix and related problems, Theory of functional connections applied to quadratic and nonlinear programming under equality constraints, Deviation maximization for rank-revealing QR factorizations, Fast and backward stable transforms between spherical harmonic expansions and bivariate Fourier series, On the existence and computation of rank-revealing LU factorizations, Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions, Local Lagrangian reduced-order modeling for the Rayleigh-Taylor instability by solution manifold decomposition, Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation, A high-order accurate accelerated direct solver for acoustic scattering from surfaces, Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices, Bi-fidelity reduced polynomial chaos expansion for uncertainty quantification, A fast algorithm for the inversion of general Toeplitz matrices
Uses Software
