A parallel computer (PC) with fixed communication network is called fair if the degree of this network is bounded, otherwise it is called unfair. In a PC with predictable communication each processor can precompute the addresses of the processors it wants to communicate with in the next t steps in $O(t)$ steps. For an arbitrary $\varepsilon > 0$ we define fair PC’s M and $M'$ with $O(n^{1 + \varepsilon } )$ processors each. $M(M')$ can simulate each unfair PC with predictable communication and $O(\log (n))$ storage locations per processor (each fair PC) with n processors with constant time loss. $M'$ improves a result from [Acts Informatics, 19 (1983), pp. 269–296] where a time loss of $O(\log \log (n))$ was achieved. Assuming some reasonable properties of simulations we finally prove a lower bound $\Omega (\log (n))$ for the time loss of a fair PC which can simulate each unfair PC. Applying fast sorting or packet switching algorithms (Proc.15th Annual ACM Symposiums on Theory of Computing, Boston, 1983, pp. 1–9; 10–16; Proc. ACM Symposiums on Principles of Distributed Computing, Ottawa, 1982) one sees easily that this bound is asymptotically tight.

In this work we review the present status of numerical methods for partial differential equations on vector and parallel computers. A discussion of the relevant aspects of these computers and a brief review of their development is included, with particular attention paid to those characteristics that influence algorithm selection. Both direct and iterative methods are given for elliptic equations as well as explicit and implicit methods for initial-boundary value problems. The intent is to point out attractive methods as well as areas where this class of computer architecture cannot be fully utilized because of either hardware restrictions or the lack of adequate algorithms. A brief discussion of application areas utilizing these computers is included.