FAST PARALLEL COMPUTATION OF THE POLYNOMIAL REMAINDER SEQUENCE VIA BEZOUT AND HANKEL-MATRICES

被引：18

作者：

BINI, D ^{[1
]}

GEMIGNANI, L ^{[1
]}

机构：

[1] UNIV PARMA,DIPARTIMENTO MATEMAT,I-43100 PARMA,ITALY

来源：

SIAM JOURNAL ON COMPUTING | 1995年 / 24卷 / 01期

关键词：

EUCLIDEAN SCHEME; GREATEST COMMON DIVISOR; HANKEL AND BEZOUT MATRICES; COMPUTATIONAL COMPLEXITY; PARALLEL ALGORITHMS;

D O I：

10.1137/S0097539791201903

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

If u(x) and upsilon(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 upsilon(x) can be computed by using O (log(3) n) parallel arithmetic steps and n(2)/log n processors over any held of characteristic O 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 upsilon(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.

引用

页码：63 / 77

页数：15

共 25 条

[11] HANKEL AND LOEWNER MATRICES [J].