Accessibility navigation

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

Al Daas, H., Rees, T. and Scott, J. ORCID: (2021) Two-level Nystrom-Schur preconditioner for sparse symmetric positive definite matrices. SIAM Journal on Scientific Computing, 43 (6). A3837-A3861. ISSN 1095-7197

Text - Accepted Version
· Please see our End User Agreement before downloading.


It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1137/21M139548X


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
Divisions:Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
ID Code:99495
Publisher:Society for Industrial and Applied Mathematics


Downloads per month over past year

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation