Transformations of matrix structures work again
From MaRDI portal
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)
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.
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
Cites work
- [[Item:Q2760974|scientific article; zbMATH DE number 1682655 (Why is no real title available?)]]
- [[Item:Q3613032|scientific article; zbMATH DE number 5527834 (Why is no real title available?)]]
- [[Item:Q3838074|scientific article; zbMATH DE number 1183880 (Why is no real title available?)]]
- [[Item:Q4220521|scientific article; zbMATH DE number 1226426 (Why is no real title available?)]]
- [[Item:Q4228445|scientific article; zbMATH DE number 1256709 (Why is no real title available?)]]
- [[Item:Q4314299|scientific article; zbMATH DE number 691245 (Why is no real title available?)]]
- [[Item:Q4365459|scientific article; zbMATH DE number 1083142 (Why is no real title available?)]]
- [[Item:Q4952723|scientific article; zbMATH DE number 1445400 (Why is no real title available?)]]
- [[Item:Q5689624|scientific article; zbMATH DE number 961607 (Why is no real title available?)]]
- A Fast Adaptive Multipole Algorithm for Particle Simulations
- A Fast Solver for HSS Representations via Sparse Matrices
- A Superfast Algorithm for Toeplitz Systems of Linear Equations
- A bibliography on semiseparable matrices
- A fast algorithm for particle simulations
- A fast algorithm for the inversion of general Toeplitz 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
- A superfast structured solver for Toeplitz linear systems via randomized sampling
- An algebraic approach to approximate evaluation of a polynomial on a set of real points
- Approximate displacement rank and applications
- Complexity of multiplication with vectors for structured matrices
- Computations with quasiseparable polynomials and matrices
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Displacement ranks of matrices and linear equations
- Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
- Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation
- Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
- Fast Solution of Toeplitz‐ and Cauchy‐Like Least‐Squares Problems
- Fast and Efficient Parallel Solution of Sparse Linear Systems
- Fast approximate computations with Cauchy matrices, polynomials and rational functions
- Generalized Nested Dissection
- Generalized inverses of certain Toeplitz matrices
- Incomplete cross approximation in the mosaic-skeleton method
- Inversion of Displacement Operators
- Linear complexity algorithms for semiseparable matrices
- Lower bounds for the condition number of Vandermonde matrices
- Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization
- On the Boolean complexity of real root refinement
- On the complexity of some hierarchical structured matrix algorithms
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Randomized sparse direct solvers
- Stable and Efficient Algorithms for Structured Systems of Linear Equations
- Superfast and stable structured solvers for Toeplitz least squares via randomized sampling
Cited in
(12)- Fast approximate computations with Cauchy matrices and polynomials
- Fast approximate computations with Cauchy matrices, polynomials and rational functions
- An efficient, memory-saving approach for the Loewner framework
- Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions
- On Computations with Dense Structured Matrices
- Analytical low-rank compression via proxy point selection
- How bad are Vandermonde matrices?
- Solving Toeplitz- and Vandermonde-like linear systems with large displacement rank
- Fast matrix multiplication and its algebraic neighbourhood
- On matrices with displacement structure: generalized operators and faster algorithms
- Nearly optimal computations with structured matrices
- Nearly optimal computations with structured matrices
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)
