We develop a multi-level restricted maximum likelihood method for
  estimating the covariance function parameters and computing the best
  linear unbiased predictor (BLUP). Our approach produces a new set of
  multi-level contrasts where the deterministic parameters of the
  model is filtered out thus enabling the estimation of the covariance
  parameters to be decoupled from the deterministic
  component. Moreover, the multi-level covariance matrix of the
  contrasts exhibit fast decay that is dependent on the smoothness of
  the covariance function.  Due to the fast decay of the multi-level
  covariance matrix coefficients only a small set are computed with a
  distance criterion. We demonstrate our approach on problems of up
  512,000 observations with a Matern covariance function.