A new folding gaussian elimination algorithm for general linear systems

Abstract

Motivated by the folding algorithm of Evans and Hatzopoulos [6] (see also [1]) for the solution of certain banded systems of linear equations, we describe a “new” folding Gaussian elimination algorithm for linear systems Ax = d with a full general coefficient matrix . We introduce a series of transformations W^m which simultaneously eliminate the elements and . For n even, the transformed system has a coefficient matrix with two half-size triangular subsystems uncoupled, obviating the need to solve 2×2 core subsystems as in [6]. The new algorithm has an arithmetical operations count of which is consistent with of the unidirectional algorithm; thus, it could possibly attain a speed up of 1.6 if implemented on a dual processor machine. The present algorithm can be adapted for banded linear systems; we consider its adaptation for tridiagonal linear systems where it exhibits a near perfect speed up over Thomas' algorithm.

Keywords:

• Linear systems
• general coefficient matrix
• folding Gaussian elimination algorithm
• parallel implementation
• consistency
• speed up
• efficiency
• tridiagonal linear systems

C.R. Categories:

• G.1.3
• G.1.0