Parallel Computing and Its Impact

Today the factors of ten can be replaced by factors of one hundred or even more. Given the intricate connection between algorithms and the theory upon which they are based, it is clear that huge factors can emerge when the same quantity is calculated by different methods just because of the suitability of the methods to parallel computation. It is clearly of central importance to establish 

It is well known that the direct evaluation of this expression 

Let us analysis the algebraic complexity of these schemes. The evaluation of the polynomial term by term requires (2n — 1) multiplications and n additions, giving a total of (3n— 1) operations, whereas the Horner scheme involves n multiplications and n additions, a total of 2n operations. 

Now consider the algebraic complexity of algorithms suitable for concurrent computation for this problem. As it is presented above, the Horner scheme for the evaluation of polynomials is not suitable for parallel computation since it involves the computation of n sums and n products in strictly sequential order. Can we modify the Horner algorithm to partition the computation between two or more processors Let us, for the moment, restrict our attention to the case of two processors and write the polynomial in the form 

We can then evaluate the first parenthesis on the first processor 

---