lattice (regular grid), one can use the fast Fourier transform (FFT), which takes time $O(n\log
n)$ \[@toeplitzbook\]. Even when the grid is partial (with occluded observations), this idea can still be applied. On the other hand, for nongridded observations, exact multiplication generally requires $O(n^2)$ operations. However, one can use a combination of direct summations for close-by points and multipole expansions of the covariance kernel for faraway points to compute the matrix–vector products in $O(n\log n)$, even $O(n)$, time \[@treecode [@fmm]\]. In the case of Matérn-type Gaussian processes and in the context of solving the stochastic approximation (\[ascore\]), such fast multipole approximations were presented by @anitescu2012mfa. Note that the total computational cost of the solver is the cost of each iteration times the number of iterations, the latter being usually much less than $n$.

The number of iterations to achieve a desired accuracy depends on how fast $x^i$ approaches $x^*$, which, from (\[eqncgconverge\]), is in turn affected by the condition number $\kappa$ of $A$. Two techniques can be used to improve convergence. One is to perform preconditioning in order to reduce $\kappa$; this technique will be discussed in the next section. The other is to adopt a block version of the 