A superfast solver for Sylvester's resultant linear systems generated by a stable and an anti-stable polynomial
type: Item
instance of: scholarly article
title: A superfast solver for Sylvester's resultant linear systems generated by a stable and an anti-stable polynomial
zbMATH Open document ID: 1027.65063
DOI: 10.1016/S0024-3795(02)00595-5
published in: Linear Algebra and its Applications
publication date: 2003-05-25T00:00:00Z
review text: A method for the solution of \((n+ m)\times (n+m)\) Sylvester's resultant linear systems associated with two real polynomials, a stable one (i.e., all its roots lie inside the unit circle) \(a(z)\) and an anti-stable one (i.e., \(z^m c(z^{-1})\) is stable) \(c(z)\) of the degree \(n\) and \(m\), respectively, is developed. The proposed scheme proceeds by iteratively constructing a sequence of increasing approximations of the solution. Each iterative step can be performed in \(O((n+ m) \log(n+m))\) arithmetic operations by combining fast polynomial arithmetic based on the fast Fourier transform with displacement rank theory of structured matrices. In addition the resulting process is shown to be quadratically convergent right from the start. The method is based on a blend of ideas from structured numerical linear algebra, computation complex analysis and linear operator theory. Finally, the results of many numerical experiments, which confirm the super fast effectiveness and robustness of the proposed algorithm are reported and discussed.
Mathematics Subject Classification ID: 65H05
Mathematics Subject Classification ID: 65F30
zbMATH DE Number: 1915807
zbMATH Keywords: Sylvester's resultant matrices
zbMATH Keywords: polynomial computations
zbMATH Keywords: stable polynomials
zbMATH Keywords: cyclic reduction
zbMATH Keywords: spectral factorization
zbMATH Keywords: displacement theory
zbMATH Keywords: computational complexity
zbMATH Keywords: numerical experiments
zbMATH Keywords: algorithm
author: L. Gemignani
reviewed by: Jiří Vaníček
describes a project that uses: na12
MaRDI profile type: Publication
cites work: Q3309525
cites work: Fast fraction-free triangularization of Bézoutians with applications to sub-resultant chain computation
cites work: Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations
cites work: Computations with infinite Toeplitz matrices and polynomials
cites work: Improved cyclic reduction for solving queueing problems
cites work: Effective Methods for Solving Banded Toeplitz Systems
cites work: Q4314299
cites work: Introduction to large truncated Toeplitz matrices
cites work: Q3847819
cites work: On Euclid's Algorithm and the Theory of Subresultants
cites work: On Direct Methods for Solving Poisson’s Equations
cites work: Power series remainder sequences and Padé fractions over an integral domain
cites work: Subresultants and Reduced Polynomial Remainder Sequences
cites work: The Euclid algorithm and the fast computation of cross-covariance and autocovariance sequences
cites work: A Newton-Raphson method for moving-average spectral factorization using the Euclid algorithm
cites work: Q4309001
cites work: Computing a Hurwitz factorization of a polynomial
cites work: A numerical approach to the solution of stable resultant linear systems
cites work: Lyapunov equations for companion matrices
cites work: Q4072022
cites work: Q3309712
cites work: Q3768294
cites work: The roles of Sylvester and Bezoutian matrices in the historical study of stability of linear discrete-time systems
cites work: Displacement ranks of matrices and linear equations
cites work: Fast computation of contour integrals of rational functions
cites work: Inertia characteristics of self-adjoint matrix polynomials
cites work: Efficient implementation of wilson's algorithm for factorizing a self-reciprocal polynomial
cites work: Q4733209
cites work: Variations on computing reciprocals of power series
cites work: Spectral fractorization of Laurent polynomials
cites work: Factorization of the Covariance Generating Function of a Pure Moving Average Process
description: scientific article; zbMATH DE number 1915807