A Computation Model of Parallel Solution of Linear Equations

Abstract

The solution process of Ax = b is modeled by an acyclic directed graph in which the nodes represent the arithmetic operations applied to the elements of A, and the arcs represent the precedence relations that exist among the operations in the solution process. Operations that can-be done in parallel are identified in the model and the absolute minimum completion time and lower bounds on theminimum number of processors required to solve the equations in minimal time can be found from it. Properties of the model are derived. Hu's level scheduling strategy is applied to examples of sparse matrix equations with surprisingly good results. Speed-up using parallel processing is found to be proportional to the number of processors when it is 10–20 percent of the order of A. Copyright © 1980 by The Institute of Electrical and Electronics Engineers, Inc.