Superfast algorithms for Cauchy-like matrix computations and extensions

DOI10.1016/S0024-3795(00)00041-0zbMath0971.65024MaRDI QIDQ1978119

Publication date: 24 October 2001

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

complexity; rational interpolation; fast Fourier transform; finite field; determinant; matrix inversion; least squares solution; Cauchy-like matrix; Cauchy matrix; triangular factorization; superfast algorithm; displacement rank

Mathematics Subject Classification ID

65F20: Numerical solutions to overdetermined systems, pseudoinverses

65F40: Numerical computation of determinants

65Y20: Complexity and performance of numerical algorithms

65F05: Direct numerical methods for linear systems and matrix inversion

Related Items

Iterative inversion of structured matrices, A fast algorithm for the inversion of general Toeplitz matrices, Solving structured linear systems with large displacement rank, An efficient solution for Cauchy-like systems of linear equations

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Linear complexity parallel algorithms for linear systems of equations with recursive structure
Algebraic methods for Toeplitz-like matrices and operators
Efficient solution of linear systems of equations with recursive structure
Rapid solution of integral equations of classical potential theory
Displacement ranks of matrices and linear equations
Asymptotically fast solution of Toeplitz and related systems of linear equations
On fast multiplication of polynomials over arbitrary algebras
Interpolation of rational matrix functions
Parametrization of Newton's iteration for computations with structured matrices and applications
Norm estimates for inverses of Vandermonde matrices
A probabilistic remark on algebraic program testing
Complexity of multiplication with vectors for structured matrices
Fast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems
Fast algorithms with preprocessing for matrix-vector multiplication problems
New transformations of Cauchy matrices and Trummer's problem
Multivariate polynomials, duality, and structured matrices
An inversion formula and fast algorithms for Cauchy-Vandermonde matrices
Gaussian elimination is not optimal
A displacement approach to efficient decoding of algebraic-geometric codes
Stability Analysis of Algorithms for Solving Confluent Vandermonde-Like Systems
On Computations with Dense Structured Matrices
An Efficient Implementation of a Conformal Mapping Method Based on the Szegö Kernel
A Fast Algorithm for the Multiplication of Generalized Hilbert Matrices with Vectors
Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials
Fast Probabilistic Algorithms for Verification of Polynomial Identities
Decreasing the Displacement Rank of a Matrix
Fast Solution of Confluent Vandermonde Linear Systems
Fast Algorithms for Confluent Vandermonde Linear Systems and Generalized Trummer’s Problem
Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
Solution of Vandermonde-Like Systems and Confluent Vandermonde-Like Systems
Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
A Matrix Problem with Application to Rapid Solution of Integral Equations
Solution of Vandermonde systems of equations
A fast algorithm for particle simulations