Fomenko E.
On improving stability of solving systems of linear equations with symmetric indefinite
ON IMPROVING STABILITY OF SOLVING SYSTEMS OF LINEAR EQUATIONS WITH SYMMETRIC INDEFINITE SPARSE MATRICES
E. M. Fomenko
Intel Corporation
evarist.m.fomenko@intel.com
Solving systems of linear equations with sparse symmetric positive definite matrices using direct methods usually consists of three main stages: symbolic LLT factorization of the initial matrix, numeric factorization, and forward and backward substitution. This approach utilizes the sparsity of the matrix and has good scalability and accuracy properties. For inde nite matrices, LDLT decomposition is used instead of LLT . Unfortunately, in this case stability issues can arise due to necessity of division by zero or a small value. There are two main approaches that avoid these stability issues: perform a small perturbation to replace any zero value with some non-zero value or perform factorization with full or partial pivoting. Both approaches have advantages and disadvantages: the rst approach is fast but might produce an incorrect result, while the second one is accurate but degrades performance signi cantly.
This paper introduces a new approach that on the one hand preserves the structure of the matrix L obtained by symbolic factorization, which avoids pivots and thus has good performance and on the other hand allows an accurate solution by dynamically enlarging the size of the initial system.
Error estimation of the proposed algorithm and numeric experiments are presented.
To reports list