Residual elimination algorithm for solving linear equations and application for sparse systems

A new direct algorithm for solving linear system of equations will be presented. Short theoretical background and analysis of the proposed method will be given. We formulate an optimized version of the proposed algorithm, which also works for sparse matrices. The complexity of the suggested algorithm for full matrix systems is n 3 /3 + O(n 2 ) where n is the dimension of the problem. The numerical experiments show that some versions of the residual elimination algorithm can be competitive with the Gaussian elimination both in complexity and precision. Moreover the sparse linear solver based on this algorithm has some advantages in parallel environment.