  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 Nystr\"om'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 Nystr\"om--Schur two-level
preconditioner.
