Computing max{a1+ b1, a2+ b2, ... ,an+ bn} trivially takes n additions. We show that if we are given the ranking for the a's and the b's separately, then an algorithm exists which will compute the maximum in ≅2n additions on the average. This can be generalized to yield an efficient algorithm to compute max{h(a1,b1), h(a2,b2),..., h(an, bn)} where h(x,y) is monotone increasing in x and y. Another generalization shows an efficient way of computing the maximum norm of a difference between two vectors. Applications are shown in pattern classification and computational geometry.

An MIMD-type parallel-processing system was introduced recently. Using an extended PL/I notation, algorithms for the Gauss-Seidel method and for back substitution are written for this system. Block execution is shown to result in higher speedups.

A parallel processor system and its mode of operation are described. A notation for writing programs on it is introduced. Methods for iterative solution of a set of linear equations are then discussed. The well-known algorithms of Jacobi and Gauss–Seidel are parallelized despite the apparent inherent sequentiality of the latter. New, parallel methods for the iterative solution of linear equations are introduced and their convergence is discussed. A measure of speedup is computed for all methods. It shows that in most cases the algorithms developed in the paper may be efficiently executed on a parallel processor system.