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

W. Nowak*, Alexander Litvinenko

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

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
Volume45
Issue number4
DOIs
StatePublished - May 1 2013

Keywords

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

ASJC Scopus subject areas

  • Mathematics (miscellaneous)
  • Earth and Planetary Sciences(all)

Fingerprint

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