Symbolic Factorization for Sparse Gaussian Elimination with Partial Pivoting
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.
- Sparse Partial Pivoting in Time Proportional to Arithmetic Operations
- Parallel sparse Gaussian elimination with partial pivoting
- Symbolic and Exact Structure Prediction for Sparse Gaussian Elimination with Partial Pivoting
- An Implementation of Gaussian Elimination with Partial Pivoting for Sparse Systems
- Improved Symbolic and Numerical Factorization Algorithms for Unsymmetric Sparse Matrices
- Predicting the structure of sparse orthogonal factors
- Practical quasi-Newton methods for solving nonlinear systems
- An extension of the theory of secant preconditioners
- Fraction free Gaussian elimination for sparse matrices
- Sparse Gaussian Elimination Modulo p: An Update
- Combinatorial Aspects in Sparse Elimination Methods
- Symbolic and Exact Structure Prediction for Sparse Gaussian Elimination with Partial Pivoting
- An Implementation of Gaussian Elimination with Partial Pivoting for Sparse Systems
- General Sparse Elimination Requires No Permanent Integer Storage
- A Data Structure for Sparse QR and LU Factorizations
- Sparse Partial Pivoting in Time Proportional to Arithmetic Operations
- On the Complexity of Sparse QR and LU Factorization of Finite-Element Matrices
- The column-updating method for solving nonlinear equations in Hilbert space
- An Approximate Probabilistic Model for Structured Gaussian Elimination
- scientific article; zbMATH DE number 554767 (Why is no real title available?)
- Solving nonlinear systems of equations by means of quasi-neston methods with a nonmonotone stratgy∗
- scientific article; zbMATH DE number 1163753 (Why is no real title available?)
- Solving mixed sparse-dense linear least-squares problems by preconditioned iterative methods
- Exploiting Structural Symmetry in a Sparse Partial Pivoting Code
- A survey of direct methods for sparse linear systems
- Mixed and componentwise condition numbers for matrix decompositions
- Computing row and column counts for sparse QR and LU factorization
- Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods
- Parallel sparse Gaussian elimination with partial pivoting
- On the row merge tree for sparse LU factorization with partial pivoting
This page was built for publication: Symbolic Factorization for Sparse Gaussian Elimination with Partial Pivoting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3769846)