Superfast algorithms for Cauchy-like matrix computations and extensions
type: Item
instance of: scholarly article
title: Superfast algorithms for Cauchy-like matrix computations and extensions
zbMATH Open document ID: 0971.65024
DOI: 10.1016/S0024-3795(00)00041-0
published in: Linear Algebra and its Applications
publication date: 2001-10-24T00:00:00Z
review text: The algorithm by \textit{M. Morf} [Doubling algorithms for Toeplitz and related equations, in: Proc. IEEE Int. Conf. on ASSP, IEEE Computer Soc. Press, Silvert Spring, MD, 954-959 (1980)] and by \textit{R. R. Bitmead} and \textit{B. D. D. Anderson} [ibid. 34, 103-116 (1980; Zbl 0458.65018)] to solve Toeplitz and Toeplitz-like systems is based on the notion of displacement rank and a divide and conquer strategy. In combination with the fast Fourier transform (FFT), this gives superfast algorithms that solve a system of size \(n\) in \(O(n\log^2 n)\) operations. In this paper, the authors develop a similar strategy for Cauchy (displacement rank 1) and Cauchy-like (displacement rank \(r\)) matrices. Here the displacement rank is with respect to the displacement operator \(\nabla A = D(q)A-AD(t)\) where \(D(q)\) and \(D(t)\) are diagonal matrices. Because matrix vector multiplications for these matrices can not be directly computed with FFT, the resulting algorithm has a complexity of \(O(nr^2\log^3n)\). In principle the algorithm works for strongly nonsingular matrices \(A\), but a technique of symmetrization and/or randomization can overcome this restriction. As by-products algorithms for determinant calculation, triangular factorization, least squares solution, and matrix inversion are obtained. The algorithms apply to matrices with entries from an arbitrary field. Comparison with other (super)fast algorithms for such matrices is also made.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F20
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 65F40
zbMATH DE Number: 1453254
zbMATH Keywords: Cauchy matrix
zbMATH Keywords: Cauchy-like matrix
zbMATH Keywords: superfast algorithm
zbMATH Keywords: displacement rank
zbMATH Keywords: rational interpolation
zbMATH Keywords: determinant
zbMATH Keywords: finite field
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: complexity
zbMATH Keywords: triangular factorization
zbMATH Keywords: least squares solution
zbMATH Keywords: matrix inversion
author: Victor Y. Pan
author: Ai-Long Zheng
MaRDI profile type: Publication
cites work: Asymptotically fast solution of Toeplitz and related systems of linear equations
cites work: Interpolation of rational matrix functions
cites work: Q4314299
cites work: Solution of Vandermonde systems of equations
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: Q4405419
cites work: A probabilistic remark on algebraic program testing
cites work: An inversion formula and fast algorithms for Cauchy-Vandermonde matrices
cites work: Norm estimates for inverses of Vandermonde matrices
cites work: Q3488301
cites work: Q5615001
cites work: A Fast Algorithm for the Multiplication of Generalized Hilbert Matrices with Vectors
cites work: Efficient solution of linear systems of equations with recursive structure
cites work: Linear complexity parallel algorithms for linear systems of equations with recursive structure
cites work: Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
cites work: Q3359644
cites work: Complexity of multiplication with vectors for structured matrices
cites work: Fast algorithms with preprocessing for matrix-vector multiplication problems
cites work: Fast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems
cites work: A fast algorithm for particle simulations
cites work: Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials
cites work: Stability Analysis of Algorithms for Solving Confluent Vandermonde-Like Systems
cites work: Algebraic methods for Toeplitz-like matrices and operators
cites work: Q4234327
cites work: Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
cites work: Displacement ranks of matrices and linear equations
cites work: Q4038737
cites work: Fast Solution of Confluent Vandermonde Linear Systems
cites work: Fast Algorithms for Confluent Vandermonde Linear Systems and Generalized Trummer’s Problem
cites work: Solution of Vandermonde-Like Systems and Confluent Vandermonde-Like Systems
cites work: Multivariate polynomials, duality, and structured matrices
cites work: Q4938647
cites work: A displacement approach to efficient decoding of algebraic-geometric codes
cites work: On Computations with Dense Structured Matrices
cites work: Parametrization of Newton's iteration for computations with structured matrices and applications
cites work: Decreasing the Displacement Rank of a Matrix
cites work: Q4952723
cites work: New transformations of Cauchy matrices and Trummer's problem
cites work: Q3156423
cites work: A Matrix Problem with Application to Rapid Solution of Integral Equations
cites work: Rapid solution of integral equations of classical potential theory
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: Gaussian elimination is not optimal
cites work: An Efficient Implementation of a Conformal Mapping Method Based on the Szegö Kernel
cites work: Q3851616
Recommended article: A Superfast Algorithm for Toeplitz Systems of Linear Equations
Recommended article: Q3349856
Recommended article: A fast algorithm for solving a Toeplitz system of equations
Recommended article: Fast algorithms for solving Toeplitz systems of equations using number-theoretic transforms
Recommended article: Stability of the Levinson Algorithm for Toeplitz-Like Systems
Recommended article: Q5498431

Superfast algorithms for Cauchy-like matrix computations and extensions (Recommended article)
Recommended article: Recursive algorithms for unbalanced banded Toeplitz systems
Similarity Score: 0.83131707
Recommender Run: Recommender Run 2

Superfast algorithms for Cauchy-like matrix computations and extensions (Recommended article)
Recommended article: Q4836733
Similarity Score: 0.82804716
Recommender Run: Recommender Run 2

Superfast algorithms for Cauchy-like matrix computations and extensions (Recommended article)
Recommended article: Q3777310
Similarity Score: 0.82753813
Recommender Run: Recommender Run 2

Superfast algorithms for Cauchy-like matrix computations and extensions (Recommended article)
Recommended article: Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
Similarity Score: 0.8271323
Recommender Run: Recommender Run 2