A generalized Sylvester identity and fraction-free random Gaussian elimination (Q5933502): Difference between revisions

It is well known that Sylvester's identity can be used to prove that certain Gaussian elimination algorithms are fraction free. In this paper, Sylvester's identity is generalized to prove that certain random Gaussian elimination algorithms are fraction free. It is shown how the fraction free algorithm can be used in the simplex method of solving linear programming problems. Several numerical examples illustrating the proposed algorithms are given. The problem of sparse Cholesky factorization is investigated. Since sparse matrix factorization can be used to make use of a memory hierarchy, extremely large sparse linear systems can be solved in a reasonable time on very inexpensive computer systems. Several methods for performing Cholesky factorizations of arbitrarily large problems, constrained only by the size of the disk, are described. The first is a simple extension of the multi-frontal method to handle the case where the multi-frontal stack does not fit in core. The second and third are panel-oriented, left-looking, out-of-core methods. It is found that while the multi-frontal method is extremely effective when its stack fits in core, a left-looking variant is actually more effective when the multi-frontal stack does not fit. Experimental results for some very large matrices from structural analysis, computational fluid dynamics, and linear programming are presented. It is pointed out that one of the best methods gives the best performance of an in core method by using only a fraction of the memory.