STABILITY OF PARALLEL TRIANGULAR SYSTEM SOLVERS

Several parallel algorithms have been proposed for the solution of tri angular systems. The stability of four of them is analysed here: a fan -in algorithm, a block elimination method, a method based on a factori zed power series expansion of the matrix inverse, and a method based o n a divide and conquer matrix inversion technique. New forward error a nd residual bounds are derived, including an improvement on the bounds of Sameh and Brent for the fan-in algorithm. A forward error bound is identified that holds not only for all the methods described here, bu t for any triangular equation solver that does not rely on algebraic c ancellation; among the implications of the bound is that any such meth od is extremely accurate for certain special types of triangular syste ms.