The coefcient matrix is perturbed whenever numerically acceptable and pivots cannot be found within the diagonal block. It uses no more storage than a sparse Cholesky factorization of a positive denite matrix with the same sparsity structure due to restricting the pivoting to interchanges within the diagonal block associated to a single supernode. It is supplemented by pivot perturbation techniques. The rst al- gorithm uses SupernodenBunchnKaufman (SBK) pivoting and dynamically selects and pivots. On the other hand, the imposed pivoting restrictions can be reduced in several steps by taking the matching permutation into account.
These methods restrict the pivoting search, to stay as long as possible within predened data structures for efcient Level-3 BLAS factorization and parallelization. We will present three new variations of a direct factorization scheme to tackle the is- sue of indeniteness in sparse symmetric linear systems. is a ll reducing reordering which honors the structure of. is a reordering that is based on a symmetric weighted matching of the matrix, and tries to move the largest off-diagonal elements directly alongside the diagonal in order to form good initial or diagonal block pivots. where is a diagonal matrix with and pivot blocks, is a sparse lower triangu- lar matrix, and is a symmetric indenite diagonal matrix that reects small half-machine precision perturbations, which might be necessary to tackle the problem of tiny pivots. Numerical experiments validate these conclusions. These techniques can be seen as a complement to the alternative idea of using more complete pivoting techniques during the numerical factorization. We will also show that symmetric maximum-weighted matching strategies add an additional level of reliability to SBK. We demonstrate the effectiveness and the numerical accuracy of this algorithm and also show that a high performance implementa- tion is feasible. As opposed to many existing pivoting methods, our SupernodenBunchnKaufman (SBK) pivoting method dy- namically selects and pivots and may be supplemented by pivot perturbation techniques. Experiments demonstrate that a wide set of unsymmetric linear systems can be solved and high performance is consistently achieved for large sparse unsymmetric matrices from real world applications.read more read lessĪbstract: This paper discusses new pivoting factorization methods for solving sparse symmetric indenite sys- tems. These algorithms have been integrated into the recent unsymmetric version of the PARDISO solver. The level-3 BLAS efficiency is retained and an advanced two-level left-right looking scheduling scheme results in good speedup on SMP machines. Complete block diagonal supernode pivoting allows dynamical interchanges of columns and rows during the factorization process. The progress in weighted graph matching algorithms helps to extend these concepts further and unsymmetric prepermutation of rows is used to place large matrix entries on the diagonal. Abstract: Supernode partitioning for unsymmetric matrices together with complete block diagonal supernode pivoting and asynchronous computation can achieve high gigaflop rates for parallel sparse LU factorization on shared memory parallel computers.
0 kommentar(er)
