Gaussian Elimination is not Optimal.
General theory of direct methods for solving systems of equations with band matrices
A unified approach to the theory and construction of direct methods is presented. The approach is based on the idea of the transfer of conditions. In examples it is shown how to obtain a particular method from the general algorithm.
Generalizations of Nekrasov matrices and applications
In this paper we present a nonsingularity result which is a generalization of Nekrasov property by using two different permutations of the index set. The main motivation comes from the following observation: matrices that are Nekrasov matrices up to the same permutations of rows and columns, are nonsingular. But, testing all the permutations of the index set for the given matrix is too expensive. So, in some cases, our new nonsingularity criterion allows us to use the results already calculated...