Abstract
The sum of Kronecker products (SKP) representation for spatial covariance matrices from gridded observations and a corresponding adaptive-cross-approximation-based framework for building the Kronecker factors are investigated. The time cost for constructing an n-dimensional covariance matrix is O(nk2) and the total memory footprint is O(nk), where k is the number of Kronecker factors. The memory footprint under the SKP representation is compared with that under the hierarchical representation and found to be one order of magnitude smaller. A Cholesky factorization algorithm under the SKP representation is proposed and shown to factorize a one-million dimensional covariance matrix in under 600 seconds on a standard scientific workstation. With the computed Cholesky factor, simulations of Gaussian random fields in one million dimensions can be achieved at a low cost for a wide range of spatial covariance functions.
•The sum of Kronecker products (SKP) representation can be constructed with linear complexity.•The SKP representation reaches near-optimal memory footprint.•Cholesky factorization in one million dimensions can be performed in under 600 seconds.