Optimal Partitioning and Redundancy Removal in Computing Partial Sums

Two novel algorithms for simultaneous computation of a large number of partial sums are introduced, their performance assessed, and architectures for their implementation suggested. The direct computation of D operations are replaced by O(D/log D). The new approach is based on a new concept of optimal partitioning and redundancy removal in arithmetic intensive, high throughput computing that is expected to be the basis of a new class of algorithms which represent a departure from brute force parallel computation where inherent redundancy is not detected or removed.