Kriging and Spatial Design Accelerated by Orders of Magnitude: Combining Low-Rank Covariance Approximations with FFT-Techniques

W. Nowak*, A. Litvinenko

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Computational power poses heavy limitations to the achievable problem size for Kriging. In separate research lines, Kriging algorithms based on FFT, the separability of certain covariance functions, and low-rank representations of covariance functions have been investigated, all three leading to drastic speedup factors. The current study combines these ideas, and so combines the individual speedup factors of all ideas. This way, we reduce the mathematics behind Kriging to a computational complexity of only O(dL*Log L*), when L* is the number of points along the longest edge of the involved lattice of estimation points, and d is the physical dimensionality of the lattice. For separable (factorized) covariance functions, the results are exact, and nonseparable covariance functions can be approximated well through sums of separable components. Only outputting the final estimate as an explicit map causes computational costs of O(n), where n is the number of estimation points. In illustrative numerical test cases, we achieve speedup factors up to 108 (eight orders of magnitude), and we can treat problem sizes of up to 15 trillion and two quadrillion estimation points for Kriging and spatial design, respectively, within seconds on a contemporary desktop computer. The current study assumes second-order stationarity and simple Kriging on a regular, equispaced lattice, without working with restricted neighborhoods. Extensions to many other cases are straightforward.

Original languageEnglish (US)
Pages (from-to)411-435
Number of pages25
JournalMathematical Geosciences
Issue number4
StatePublished - May 2013
Externally publishedYes


  • Efficient geostatistical estimation
  • Geostatistical optimal design
  • Low-rank tensor approximation
  • Spectral methods

ASJC Scopus subject areas

  • Mathematics (miscellaneous)
  • General Earth and Planetary Sciences


Dive into the research topics of 'Kriging and Spatial Design Accelerated by Orders of Magnitude: Combining Low-Rank Covariance Approximations with FFT-Techniques'. Together they form a unique fingerprint.

Cite this