Advantages for solving linear systems in an asynchronous environment

摘要

In this paper we present two efficient algorithms for the parallel solution of n × n dense linear algebraic systems of equations on an asynchronous multiprocessor computer (MIMD) employing a feasible number of p processors (2 ⩽ p ⩽ O(n)). The first algorithm transforms the serial Gauss-Jordan (GJ) method to parallel form and its execution is carried out by producing a schedule on ⌈12n⌉ processors. Next, the recently developed WZ algorithm [2] is treated similarly and is shown to exhibit a superior efficiency by employing ⌈14n⌉ processors.