Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
From MaRDI portal
Publication:4878512
DOI10.2307/2153371zbMath0848.65010OpenAlexW2036932727MaRDI QIDQ4878512
Israel Gohberg, Thomas Kailath, Vadim Olshevsky
Publication date: 27 October 1996
Published in: Mathematics of Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/dee42fd597777ad62d977cc6d45431603f5c7fbe
Gauss eliminationSchur algorithmpartial pivotingVandermonde-like matricesblock-Toeplitz systemsCauchy-like displacement structureSylvester-type equation
Related Items
A superfast method for solving Toeplitz linear least squares problems., A fast and stable algorithm for downdating the singular value decomposition, Pseudospectra of Loewner Matrix Pencils, A Lagrange matrices approach to confluent Cauchy matrices, Fast iterative adaptive multi-quadric radial basis function method for edges detection of piecewise functions. I: Uniform mesh, Pivoting and backward stability of fast algorithms for solving Cauchy linear equations, Inversion error, condition number, and approximate inverses of uncertain matrices, Fast direct solution methods for symmetric banded Toeplitz systems, based on the sine transform, Structured matrices and Newton's iteration: unified approach, Computational Methods for Linear Matrix Equations, Stability analysis of a general Toeplitz system solver, On the fast solution of Toeplitz-block linear systems arising in multivariate approximation theory, Newton's iteration for inversion of Cauchy-like and other structured matrices, Displacement-structure approach to polynomial Vandermonde and related matrices, Computing curve intersection by means of simultaneous iterations, The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related matrices, On the rational approximation of Markov functions, with applications to the computation of Markov functions of Toeplitz matrices, Solving large-scale nonsymmetric algebraic Riccati equations from two-dimensional transport models by doubling, A lookahead algorithm for the solution of block Toeplitz systems, On rational B-splines with prescribed poles, Iterative inversion of structured matrices, Generalized Cauchy-Vandermonde matrices, Lagrange's formula for tangential interpolation with application to structured matrices, An Accelerated Divide-and-Conquer Algorithm for the Bidiagonal SVD Problem, Factorizations of Cauchy matrices, Look-ahead methods for block Hankel systems, A stabilized superfast solver for indefinite Hankel systems, Eigenvector computation for almost unitary Hessenberg matrices and inversion of Szegö-Vandermonde matrices via discrete transmission lines, High performance algorithms for Toeplitz and block Toeplitz matrices, A fast solver for linear systems with displacement structure, Spectral properties of Toeplitz-plus-Hankel matrices, Solving Toeplitz systems after extension and transformation, A fast block Hankel solver based on an inversion formula for block Loewner matrices, Displacement structure approach to discrete-trigonometric-transform based preconditioners of G. Strang type and of T. Chan type, Recursive properties of Toeplitz and Hurwitz matrices, A modified structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equations from transport theory, Wiener-Hopf and spectral factorization of real polynomials by Newton's method, Some predictor-corrector-type iterative schemes for solving nonsymmetric algebraic Riccati equations arising in transport theory, Orthogonal Cauchy-like matrices, Matrix computations and polynomial root-finding with preprocessing, Randomized preprocessing versus pivoting, Additive preconditioning and aggregation in matrix computations, A Fast Algorithm for Computing Macaulay Null Spaces of Bivariate Polynomial Systems, Fast recovery and approximation of hidden Cauchy structure, Parallel computation of the eigenvalues of symmetric Toeplitz matrices through iterative methods, Matrix Structures in Queuing Models, A Fast Schur–Euclid-Type Algorithm for Quasiseparable Polynomials, Solving linear systems of equations with randomization, augmentation and aggregation, Low memory and low complexity iterative schemes for a nonsymmetric algebraic Riccati equation arising from transport theory, Displacement structures and fast inversion formulas for confluent polynomial Vandermonde-like matrices, A least squares approach to reduce stable discrete linear systems preserving their stability., Transformations of matrix structures work again, A multilevel parallel algorithm to solve symmetric Toeplitz linear systems, A fast parallel Björck-Pereyra-type algorithm for solving Cauchy linear equations, Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization, Generalized-confluent Cauchy and Cauchy-Vandermonde matrices, Superfast algorithms for Cauchy-like matrix computations and extensions, Fast QR factorization of Cauchy-like matrices, Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. I: Transformations, Diagonal pivoting for partially reconstructible Cauchy-like matrices, with applications to Toeplitz-like linear equations and to boundary rational matrix interpolation problems, Displacement structures and fast inversion formulas for confluent polynomial Vandermonde-like matrices, Fast computation of determinants of Bézout matrices and application to curve implicitization, On a class of matrices with low displacement rank, Randomized preprocessing of homogeneous linear systems of equations, An efficient solution for Cauchy-like systems of linear equations, Block LU-factorization of confluent Vandermonde matrices, Structural and computational properties of possibly singular semiseparable matrices, Displacement structure approach to Cauchy and Cauchy-Vandermonde matrices: Inversion formulas and fast algorithms, A unified least squares approach to identify and to reduce continuous asymptotically stable systems, A fast iterative method for determining the stability of a polynomial, A note on the \(O(n)\)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices, Superfast Divide-and-Conquer Method and Perturbation Analysis for Structured Eigenvalue Solutions, How Bad Are Vandermonde Matrices?, Optimal trigonometric preconditioners for nonsymmetric Toeplitz systems, A fast Hankel solver based on an inversion formula for Loewner matrices, Generalized confluent Cauchy-Vandermonde matrices: Displacement structures, inversion formulas and tangential interpolations, Confluent polynomial Vandermonde-like matrices: Displacement structures, inversion formulas and fast algorithm, Fast Computation of the Matrix Exponential for a Toeplitz Matrix, Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. II: Algorithms, Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation, A fast algorithm for multivariate Hermite interpolation, Fast approximate computations with Cauchy matrices and polynomials, A look-ahead block Schur algorithm for diagonal plus semiseparable matrices
