Abstract
In many geostatistical applications, spatially discretized unknowns are conditioned on observations that depend on the unknowns in a form that can be linearized. Conditioning takes several matrix–matrix multiplications to compute the cross-covariance matrix of the unknowns and the observations and the auto-covariance matrix of the observations. For large numbers n of discrete values of the unknown, the storage and computational costs for evaluating these matrices, proportional to n 2, become strictly inhibiting. In this paper, we summarize and extend a collection of highly efficient spectral methods to compute these matrices, based on circulant embedding and the fast Fourier transform (FFT). These methods are applicable whenever the unknowns are a stationary random variable discretized on a regular equispaced grid, imposing an exploitable structure onto the auto-covariance matrix of the unknowns. Computational costs are reduced from O(n 2) to O(nlog2 n) and storage requirements are reduced from O(n 2) to O(n).
Similar content being viewed by others
REFRENCES
Barnett, S., 1990, Matrices methods and applications (Oxford applied mathematics and computing science series): Clarendon Press, Oxford, 450p.
Cooley, J., and Tukey, J., 1965, An algorithm for the machine calculation of complex fourier series: Math. Comp., v.19, p. 297-301.
Davis, P., 1979, Circulant matrices, pure and applied mathematics: Wiley, New York, 250p.
Dietrich, C., and Newsam, G., 1993, A fast and exact method for multidimensional gaussian stochastic simulations: Water Resourc. Res., v.29, no.8, p. 2861-2869.
Dietrich, C., and Newsam, G., 1996, A fast and exact method for multidimensional gaussian stochastic simulations: Extension to realizations conditioned on direct and indirect measurements: Water Resourc. Res., v.32, no.6, p. 1643-1652.
Dietrich, C., and Newsam, G., 1997, Fast and exact simulation of stationary gaussian processes through circulant embedding of the covariance matrix: SIAM J. Sci. Comp., v.18, no.4, p. 1088-1107.
Frigo, M., and Johnson, S., 1998, FFTW: An adaptive software architecture for the FFT, in ICASSP conference proceedings, Vol. 3, p. 1381-1384. http://www.fftw.org
Golub, G., and van Loan, C., 1996, em matrix computations, 3rd edn.: John Hopkins University Press, Baltimore, 694 p.
Good, I., 1950, On the inversion of circulant matrices: Biometrika, v.37, p. 185-186.
Gray, R., 1972, On the asymptotic eigenvalue distribution of Toeplitz matrices: IEEE Trans. Inf. Theor., v.18, no.6, p. 725-730.
Kitanidis, P., 1995, Quasi-linear geostatistical theory for inversing: Water Resourc. Res., v.31, no.10, p. 2411-2419.
Kozintsev, B., 1999, Computations with gaussian random fields: PhD thesis, Institute for Systems Research, University of Maryland.
Nott, D., and Wilson, R., 1997, Parameter estimation for excursion set texture models: Signal Process., v.63, p. 199-210.
Schweppe, F., 1973, Uncertain dynamic systems: Prentice-Hall, Englewood Cliffs, NJ, 563 p.
Sun, N.-Z., 1994, Inverse problems in groundwater modeling, Theory and applications of transport in porous media: Kluwer Academic, Dordrecht, The Netherlands.
van Loan, C., 1992, Computational frameworks for the Fast Fourier Transform: SIAM, Philadelphia, 273 p.
Zimmerman, D., 1989, Computationally exploitable structure of covariance matrices and generalized covariance matrices in spatial models: J. Stat. Comp. Sim., v.32, no. 1/2, p. 1-15.
Zimmerman, D., de Marsily, G., Gotaway, C., and Marietta, M., 1998, A comparison of seven geostatistically based inverse approaches to estimate transmissivities for modeling advective transport by groundwater flow: Water Resourc. Res., v.34, no.6, p. 1373-1413.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nowak, W., Tenkleve, S. & Cirpka, O.A. Efficient Computation of Linearized Cross-Covariance and Auto-Covariance Matrices of Interdependent Quantities. Mathematical Geology 35, 53–66 (2003). https://doi.org/10.1023/A:1022365112368
Issue Date:
DOI: https://doi.org/10.1023/A:1022365112368