We prove that any multivariate polynomial P of degree d that can be computed with $C(P)$ multiplications-divisions can be computed in $O(\log d \cdot \log C(P))$ parallel steps and $O(\log d)$ parallel multiplicative steps.

We prove that any multivariate polynomial P of degree d that can be computed with C(P) multiplications-divisions can be computed in O(log d.log C(P)) parallel steps and O(log d) parallel multiplicative steps.

In this paper we show that the computation of the determinant requires an exponential number of multiplications if the commutativity of indeterminates is not allowed. The determinant can be computed in polynomial time with the commutation of indeterminates. Hence the use of commutativity can reduce a computation of exponential complexity to a computation of polynomial complexity.

The problem oI evaluatmgxn defined by the linear recurrence x, = x~-lb, + a,+l, t >-1, x0 = al, or equivalently evaluating the HorneT expression ( '(alb~ + a.o)bz + + a,,)b,, + a,,+~ is considered It is shown that by using an rdeahzed k-processor parallel computer the speedup for the problem is at most ~rk + rather than k The bound is essentially sharp

In this paper we show that the minimum number of comparisons necessary for the computation of the kth element of a totally ordered set of size n, $V_k (n)$, is bounded below by $n - k + (k - 1)\lceil \log _2 (n/(k - 1)) \rceil $. For $3 < k < n/4$, this bound is an improvement on the best lower bound presently known. A new algorithm which yields an upper bound that is better than the currently known bound for a large range of values of n will also be presented.

The concept of computers such as C.mmp and ILLIAC IV is to achieve computational speed-up by performing several operations simultaneously with parallel processors. This type of computer organization is referred to as a parallel computer. In this paper, we prove upper bounds on speed-ups achievable by parallel computers for a particular problem, the solution of first order linear recurrences. We consider this problem because it is important in practice and also because it is simply stated so that we might obtain some insight into the nature of parallel computation by studying it.

In this paper, we present an algorithm which computes the optimal pattern for merging n equal size sorted sequences stored on a disk, in time O(log n) and constant space. The best previously known algorithm for solving this problem (Knuth [4], Schlumberger-Vuillemin [5]) takes time O(n2) and space O(n).