Stable and Efficient Algorithms for Structured Systems of Linear Equations
A Cauchy-like matrix has the form \[ C= \Biggl({a^T_i b_j\over \omega_i-\lambda_j}\Biggr)_{1\leq i,j\leq n}\qquad (a_i, b_j\in\mathbb{R}^\alpha), \] where \(\alpha\ll n\). It satisfied a so-called displacement equation, i.e., \[ \Omega C- C\Lambda= A\cdot B\qquad (A\in\mathbb{R}^{n\times\alpha}, B\in\mathbb{R}^{\alpha\times n}). \] The author studies variations of a fast Gaussian elimination algorithm with partial or complete pivoting for Cauchy-like matrices, working systematically with the displacement equation. He describes algorithms that avoid internal element growths and therefore have better backward error properties than the existing methods. The solution of Toeplitz, Hankel and Toeplitz-plus-Hankel matrices can be reduced (in more than one way) to solutions of linear systems with a Cauchy-like matrix. The author discusses implementation techniques that further reduce execution. He presents a careful error analysis, flow counts and extensive numerical experiments that show the superiority of the newly developed methods.
- An efficient solution for Cauchy-like systems of linear equations
- Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
- Diagonal pivoting for partially reconstructible Cauchy-like matrices, with applications to Toeplitz-like linear equations and to boundary rational matrix interpolation problems
- Solving Toeplitz systems after extension and transformation
- Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. II: Algorithms
- Pivoting and backward stability of fast algorithms for solving Cauchy linear equations
- Factorizations of Cauchy matrices
- Look-ahead methods for block Hankel systems
- A least squares approach to reduce stable discrete linear systems preserving their stability.
- Fast iterative adaptive multi-quadric radial basis function method for edges detection of piecewise functions. I: Uniform mesh
- An efficient solution for Cauchy-like systems of linear equations
- A superfast method for solving Toeplitz linear least squares problems.
- Toward the best algorithm for approximate GCD of univariate polynomials
- Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
- A fast and stable algorithm for downdating the singular value decomposition
- Algorithms that preserve the volume amplification factor for linear systems
- Orthogonal Cauchy-like matrices
- Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions
- How bad are Vandermonde matrices?
- Accurate solution of structured linear systems via rank-revealing decompositions
- An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
- Fast computation of the matrix exponential for a Toeplitz matrix
- scientific article; zbMATH DE number 3863012 (Why is no real title available?)
- scientific article; zbMATH DE number 4028839 (Why is no real title available?)
- scientific article; zbMATH DE number 64181 (Why is no real title available?)
- scientific article; zbMATH DE number 4124891 (Why is no real title available?)
- Numerical stability of some fast algorithms for structured matrices
- Transformations of matrix structures work again
- scientific article; zbMATH DE number 2098303 (Why is no real title available?)
- Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
- Fast approximate computations with Cauchy matrices, polynomials and rational functions
- Efficient algorithms for solving systems of linear equations and path problems
- Algorithms for structured linear systems solving and their implementation
- Solving structured linear systems of large displacement rank
- A note on the O(n)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices
- A fast solver for linear systems with displacement structure
- A Fast Algorithm for Computing Macaulay Null Spaces of Bivariate Polynomial Systems
- Diagonal pivoting for partially reconstructible Cauchy-like matrices, with applications to Toeplitz-like linear equations and to boundary rational matrix interpolation problems
- Fast recovery and approximation of hidden Cauchy structure
- Randomized preprocessing of homogeneous linear systems of equations
- A unified least squares approach to identify and to reduce continuous asymptotically stable systems
This page was built for publication: Stable and Efficient Algorithms for Structured Systems of Linear Equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4389075)