Premium
Wilkinson's inertia‐revealing factorization and its application to sparse matrices
Author(s) -
Druinsky Alex,
Carlebach Eyal,
Toledo Sivan
Publication year - 2018
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2130
Subject(s) - tridiagonal matrix , incomplete lu factorization , factorization , incomplete cholesky factorization , mathematics , sparse matrix , matrix decomposition , matrix (chemical analysis) , inertia , sylvester's law of inertia , bounded function , sparse approximation , symmetric matrix , algebra over a field , algorithm , pure mathematics , mathematical analysis , computational chemistry , eigenvalues and eigenvectors , physics , chemistry , materials science , quantum mechanics , composite material , classical mechanics , gaussian
Summary We propose a new inertia‐revealing factorization for sparse symmetric matrices. The factorization scheme and the method for extracting the inertia from it were proposed in the 1960s for dense, banded, or tridiagonal matrices, but they have been abandoned in favor of faster methods. We show that this scheme can be applied to any sparse symmetric matrix and that the fill in the factorization is bounded by the fill in the sparse Q R factorization of the same matrix (but is usually much smaller). We describe our serial proof‐of‐concept implementation and present experimental results, studying the method's numerical stability and performance.