TY - JOUR

T1 - Application of FFT-based algorithms for large-scale universal kriging problems

AU - Fritz, Jochen

AU - Neuweiler, Insa

AU - Nowak, Wolfgang

N1 - Funding information: We are indebted to and thank Prof. Pegram at the University of KwaZulu-Natal, South Africa, for his valuable comments on the manuscript, and to the anonymous reviewers for their helpful suggestions. This study was funded in part by the German Research Foundation (DFG) under the grants No. 824/2-2, No. 824/3 and No. 805/1-1 and by the international research training group NUPUS, financed by the German Research Foundation (DFG) (GRK 1398) and the Netherlands Organisation for Scientific Research (NWO) (DN 81-754).

PY - 2009/4/1

Y1 - 2009/4/1

N2 - Looking at kriging problems with huge numbers of estimation points and measurements, computational power and storage capacities often pose heavy limitations to the maximum manageable problem size. In the past, a list of FFT-based algorithms for matrix operations have been developed. They allow extremely fast convolution, superposition and inversion of covariance matrices under certain conditions. If adequately used in kriging problems, these algorithms lead to drastic speedup and reductions in storage requirements without changing the kriging estimator. However, they require second-order stationary covariance functions, estimation on regular grids, and the measurements must also form a regular grid. In this study, we show how to alleviate these rather heavy and many times unrealistic restrictions. Stationarity can be generalized to intrinsicity and beyond, if decomposing kriging problems into the sum of a stationary problem and a formally decoupled regression task. We use universal kriging, because it covers arbitrary forms of unknown drift and all cases of generalized covariance functions. Even more general, we use an extension to uncertain rather than unknown drift coefficients. The sampling locations may now be irregular, but must form a subset of the estimation grid. Finally, we present asymptotically exact but fast approximations to the estimation variance and point out application to conditional simulation, cokriging and sequential kriging. The drastic gain in computational and storage efficiency is demonstrated in test cases. Especially high-resolution and data-rich fields such as rainfall interpolation from radar measurements or seismic or other geophysical inversion can benefit from these improvements.

AB - Looking at kriging problems with huge numbers of estimation points and measurements, computational power and storage capacities often pose heavy limitations to the maximum manageable problem size. In the past, a list of FFT-based algorithms for matrix operations have been developed. They allow extremely fast convolution, superposition and inversion of covariance matrices under certain conditions. If adequately used in kriging problems, these algorithms lead to drastic speedup and reductions in storage requirements without changing the kriging estimator. However, they require second-order stationary covariance functions, estimation on regular grids, and the measurements must also form a regular grid. In this study, we show how to alleviate these rather heavy and many times unrealistic restrictions. Stationarity can be generalized to intrinsicity and beyond, if decomposing kriging problems into the sum of a stationary problem and a formally decoupled regression task. We use universal kriging, because it covers arbitrary forms of unknown drift and all cases of generalized covariance functions. Even more general, we use an extension to uncertain rather than unknown drift coefficients. The sampling locations may now be irregular, but must form a subset of the estimation grid. Finally, we present asymptotically exact but fast approximations to the estimation variance and point out application to conditional simulation, cokriging and sequential kriging. The drastic gain in computational and storage efficiency is demonstrated in test cases. Especially high-resolution and data-rich fields such as rainfall interpolation from radar measurements or seismic or other geophysical inversion can benefit from these improvements.

KW - Efficient geostatistical estimation

KW - Fast Fourier transform

KW - Spectral methods

KW - Superfast Toeplitz solver

UR - http://www.scopus.com/inward/record.url?scp=67649921167&partnerID=8YFLogxK

U2 - 10.1007/s11004-009-9220-x

DO - 10.1007/s11004-009-9220-x

M3 - Article

AN - SCOPUS:67649921167

VL - 41

SP - 509

EP - 533

JO - Mathematical geosciences

JF - Mathematical geosciences

SN - 1874-8961

IS - 5

ER -