  The spectrum of a kernel matrix significantly depends on the parameter values
of the kernel function used to define the kernel matrix. This makes it
challenging to design a preconditioner for a regularized kernel matrix that is
robust across different parameter values. This paper proposes the Adaptive
Factorized Nystr\"om (AFN) preconditioner. The preconditioner is designed for
the case where the rank k of the Nystr\"om approximation is large, i.e., for
kernel function parameters that lead to kernel matrices with eigenvalues that
decay slowly. AFN deliberately chooses a well-conditioned submatrix to solve
with and corrects a Nystr\"om approximation with a factorized sparse
approximate matrix inverse. This makes AFN efficient for kernel matrices with
large numerical ranks. AFN also adaptively chooses the size of this submatrix
to balance accuracy and cost.
