A New Matrix Truncation Method for Improving Approximate Factorization Preconditioners

ABSTRACT In this experimental work, we present a general framework based on the Bregman log determinant divergence for preconditioning Hermitian positive definite linear systems. We explore this divergence as a measure of discrepancy between a preconditioner and a matrix. Given an approximate factorization of a given matrix, the proposed framework informs the construction of a low‐rank approximation of the typically indefinite factorization error. The resulting preconditioner is therefore a sum of a Hermitian positive definite matrix given by an approximate factorization plus a low‐rank matrix. Notably, the low‐rank term is not generally obtained as a truncated singular value decomposition (TSVD). This framework leads to a new truncation where principal directions are not based on the magnitude of the singular values, and we prove that such truncations are minimizers of the aforementioned divergence. We present several numerical examples showing that the proposed preconditioner can reduce the number of PCG iterations compared to a preconditioner constructed using a TSVD for the same rank. We also propose a heuristic to approximate the proposed preconditioner in the case where exact truncations cannot be computed explicitly (e.g., in a large‐scale setting) and demonstrate its effectiveness over TSVD‐based approaches.