Fast parallel computation of the polynomial shift

Author

Zima, Eugene V.

Author_Institution

Dept. of Comput. Math. & Cybern., Moscow State Univ., Russia

fYear

1997

fDate

1-5 Apr 1997

Firstpage

402

Lastpage

406

Abstract

Given an n-degree polynomial f(x) over an arbitrary ring, the shift of f(x) by c is the operation which computes the coefficients of the polynomial f(x+c). In this paper, we consider the case when the shift by the given constant c has to be performed several times (repeatedly). We propose a parallel algorithm that is suited to an SIMD architecture to perform the shift in O(1) time if we have O(n²) processor elements available. The proposed algorithm is easy to generalize to multivariate polynomial shifts. The possibility of applying this algorithm to polynomials with coefficients from non-commutative rings is discussed, as well as the bit-wise complexity of the algorithm

Keywords

computational complexity; iterative methods; mathematical operators; mathematics computing; parallel algorithms; parallel architectures; polynomials; SIMD architecture; bit-wise complexity; coefficient computation; fast parallel computation; multivariate polynomial shifts; noncommutative rings; parallel algorithm; processor elements; repeated operation; time complexity; Concurrent computing; Cybernetics; Finite difference methods; Mathematics; Parallel algorithms; Polynomials;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1997. Proceedings., 11th International

Conference_Location

Genva

ISSN

1063-7133

Print_ISBN

0-8186-7793-7

Type

conf

DOI

10.1109/IPPS.1997.580933

Filename

580933