Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ababou R, Bagtzoglou AC, Wood EF (1994) On the condition number of covariance matrices in kriging, estimation, and simulation of random fields. Math Geol 26(1):99–133
Barnett S (1990) Matrices methods and applications. Oxford applied mathematics and computing science series. Clarendon, Oxford
Börm S, Grasedyck L, Hackbusch W (2003) Introduction to hierarchical matrices with applications. Eng Anal Bound Elem 27:405–422. doi:10.1016/S0955–7997(02)00152–2
Chan RH, Ng MK (1996) Conjugate gradient methods for Toeplitz systems. SIAM Rev 38(3):427–482
Cirpka OA, Nowak W (2003) Dispersion on kriged hydraulic conductivity fields. Water Resour Res. doi:10.1029/2001WR000598
Cirpka OA, Nowak W (2004) First-order variance of travel time in non-stationary formations. Water Resour Res 40:W03507. doi:10.1029/2003WR002851
Cooley JW, Tukey JW (1965) An algorithm for the machine calculation of complex Fourier series. Math Comput 19:297–301
Davis PJ (1979) Circulant matrices. Pure and applied mathematics. Wiley, New York
Davis MW, Culhane PG (1984) Contouring very large data sets using kriging. In: Verly G (eds) Geostatistics for natural resources characterization, Part 2. Reidel, Dordrecht
Davis MW, Grivet C (1984) Kriging in a global neighborhood. Math Geol 16(3):249–265
Dietrich CR, Newsam GN (1989) A stability analysis of the geostatistical approach to aquifer transmissivity identification. Stoch Hydrol Hydraul 3:293–316
Dietrich CR, Newsam GN (1993) A fast and exact method for multidimensional Gaussian stochastic simulations. Water Resour Res 29(8):2861–2869
Dietrich CR, Newsam GN (1996) A fast and exact method for multidimensional Gaussian stochastic simulations: Extension to realizations conditioned on direct and indirect measurements. Water Resour Res 32(6):1643–1652
Dietrich CR, Newsam GN (1997) Fast and exact simulation of stationary Gaussian processes through circulant embedding of the covariance matrix. SIAM J Sci Comput 18(4):1088–1107
Duijndam AJW, Schonewille MA (1999) Nonuniform fast Fourier transform. Geophysics 64(2):539–551
Dykaar BB, Kitanidis PK (1992) Determination of the effective hydraulic conductivity for heterogeneous porous media using a numerical spectral approach. 1. Method. Water Resour Res 28(4):1155–1166
Fessler JA, Sutton BP (2003) Nonuniform fast Fourier transform using min-max interpolation. IEEE Trans Signal Process 51(2):560–574
Fourmont K (2003) Non-equispaced fast Fourier transforms with applications to tomography. J Fourier Anal Appl 9(5):431–450
Frigo M, Johnson SG (1998) FFTW: An adaptive software architecture for the FFT. In: Proc ICASSP, vol 3. IEEE Press, New York, pp 1381–1384. http://www.fftw.org
Fuentes M (2007) Approximate likelihood for large irregularly spaced spatial data. J Am Stat Assoc 102(477) 321–331. doi:10.1198/016214506000000852
Gallivan K, Thirumalai S, Dooren PV, Vermaut V (1996) High performance algorithms for Toeplitz and block Toeplitz matrices. Linear Algebra Appl 241–243(13):343–388
Golub GH, van Loan CF (1996) Matrix computations, 3rd edn. John Hopkins University Press, Baltimore
Good IJ (1950) On the inversion of circulant matrices. Biometrika 37:185–186
Greengard L, Lee J-Y (2004) Accelerating the nonuniform fast Fourier transform. SIAM Rev 46(3):443–454
Hestenes MR, Stiefel E (1952) Methods of conjugate gradients for solving linear systems. J Res Nat Bur Stand 49:409–436
Kailath T, Sayed AH (1995) Displacement structure: Theory and applications. SIAM Rev 37(3):297–386
Kailath T, Sayed AH (1999) Fast reliable algorithms of matrices with structure. SIAM, Philadelphia
Kitanidis PK (1986) Parameter uncertainty in estimation of spatial functions: Bayesian analysis. Water Resour Res 22(4):499–507
Kitanidis PK (1993) Generalized covariance functions in estimation. Math Geol 25(5):525–540
Kitanidis PK (1995) Quasi-linear geostatistical theory for inversing. Water Resour Res 31(10):2411–2419
Kitanidis PK (1996) Analytical expressions of conditional mean, covariance, and sample functions in geostatistics. Stoch Hydrol Hydraul 12:279–294
Kitanidis PK (1997) Introduction to geostatistics. Cambridge University Press, Cambridge
Kitanidis PK, Vomvoris EG (1983) A geostatistical approach to the inverse problem in groundwater modeling (steady state) and one-dimensional simulations. Water Resour Res 19(3):677–690
Kozintsev B (1999) Computations with Gaussian random fields. PhD thesis, Institute for Systems Research, University of Maryland
Liu QH, Ngyuen N (1998) An accurate algorithm for nonuniform fast Fourier transforms (NUFFT’s). IEEE Microw Guided Wave Lett 8(1):18–20
Müller WG (2007) Collecting spatial data. Optimum design of experiments for random fields, 3rd edn. Springer, Berlin
Newsam GN, Dietrich CR (1994) Bounds on the size of nonnegative definite circulant embeddings of positive definite Toeplitz matrices. IEEE Trans Inf Theory 40(4):1218–1220
Nowak W (2005) Geostatistical methods for the identification of flow and transport parameters in subsurface flow. Ph.D. thesis, Institut für Wasserbau, Universität Stuttgart, http://elib.uni-stuttgart.de/opus/frontdoor.php?source_opus=2275
Nowak W, Cirpka OA (2004) A modified Levenberg–Marquardt algorithm for quasi-linear geostatistical inversing. Adv Water Resour 27(7):737–750
Nowak W, Cirpka OA (2006) Geostatistical inference of conductivity and dispersion coefficients from hydraulic heads and tracer data. Water Resour Res 42:W08416. doi:10.1029/2005WR004832
Nowak W, Tenkleve S, Cirpka OA (2003) Efficient computation of linearized cross-covariance and auto-covariance matrices of interdependent quantities. Math Geol 35(1):53–66
Omre H (1987) Bayesian kriging-merging observations and qualified guesses in kriging. Math Geol 19(1):25–39
Pegram GGS (2004) Spatial interpolation and mapping of rainfall (SIMAR). Data merging for rainfall map production, vol 3. Water Research Commission Report (1153/1/04)
Press WH, Teukolsky BPFSA, Vetterling WT (1992) Numerical recipes: the art of scientific computing, 2nd edn. Cambridge University Press, Cambridge
Pukelsheim F (2006) Optimal design of experiments. Classics in applied mathematics. SIAM, Philadelphia
Rino CL (1970) The inversion of covariance matrices by finite Fourier transforms. IEEE Trans Inf Theory 16:230–232
Schweppe FC (1973) Uncertain dynamic systems. Prentice-Hall, Englewood Cliffs
Shewchuk JR (1994). An introduction to the conjugate gradient method without the agonizing pain. http://www.cs.berkeley.edu/~jrs/
Strang G (1986) A proposal for Toeplitz matrix calculations. Stud Appl Math 74:171–176
Trapp GE (1973) Inverses of circulant matrices and block circulant matrices. Kyungpook Math J 13(1): 11–20
Van Barel M, Heinig G, Kravanja P (2001) A stabilized superfast solver for nonsymmetric Toeplitz systems. SIAM J Matrix Anal A 23(2):494–510
van Loan CF (1992) Computational frameworks for the fast Fourier transform. SIAM, Philadelphia
Varga RS (1954) Eigenvalues of circulant matrices. Pac J Math 4:151–160
Vargas-Guzmán JA, Yeh T-CJ (1999) Sequential kriging and cokriging: Two powerful geostatistical approaches. Stoch Environ Res Risk Assess 13:416–435
Vargas-Guzmán JA, Yeh T-CJ (2002) The successive linear estimator: a revisit. Adv Water Resour 25:773–781
Wesson SM, Pegram GGS (2004) Radar rainfall image repair techniques. Hydrol Earth Syst Sci 8(2):8220–8234
Zimmerman DL (1989) Computationally exploitable structure of covariance matrices and generalized covariance matrices in spatial models. J Stat Comput Simul 32(1/2):1–15
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fritz, J., Neuweiler, I. & Nowak, W. Application of FFT-based Algorithms for Large-Scale Universal Kriging Problems. Math Geosci 41, 509–533 (2009). https://doi.org/10.1007/s11004-009-9220-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11004-009-9220-x