A new algorithm is presented to improve by a factor of log m the estimates for both parallel and sequential time complexity of division with remainder of two integer polynomials. Under the parallel model, this means B...
详细信息
A new algorithm is presented to improve by a factor of log m the estimates for both parallel and sequential time complexity of division with remainder of two integer polynomials. Under the parallel model, this means Boolean logarithmic time, which is asymptotically optimum. The algorithm exploits the reduction of the problem to integer division; the polynomial remainder and quotient are recovered from integer remainder and quotient via binary segmentation.
作者：
Murphy, Brian J.CUNY
CUNY Herbert H Lehman Coll Dept Math & Comp Sci Bronx NY 10468 USA
Computing the reciprocal of a polynomial in z modulo a power z(n) is well known to be closely linked to polynomial division and equivalent to the inversion of an n x n triangulartoeplitzmatrix. The degree k of the p...
详细信息
ISBN:
(纸本)9783642235672;9783642235689
Computing the reciprocal of a polynomial in z modulo a power z(n) is well known to be closely linked to polynomial division and equivalent to the inversion of an n x n triangulartoeplitzmatrix. The degree k of the polynomial is precisely the bandwidth of the matrix, and so the matrix is banded iff k << n. We employ the above equivalence and some elementary but novel and nontrivial techniques to obtain minor yet noticeable acceleration of the solution of the cited fundamental computational problems.
暂无评论