EFFICIENT COMPUTATION OF LINEARIZED CROSS-COVARIANCE AND AUTO-COVARIANCE MATRICES OF INTERDEPENDENT QUANTITIES

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 n2, 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 ${\cal O}$(n2) to ${\cal O}$(nlog2n) and storage requirements are reduced from ${\cal O}$(n2) to ${\cal O}$(n).