Subdivision schemes are nowadays customary in curve and surface modeling. In this paper the problem of designing interpolatory subdivision schemes is considered. The idea is to modify a given approximating subdivision scheme just enough to satisfy the interpolation requirement. From an algebraic point of view this leads to the solution of a generalized Bezout polynomial equation possibly involving more than two polynomials. By exploiting the matrix counterpart of this equation it is shown that small-degree solutions can be generally found by inverting an associated structured matrix of Toeplitz-like form. If the approximating scheme is defined in terms of a free parameter, then the inversion can be performed by numeric-symbolic methods.

In this paper we discuss the use of structured matrix methods for the numerical approximation of the zeros of a univariate polynomial. In particular, it is shown that root-finding algorithms based on floating-point eigenvalue computation can benefit from the structure of the matrix problem to reduce their complexity and memory requirements by an order of magnitude.

In this paper we present a suitable generalization of the classical Graeffe's iteration by showing that it provides effective algorithms for the fast evaluation of polynomials and residues of rational and meromorphic functions. In particular, if g(z) = q(z)/p(z) is a rational function with n finite poles ξ1,…,ξn and ξ is an initial approximation of ξk such that ¦ξ - ξk¦ < ¦ξ - ξj¦ for any j ≠ k, 1 ⪇ j ⪇ n, then an extrapolation method is found for computing the residue of g(z) at ξk by means of successive evaluations of the derivatives of q(z) and p(z) at the point z = ξ. In the case where q(z) = zp′(z) we thus obtain a set of iterations for the refinement of polynomial zeros. Moreover, by setting q(z) = r(z)p′(z), the same approach can also be used for the fast approximate evaluation of r(z) on the zeros of p(z).

A new algorithm is presented for computing an integer polynomial similar to the GCD of two polynomials 7~(z) and v(z) E Z[z], deg (u(~)) = n 2 deg (v(z)).Our approach uses structured matrix computations involving Bezout matrices rather than Hankel matrices.In this way we reduce the computational costs showing that the new algorithm requires 0(n2) arithmetical operations or 0(rr4(log2 n + 12)) Boolean operations, where 1 = max{log(ll u(z) Ilm), log(ll u(x) Ilm)}. 1

Previous article Full AccessErratum: Fast Parallel Computation of the Polynomial Remainder Sequence via Bezout and Hankel MatricesDario Bini and Luca GemignaniDario Bini and Luca Gemignanihttps://doi.org/10.1137/0225062PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Erratum: Fast Parallel Computation of the Polynomial Remainder Sequence via Bezout and Hankel Matrices." SIAM Journal on Computing, 25(6), p. 1358[1] Dario Bini and , Luca Gemignani, Fast parallel computation of the polynomial remainder sequence via Bézout and Hankel matrices, SIAM J. Comput., 24 (1995), 63–77 10.1137/S0097539791201903 95j:65048 0818.68092 LinkISIGoogle ScholarKeywordsEuclidean schemegreatest common divisorHankel and Bezout matricescomputational complexityparallel algorithms Previous article FiguresRelatedReferencesCited byDetails Fast fraction-free triangularization of Bezoutians with applications to sub-resultant chain computationLinear Algebra and its Applications, Vol. 284, No. 1-3 Cross Ref Volume 25, Issue 6| 1996SIAM Journal on Computing History Submitted:14 February 1996Accepted:15 February 1996Published online:31 July 2006 InformationCopyright © 1996 © Society for Industrial and Applied MathematicsKeywordsEuclidean schemegreatest common divisorHankel and Bezout matricescomputational complexityparallel algorithmsMSC codes68Q2565Y05PDF Download Article & Publication DataArticle DOI:10.1137/0225062Article page range:pp. 1358-1358ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

If $u(x)$ and $v(x)$ are polynomials of degree n and m, respectively, $m < n$, all the coefficients of the polynomials generated by the Euclidean scheme applied to $u(x)$ and $v(x)$ can be computed by using $O(\log^{3} n)$ parallel arithmetic steps and $n^{2}/ \log n$ processors over any field of characteristic 0 supporting FFT (Fast Fourier Transform). If the field does not support FFT the number of processors is increased by a factor of $\log \log n$; if the field does not allow division by $n!$ the number of processors is increased by a factor of n. This result is obtained by reducing the Euclidean scheme to computing the block triangular factorization of the Bezout matrix associated with $u(x)$ and $v(x)$. This approach is also extended to the evaluation of polynomial gcd (greatest common divisor) over any field of constants in $O(\log^{2} n)$ steps with the same number of processors.

The parallel complexity of the simultaneous approximation to all the zeros of a polynomial is investigated. By modifying and analyzing an algorithm given by Householder, it is possible to obtain a priori bounds to the number of iterations sufficient to yield a given accuracy, and to the number of digits required in the finite arithmetic. More classes of polynomials, for which the simultaneous approximation to all the zeros can be carried out in polylogarithmic time, are found. Some cases of polynomials, customarily considered hard, are easily solved. The root-finding problem for a polynomial of degree n, having zeros $z_i $, $i = 1, \cdots ,n$ is $\mathcal{NC}$-reduced to finding a polynomial $a(z)$ such that $|a(z_i + 1)/a(z_i )| \leq 1 - 1/n^c $, where c is a constant.