Two-level Nystrom-Schur preconditioner for sparse symmetric positive definite matrices

Al Daas, H., Rees, T. and Scott, J. ORCID: https://orcid.org/0000-0003-2130-1091 (2021) Two-level Nystrom-Schur preconditioner for sparse symmetric positive definite matrices. SIAM Journal on Scientific Computing, 43 (6). A3837-A3861. ISSN 1095-7197 doi: 10.1137/21M139548X

Abstract/Summary

Randomized methods are becoming increasingly popular in numerical linear algebra. However, few attempts have been made to use them in developing preconditioners. Our interest lies in solving large-scale sparse symmetric positive definite linear systems of equations where the system matrix is preordered to doubly bordered block diagonal form (for example, using a nested dissection ordering). We investigate the use of randomized methods to construct high quality preconditioners. In particular, we propose a new and efficient approach that employs Nystrom's method for computing low rank approximations to develop robust algebraic two-level preconditioners. Construction of the new preconditioners involves iteratively solving a smaller but denser symmetric positive definite Schur complement system with multiple right-hand sides. Numerical experiments on problems coming from a range of application areas demonstrate that this inner system can be solved cheaply using block conjugate gradients and that using a large convergence tolerance to limit the cost does not adversely affect the quality of the resulting Nystrm-Schur two-level preconditioner.

Item Type	Article
URI	https://reading-clone.eprints-hosting.org/id/eprint/99495
Identification Number/DOI	10.1137/21M139548X
Refereed	Yes
Divisions	Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
Publisher	Society for Industrial and Applied Mathematics
Download/View statistics	View download statistics for this item