Symbolic Factorization for Sparse Gaussian Elimination with Partial Pivoting (Q3769846)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4028727
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Symbolic Factorization for Sparse Gaussian Elimination with Partial Pivoting |
scientific article; zbMATH DE number 4028727 |
Statements
Symbolic Factorization for Sparse Gaussian Elimination with Partial Pivoting (English)
0 references
1987
0 references
sparse matrix algorithms
0 references
symbolic factorization
0 references
large sparse nonsingular system
0 references
Gaussian elimination with partial pivoting
0 references
0.8826200366020203
0 references
0.8636940717697144
0 references
0.8474366664886475
0 references
0.840161144733429
0 references
0.8184813261032104
0 references
From author's summary: Let \(Ax=b\) be a large sparse nonsingular system of linear equations to be solved using Gaussian elimination with partial pivoting. The factorization obtained can be expressed in the form \(A=P_ 1M_ 1P_ 2M_ 2...P_{n-1}M_{n-1}U\), where \(P_ k\) is an elementary permutation matrix reflecting the row interchange that occurs at step k during the factorization, \(M_ k\) is a unit lower triangular matrix whose kth column contains the multipliers, and U is an upper triangular matrix. Consider the kth step of the elimination. Suppose we replace the structure of row k of the partially reduced matrix by the union of the structures of those rows which are candidates for the pivot row and then perform symbolically Gaussian elimination without partial pivoting. Assume that this is done at each step k, and let \(\bar L\) and \(\bar U\) denote the resulting lower and upper triangular matrices, respectively. Then the structures of \(\bar L\) and \(\bar U,\) respectively, contain the structures \(\sum^{n-1}_{k=1}M_ k\) and U. This paper describes an algorithm which determines the structures of \(\bar L\) and \(\bar U,\) and sets up an efficient data structure for them. The algorithm is shown to execute in time bounded by \(| \bar L| +| \bar U|\), where \(| M|\) denotes the number of nonzeros in the matrix M.
0 references