A superfast solver for Sylvester's resultant linear systems generated by a stable and an anti-stable polynomial (Q1874670): Difference between revisions

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.