Transformations of matrix structures work again

DOI10.1016/j.laa.2014.09.004zbMath1310.15006arXiv1303.0353OpenAlexW2963605062MaRDI QIDQ471925

Pan, Victor Y.

Publication date: 17 November 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1303.0353

zbMATH Keywords

Toeplitz matricesVandermonde matricesCauchy matricesHSS matricesmultipole methodtransformations of matrix structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of matrix inversion and generalized inverses (15A09) Numerical interpolation (65D05) Structure theory of linear operators (47A65) Linear transformations, semilinear transformations (15A04) Direct numerical methods for linear systems and matrix inversion (65F05) Linear equations (linear algebraic aspects) (15A06)

Related Items

An efficient, memory-saving approach for the Loewner framework, 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, Superfast Divide-and-Conquer Method and Perturbation Analysis for Structured Eigenvalue Solutions, How Bad Are Vandermonde Matrices?, Nearly optimal computations with structured matrices, Fast approximate computations with Cauchy matrices and polynomials

Uses Software

• hlib
• na20
• tpls

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
• Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization
• A fast algorithm for the inversion of general Toeplitz matrices
• Linear complexity algorithms for semiseparable matrices
• Lower bounds for the condition number of Vandermonde matrices
• A logarithmic Boolean time algorithm for parallel polynomial division
• Displacement ranks of matrices and linear equations
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)]
• Complexity of multiplication with vectors for structured matrices
• A modification of the Dewilde-van der Veen method for inversion of finite structured matrices
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Incomplete cross approximation in the mosaic-skeleton method
• 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
• Generalized inverses of certain Toeplitz matrices
• 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
• A Superfast Algorithm for Toeplitz Systems of Linear Equations
• A Fast Adaptive Multipole Algorithm for Particle Simulations
• Generalized Nested Dissection
• Fast and Efficient Parallel Solution of Sparse Linear Systems
• Stable and Efficient Algorithms for Structured Systems of Linear Equations
• Inversion of Displacement Operators
• Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation
• Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
• A Superfast Structured Solver for Toeplitz Linear Systems via Randomized Sampling
• Fast Approximate Computations with Cauchy Matrices, Polynomials and Rational Functions
• Fast Solution of Toeplitz‐ and Cauchy‐Like Least‐Squares Problems
• Randomized Sparse Direct Solvers
• A Fast Solver for HSS Representations via Sparse Matrices
• A bibliography on semiseparable matrices
• A fast algorithm for particle simulations