Efficient Ehrlich-Aberth iteration for finding intersections of interpolating polynomials and rational functions

We analyze the problem of carrying out an efficient iteration to approximate the eigenvalues of some rank structured pencils obtained as linearization of sums of polynomials and rational functions expressed in (possibly different) interpolation bases. The class of linearizations that we consider has been introduced by Robol, Vandebril and Van Dooren in [17]. We show that a traditional QZ iteration on the pencil is both asymptotically slow (since it is a cubic algorithm in the size of the matrices) and sometimes not accurate (since in some cases the deflation of artificially introduced infinite eigenvalues is numerically difficult). To solve these issues we propose to use a specifically designed Ehrlich-Aberth iteration that can approximate the eigenvalues in O(kn²) flops, where k is the average number of iterations per eigenvalue, and n the degree of the linearized polynomial. We suggest possible strategies for the choice of the initial starting points that make k asymptotically smaller than O(n), thus making this method less expensive than the QZ iteration. Moreover, we show in the numerical experiments that this approach does not suffer of numerical issues, and accurate results are obtained.