Bidirectional Division-free Gaussian Elimination Algorithm for Solving Linear Equations

摘要

Multiple-chained divisions and/or square root computations result in an unacceptable cumulative roundoff errors in the solution of linear equations. To circumvent this difficulty, algorithms based on division-free and/or square root-free computations have been proposed. In this paper, a new and faster algorithm based on division-free Gaussian Elimination (GE) for solving a system of linear equations is presented. The new algorithm uses the bidirectional elimination principle proposed in. The mapping of the new algorithm on to systolic arrays is discussed and it is shown that the new algorithm is faster than any of the existing algorithms for solving linear equations. Finally, a problem partitioning technique to solve problems of larger size on an array of smaller size is described.