Transformations of matrix structures work again
From MaRDI portal
Publication:471925
DOI10.1016/J.LAA.2014.09.004zbMATH Open1310.15006arXiv1303.0353OpenAlexW2963605062MaRDI QIDQ471925FDOQ471925
Publication date: 17 November 2014
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: In 1989 we proposed to employ Vandermonde and Hankel multipliers to transform into each other the matrix structures of Toeplitz, Hankel, Vandermonde and Cauchy types as a means of extending any successful algorithm for the inversion of matrices having one of these structures to inverting the matrices with the structures of the three other types. Surprising power of this approach has been demonstrated in a number of works, which culminated in ingeneous numerically stable algorithms that approximated the solution of a nonsingular Toeplitz linear system in nearly linear (versus previuosly cubic) arithmetic time. We first revisit this powerful method, covering it comprehensively, and then specialize it to yield a similar acceleration of the known algorithms for computations with matrices having structures of Vandermonde or Cauchy types. In particular we arrive at numerically stable approximate multipoint polynomial evaluation and interpolation in nearly linear arithmetic time.
Full work available at URL: https://arxiv.org/abs/1303.0353
Recommendations
- Fast approximate computations with Cauchy matrices, polynomials and rational functions
- Fast approximate computations with Cauchy matrices and polynomials
- Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. II: Algorithms
- Nearly optimal computations with structured matrices
- Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. I: Transformations
Vandermonde matricesToeplitz matricesCauchy matricesHSS matricesmultipole methodtransformations of matrix structures
Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25) Linear equations (linear algebraic aspects) (15A06) Theory of matrix inversion and generalized inverses (15A09) Numerical interpolation (65D05) Structure theory of linear operators (47A65) Linear transformations, semilinear transformations (15A04)
Cites Work
- Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Fast Solution of Toeplitz‐ and Cauchy‐Like Least‐Squares Problems
- Title not available (Why is that?)
- Generalized Nested Dissection
- A fast algorithm for particle simulations
- Incomplete cross approximation in the mosaic-skeleton method
- Title not available (Why is that?)
- Approximate displacement rank and applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Superfast Algorithm for Toeplitz Systems of Linear Equations
- Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation
- Inversion of Displacement Operators
- A fast algorithm for the inversion of general Toeplitz matrices
- A Fast Adaptive Multipole Algorithm for Particle Simulations
- A Fast Solver for HSS Representations via Sparse Matrices
- Linear complexity algorithms for semiseparable matrices
- Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
- Generalized inverses of certain Toeplitz matrices
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- A bibliography on semiseparable matrices
- Displacement ranks of matrices and linear equations
- Complexity of multiplication with vectors for structured matrices
- Lower bounds for the condition number of Vandermonde matrices
- A logarithmic Boolean time algorithm for parallel polynomial division
- A modification of the Dewilde-van der Veen method for inversion of finite structured matrices
- A new approach to fast polynomial interpolation and multipoint evaluation
- An algebraic approach to approximate evaluation of a polynomial on a set of real points
- Computations with quasiseparable polynomials and matrices
- Superfast and stable structured solvers for Toeplitz least squares via randomized sampling
- On the complexity of some hierarchical structured matrix algorithms
- On the boolean complexity of real root refinement
- Title not available (Why is that?)
- Fast and Efficient Parallel Solution of Sparse Linear Systems
- Title not available (Why is that?)
- Stable and Efficient Algorithms for Structured Systems of Linear Equations
- A Superfast Structured Solver for Toeplitz Linear Systems via Randomized Sampling
- Title not available (Why is that?)
- Fast Approximate Computations with Cauchy Matrices, Polynomials and Rational Functions
- Randomized Sparse Direct Solvers
- Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization
Cited In (9)
- Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions
- How bad are Vandermonde matrices?
- On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms
- Fast matrix multiplication and its algebraic neighbourhood
- Analytical Low-Rank Compression via Proxy Point Selection
- An efficient, memory-saving approach for the Loewner framework
- On Computations with Dense Structured Matrices
- Fast approximate computations with Cauchy matrices and polynomials
- Nearly optimal computations with structured matrices
Uses Software
This page was built for publication: Transformations of matrix structures work again
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471925)
