"Time" -parallel diffusion-based correlation operators

Correlation operators based on the solution of an implicitly formulated diffusion equation can be implemented numerically using the Chebyshev iteration method. The attractive properties of the algorithm for modelling correlation functions on high-performance computers have been discussed in a recent paper. The current paper describes a straightforward variant of that algorithm that allows the matrix-vector products involved in the sequential pseudo-time diffusion process to be performed in parallel. Contrary to the original algorithm, which requires solving a sequence of linear systems involving a symmetric positive-definite (SPD) matrix, the “time”-parallel algorithm requires solving a single linear system involving a nonsymmetric positive-definite (NSPD) matrix. The key information required by the Chebyshev iteration for solving the NSPD problem is an estimate of the extreme eigenvalues of the NSPD matrix. For the problem under consideration, the extreme eigenvalues of the NSPD matrix are the same as those of the original SPD matrix, and can be pre-computed using a Lanczos algorithm. The convergence properties of the algorithm are studied from a theoretical perspective and using numerical experiments with a diffusion-based covariance model employed with a variational data assimilation system for the global ocean. Results suggest that time-parallelization can reduce the run-time of an implicit diffusion-based correlation operator by greater than a factor of two. It can be implemented practically using a hybrid parallelization approach that combines Message Passing Interface tasks in the spatial domain with Open Multi-Processing threads spanning the pseudo-time dimension. The sensitivity of the results to preconditioning, to the choice of first guess and to the stopping criterion is discussed.