V. Yadav and A.M. Michalak
In this study, we present two algorithms that significantly reduce the cost of solving linear inverse problems. The first algorithm reduces the cost of matrix multiplication between an arbitrary matrix and a matrix that can be expressed as a Kronecker product of two or more smaller matrices. This algorithm has wide applicability in inverse problems, statistics, and numerical analysis. The second algorithm is specifically designed for linear inverse problems, and allows for the efficient computation of a posteriori covariances at aggregated spatio-temporal scales.
Addressing a variety of questions within Earth science disciplines entails the inference of the spatio-temporal distribution of parameters of interest based on observations of related quantities. Such estimation problems often represent inverse problems that are formulated as linear optimization problems. Computational limitations arise when the number of observations and/or the size of the discretized state space becomes large, especially if the inverse problem is formulated in a probabilistic framework and therefore aims to assess the uncertainty associated with the estimates. This work proposes two approaches to lower the computational costs and memory requirements for large linear space-time inverse problems, taking the Bayesian approach for estimating carbon dioxide (CO2) emissions and uptake (a.k.a. fluxes) as a prototypical example. The first algorithm can be used to efficiently multiply two matrices, as long as one can be expressed as a Kronecker product of two smaller matrices, a condition that is typical when multiplying a sensitivity matrix by a covariance matrix in the solution of inverse problems. The second algorithm can be used to compute a posteriori uncertainties directly at aggregated spatio-temporal scales, which are the scales of most interest in many inverse problems. Both algorithms have significantly lower memory requirements and computational complexity relative to direct computation of the same quantities (O(n2.5) vs. O(n3)). For an examined benchmark problem, the two algorithms yielded massive savings in floating point operations relative to direct computation of the same quantities. Sample computer codes are provided for assessing the computational and memory efficiency of the proposed algorithms for matrices of different dimensions.
Yadav, V., A.M. Michalak (2013) “Improving computational efficiency in large linear inverse problems: an example from carbon dioxide flux estimation”, Geoscientific Model Development, 6, 583-590, doi:10.5194/gmd-6-583-2013.