A Superfast Structured Solver for Toeplitz Linear Systems via Randomized Sampling

DOI10.1137/110831982zbMath1258.65030OpenAlexW1973915465MaRDI QIDQ4902924

Publication date: 18 January 2013

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110831982

zbMATH Keywords

stability numerical examples Toeplitz matrix QR factorization Cauchy-like matrix hierarchically semiseparable matrix superfast Toeplitz solver precomputation randomized sampling structure-preserving rank-revealing factorization

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Toeplitz, Cauchy, and related matrices (15B05)

Related Items

SuperDC: Superfast Divide-And-Conquer Eigenvalue Decomposition With Improved Stability for Rank-Structured Matrices, Effective matrix-free preconditioning for the augmented immersed interface method, Fast iterative adaptive multi-quadric radial basis function method for edges detection of piecewise functions. I: Uniform mesh, Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case, Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations, On the rational approximation of Markov functions, with applications to the computation of Markov functions of Toeplitz matrices, Uncertainty quantification and stochastic polynomial chaos expansion for recovering random data in Darcy and diffusion equations, A Fast Contour-Integral Eigensolver for Non-Hermitian Matrices, Effective and Robust Preconditioning of General SPD Matrices via Structured Incomplete Factorization, A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions, Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems, hm-toolbox: MATLAB Software for HODLR and HSS Matrices, Fast matrix multiplication and its algebraic neighbourhood, Transformations of matrix structures work again, Fast structured Jacobi-Jacobi transforms, Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations, Analytical Low-Rank Compression via Proxy Point Selection, Fast Solution Methods for Convex Quadratic Optimization of Fractional Differential Equations, An ADMM-LAP method for total variation myopic deconvolution of adaptive optics retinal images, Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations, Low-Rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions, An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures, A Fast Memory Efficient Construction Algorithm for Hierarchically Semi-Separable Representations, Estimating the norms of random circulant and Toeplitz matrices and their inverses, Superfast Divide-and-Conquer Method and Perturbation Analysis for Structured Eigenvalue Solutions, Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations, How Bad Are Vandermonde Matrices?, A stable matrix version of the fast multipole method: stabilization strategies and examples, On the Stability of Some Hierarchical Rank Structured Matrix Algorithms, An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling, Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems, Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction, Fast Computation of the Matrix Exponential for a Toeplitz Matrix, Interconnected hierarchical structures for fast direct elliptic solution, A Distributed-Memory Package for Dense Hierarchically Semi-Separable Matrix Computations Using Randomization, Fast approximate computations with Cauchy matrices and polynomials, Real polynomial root-finding by means of matrix and polynomial iterations