The odd-even permutation and associated unitary transformations for reordering the matrix coefficient A is employed as a means of breaking the strong seriality which is characteristic of closely coupled systems. The nested dissection technique is also reviewed, and the equivalence between reordering A and dissecting its network is established. The effect of transforming A with odd-even permutat~on on its topology and the topology of its Cholesky factors is discussed. This leads to the construction of directed graphs showing the computational steps required for factoring A, their precedence relationships and their sequential and concurrent assignment to the available processors. Expressions for the speed-up and efficiency of using N processors in parallel relative to the sequential use of a single processor are derived from the directed graph. Similar expressions are also derived when the number of available processors is fewer than required.
The continuing need for larger structural models bearing greater analysis details and accuracy has stimulated interest in faster solution algorithms; and even when the model order is small, the speed of the algorithm can be crucial in the success or failure of autonomous systems requiring real-time solutions. For these classes of problems, parallel processing on 'ensemble computers' appears to be a most viable means whereby larger problem orders could be solved orders of magnitude faster.
Computer architectures of the 'ensemble' class have been built and shown to be techno~ogically and economically feasible. Examples include the hypercube (or cosmic cube)', CHIP,2 and FEM.3 In this class of computers, a large number of identical processing elements for processors] each complete with its own private memory and central processing unit are homogeneously interconnected in one, two or more dimensional topology. The key to achieving high speed-up with these computers lies in one's ability to decompose the computational tasks of an algorithm for large order problems into smaller multi-tasks which can be executed simultaneously with a minimum of interprocessor communications or idle time. Thus designing and implementing suitable algorithms for these machines is crucial for their successful use.