A superfast solver for Sylvester's resultant linear systems generated by a stable and an anti-stable polynomial

摘要

We develop a superfast method for the solution of (n + m) x (n + m) Sylvester's resultant linear systems associated with two real polynomials a (z) and c (z) of degree n and m, respectively, where a(z) is a stable polynomial, i.e., all its roots lie inside the unit circle, whereas c(z) is an anti-stable polynomial, i.e, z(m)c(z(-1)) is stable. The proposed scheme proceeds by iteratively constructing a sequence of increasing approximations of the solution. It is based on a blend of ideas from structured numerical linear algebra, computational complex analysis and linear operator theory. Each iterative step can be performed in O((n + m) log(n + m)) arithmetic operations by combining fast polynomial arithmetic based on FFT with displacement rank theory for structured matrices. In addition, the resulting process is shown to be quadratically convergent right from the start since the approximation error at the jth iteration is O(r(2j)), where r = (max(a(alphai)=0)lpha(i)/(min(c(gammai)=0)gammai) denotes the separation ratio between the spectrum of a(z) and c(z). Finally, we report and discuss the results of many numerical experiments which confirm the effectiveness and the robustness of the proposed algorithm. (C) 2003 Elsevier Science Inc. All rights reserved. [References: 35]