A Note on Parallel Preconditioning for the All-at-Once Solution of Riesz Fractional Diffusion Equations

The $p$-step backward difference formula (BDF) for solving systems of ODEs can be formulated as all-at-once linear systems that are solved by parallel-in-time preconditioned Krylov subspace solvers (see McDonald et al. [36] and Lin and Ng [32]). However, when the BDF$p$ (2 ≤ $p$ ≤ 6) method is used to solve time-dependent PDEs, the generalization of these studies is not straightforward as $p$-step BDF is not selfstarting for $p$ ≥ 2. In this note, we focus on the 2-step BDF which is often superior to the trapezoidal rule for solving the Riesz fractional diffusion equations, and show that it results into an all-at-once discretized system that is a low-rank perturbation of a block triangular Toeplitz system. We first give an estimation of the condition number of the all-at-once systems and then, capitalizing on previous work, we propose two block circulant (BC) preconditioners. Both the invertibility of these two BC preconditioners and the eigenvalue distributions of preconditioned matrices are discussed in details. An efficient implementation of these BC preconditioners is also presented, including the fast computation of dense structured Jacobi matrices. Finally, numerical experiments involving both the one- and two-dimensional Riesz fractional diffusion equations are reported to support our theoretical findings.     

A parallel Navier–Stokes solver using spectral discretisation in time

We investigate the performance of a multi-harmonic space–time approach to solve time-periodic flow problems. It employs a Fourier spectral discretisation of the time domain. The resulting large system of nonlinear equations is solved iteratively and in parallel. For illustration, a three-dimensional channel flow disturbed by an oscillating force is simulated.     

Weighted relaxation for multigrid reduction in time

Current trends in computer architectures now mean that faster computation speed must come primarily from increased concurrency, not faster clock speeds, which are stagnating. Thus, this situation creates bottlenecks for serial algorithms, including the well-known bottleneck for sequential time-integration, where each individual time-value (i.e., time-step) is computed sequentially. One approach to alleviate this and achieve parallelism in time is with multigrid. In this work, we consider multigrid-reduction-in-time (MGRIT), a multilevel method applied to the time dimension that computes multiple time-steps in parallel. Like all multigrid methods, MGRIT relies on the complementary relationship between relaxation on a fine-grid and a correction from the coarse grid to solve the problem. All current MGRIT implementations are based on unweighted-Jacobi relaxation; here we introduce the concept of weighted relaxation to MGRIT. We derive new convergence bounds for weighted relaxation, and use this analysis to guide the selection of relaxation weights. Numerical results then demonstrate that by choosing appropriate non-unitary relaxation weights, one can achieve faster convergence rates and lower iteration counts for MGRIT when compared with unweighted relaxation. In most cases, weighted relaxation yields a 10%–20% saving in iterations, which is significant when using large high-performance computers. For A-stable integration schemes, results also illustrate that under-relaxation can restore convergence in some cases where unweighted relaxation is not convergent.