"Time"‐Parallel diffusion‐based correlation operators. (16th October 2018) - Weaver, Anthony T.; Gürol, Selime; Tshimanga, Jean; Chrust, Marcin; Piacentini, Andrea
Abstract : 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, in sequence, linear systems involving a symmetric positive‐definite (SPD) matrix, the "time"‐parallel algorithm requires solving a single linear system involving a non‐symmetric 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 applied to the latter. The convergence properties of the algorithm are studied from a theoretical perspective and using numerical experiments with a diffusion‐based covariance model in 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. Abstract : This paper describes a diffusion‐based correlation model in which the M matrix–vector products involved in the sequential M pseudo‐time‐step implicit diffusion process can be performed in parallel. The "time"‐parallel algorithm requires solving a single linear system involving a non‐symmetric positive definite matrix. An approximate solution can be obtained using the Chebyshev iteration. Results suggest that the "time"‐parallel algorithm can reduce run‐time of the correlation operator by a factor between two and three.