The actual complexity of parallel evaluation of low degree polynomials (Q582800)

The authors consider several sequential and parallel algorithms for the evaluation of polynomials of low degree with particular emphasis on those that are used frequently in computer graphics. A complete accounting of computation times for the speedup and efficiency of these algorithms is reported. The results are compared to standard estimates of these quantities for single and multiprocessor using classical complexity theory. A simulator which is configurable to several parallel architecture is used to provide validation of the results obtained.