  We present a new algorithm for convex separable quadratic programming (QP)
called Nys-IP-PMM, a regularized interior-point solver that uses low-rank
structure to accelerate solution of the Newton system. The algorithm combines
the interior point proximal method of multipliers (IP-PMM) with the randomized
Nystr\"om preconditioned conjugate gradient method as the inner linear system
solver. Our algorithm is matrix-free: it accesses the input matrices solely
through matrix-vector products, as opposed to methods involving matrix
factorization. It works particularly well for separable QP instances with dense
constraint matrices. We establish convergence of Nys-IP-PMM. Numerical
experiments demonstrate its superior performance in terms of wallclock time
compared to previous matrix-free IPM-based approaches.
