A generalized Sylvester identity and fraction-free random Gaussian elimination (Q5933502): Difference between revisions
From MaRDI portal
Latest revision as of 17:18, 3 June 2024
scientific article; zbMATH DE number 1599193
Language | Label | Description | Also known as |
---|---|---|---|
English | A generalized Sylvester identity and fraction-free random Gaussian elimination |
scientific article; zbMATH DE number 1599193 |
Statements
A generalized Sylvester identity and fraction-free random Gaussian elimination (English)
0 references
25 February 2002
0 references
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.
0 references
Gaussian elimination
0 references
Sylvester identity
0 references
numerical examples
0 references
random Gaussian elimination
0 references
fraction free algorithm
0 references
simplex method
0 references
linear programming
0 references
sparse Cholesky factorization
0 references
sparse matrix factorization
0 references
multifrontal method
0 references
performance
0 references