The relationship between univariate polynomial ∈-gcd and factorization of resultant matrices is investigated and several stable and effective algorithms for the computation of an ∈-gcd are proposed. The main result is the design of a practically stable algorithm whose arithmetic cost is quadratic in the degrees of the input polynomials. The algorithm relies on the displacement structure properties of Sylvester and Bezout matrices. Its effectiveness is confirmed by numerical experiments.

Surprisingly simple corollaries from the Courant--Fischer minimax characterization theorem enable us to devise a very effective algorithm for the evaluation of a set S interleaving the set E of the eigenvalues of an n X n real symmetric tridiagonal (rst) matrix T n (as well as a point that splits E into two subsets of comparable cardinalities). Furthermore, we extend this algorithm so as to approximate all the n eigenvalues of T n at nearly optimal sequential and parallel cost, that is, at the cost of staying within polylogarithmic factors from the straightforward lower bounds. The resulting improvement of the known processor bound in NC algorithms for the rst-eigenproblem is roughly by factor n. Our approach extends the previous works [M. Ben-Or and P. Tiwari, J. Complexity, 6(1990), pp. 417--442] and [M. Ben-Or et al., SIAM J. Comput., 17(1988), pp. 1081--1092] for the approximation of the zeros of a polynomial having only real zeros, and our algorithm leads to an alternative and simplified derivation of the known record parallel and sequential complexity estimates for the latter problem.

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 authors compute the first N coefficients of the reciprocal $r(x)$, $r(x)p(x) = 1\bmod x^N $ (given a natural N and a polynomial $p(x)$), $(p(0) \ne 0)$, by using $O(h\log N)$ arithmetic steps and $O(({N / h})(1 + 2^{ - h} \log ^{(h)} N))$ processors, for any h, $h = 1,2, \ldots ,\log ^ * N$, under the PRAM arithmetic models, provided that $O(\log m)$ steps and m processors suffice to perform discrete Fourier transforms on m points and that $\log ^{(0)} N = N$, $\log ^{(h)} N = \log _2 \log ^{(h - 1)} N$, $h = 1, \ldots ,\log ^ * N$, $\log ^ * N = \max \{ {h:\log ^{(h)} N > 0} \}$. The same estimates apply to some other computations, such as the division with a remainder of two polynomials of degrees $O(N)$ and the inversion of an $N \times N$ triangular Toeplitz matrix. This improves the known estimates of Reif–Tate and Georgiev. The presented techniques are extended to parallel implementation of other recursive processes, such as the evaluation modulo $x^N $ of the mth root $p(x)^{{1 / m}} $ of $p(x)$ (for any fixed natural m), for which we need $O(\log N\log \log N)$ timesteps and $O({N / {\log \log N}})$ processors. The paper demonstrates some new techniques of supereffective slowdown of parallel algebraic computations combined with the technique of stream contraction.

The authors compute the first N coefficients of the reciprocal r(x) of a given polynomial p(x), (r(x)p(x)=1 mod x/sup N/, p(0) not=0), by using, under the PRAM arithmetic models, O(h log N) time-steps and O((N/h)(1+2/sup -h/log/sup (h)/ N)) processors, for any h, h=1,2, . . .,log/sup */ N, provided that O(logm) steps and m processors suffice to perform DFT on m points and that log/sup (0)/ N=N, log/sup (h)/ N=log/sub 2/log/sup (h-1)/N, h=1, . . .,log/sup */N, log/sup */N=max(h:log/sup (h)/N>0). The same complexity estimates apply to some other computations, such as the division with a remainder of two polynomials of degrees O(N) and the inversion of an N*N triangular Toeplitz matrix. They also show how to extend the techniques to parallel implementation of other recursive processes, such as the evaluation modulo x/sup N/ of the m-th root, p(x)/sup 1/m/, of p(x) (for any fixed natural m), for which we need O(log N log log N) time-steps and O(N/log log N) processors. The paper demonstrates some new techniques of supereffective slowdown of parallel algebraic computations, which they combine with a technique of stream contraction.>

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.

Let lg stand for log2, lg(0)n = n, lg(h)n = lg lg(h-1)n, h = 1, …, lg*n, lg*n = min{h,lg(h)n ≤ 1}. Given natural N, h, 1 ≤ h ≤ lg*N, and polynomial p(x), p(O) ≠ O, we compute r(x) = p(x)-1 mod xN for the cost OA(t, P), t = h lg N, P = (N/h)lg(h)N, under the PRAM arithmetic model, that is, we need O(t) steps and O(P) processors (with t and P as above), provided DFT(m) costs OA(lg m, m). For h = lg* N, the cost bounds turn into OA(lg N lg*N, N/lg*N). The results improve [G] and apply to various related computations [BP].

We introduce a new preconditioner for solving a symmetric Toeplitz system of equations by the conjugate gradient method.This choice leads to an algorithm which is particularly suitable for parallel computations and, compared to the circulant preconditioner of [C33, has a better asymptotic convergence rate and a lower arithmetic cost per iteration.

Let $\mathcal{B}_{n,h,k} $ be the class of $n \times n$ band Toeplitz matrices $A = (a_{i,j} )$ such that $a_{i,j} = 0$ if $i - j \geqq k$ or $j - i \geqq h$, $k \leqq h$ and $\mathcal{S}_{n,k} $ the subclass of $\mathcal{B}_{n,k,k} $ made up by symmetric matrices. We show that ${\operatorname{rk}}_{\bf F} (\mathcal{B}_{n,h,k} ) = n + h - 1$ if the field ${\bf F}$ contains a primitive $(n - 1 + h)$th root of unity, ${\operatorname{brk}}_{\bf F} (\mathcal{B}_{n,h,k} ) = n + k - 1,{\operatorname{rk}}_{\bf R} (\mathcal{S}_{n,k} ) = {\operatorname{brk}}_{\bf R} (\mathcal{S}_{n,k} ) = n + 2\lfloor {{(k - 1)} / 2} \rfloor $ if ${\bf R}$ is the real field and $k \leqq {n / 2}$.

Using the concept of approximate algorithm it is shown that $6\log n + 6$ parallel steps and $2n$ processors suffice to approximate, with any precision, the solution of a linear system with an $n \times n$ triangular Toeplitz matrix A. Moreover, $7\log n + 7$ steps are sufficient for an exact computation, whereas the number of processors is increased to $( \frac{5}{2} )n^2 $. If A is also banded and k is its bandwidth, the number of processors is reduced to $( \frac{5}{2} )n(k + 1)$. Two applications are shown. It is proved that if B is any matrix belonging to the algebra generated over the complex field by a given $n \times n$ matrix, then the system $Bx = b$ can be solved with no more than $9\log n + 4$ steps with $O(n^2 )$ processors. It is proved that, given a Toeplitz matrix $A = (a_{i,j} )$ such that $a_{i,j} = 0$ if $i - j > k$ or $j - i > h$, $a_{k,1} \ne 0$, then $13\log n + O(\log ^2 k)$ steps and $\max ( (\frac{5}{2} )n(k + h), n(n + 1)/ 2 )$ processors are sufficient to solve the system $Ax = b$. Such algorithms work under the sole condition $\det A \ne 0$.

A set of bilinear forms can be evaluated with a multiplicative complexity lower than the rank of the associated tensor by allowing an arbitrarily small error. A topological interpretation of this fact is presented together with the error analysis. A complexity measure is introduced which takes into account the numerical stability of algorithms. Relations are established between the complexities of exact and approximate algorithms.