Home > Publications > Refereed Journals > Kriging and Spatial Design Accelerated by Orders of Magnitude: Combining Low-Rank Covariance Approximations with FFT-Techniques
Publications

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

Bibliography:

Nowak, W., Litvinenko, A. Kriging and Spatial Design Accelerated by Orders of Magnitude: Combining Low-Rank Covariance Approximations with FFT-Techniques, Mathematical Geosciences, Vol. 45, Num. 4, pp 411--435, Springer 2013.​​​

Authors:

Nowak, W., Litvinenko, A.

Keywords:

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

Year:

2013

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 K​riging to a computational complexity of only 
O(dL* log L*)
, where 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.​

ISSN:

Print ISSN 1874-8961, Online ISSN 1874-8953
http://link.springer.com/article/10.1007/s11004-013-9453-6