ABSTRACT. Parallel-in-time approaches for time-dependent PDEs attract much attention in the context of massively parallel environments. Multigrid Reduction in Time (MGRIT), which is one of these approaches, extracts the temporal parallelism by applying the multigrid reduction method for the temporal domain. However, as with the conventional multigrid method for spatial problems, its scalability deteriorates due to increased communication costs on the coarsest-level with high parallelism. In this work, we investigate the effectiveness of three techniques to enhance the scalability of MGRIT. The first one is coarse-grid agglomeration (CGA), which shrinks the number of active processes on the coarse-grid. The second one is the use of relaxation as a solver on the coarsest level. The third one is the GMRES acceleration. Numerical experiments show that the solver using all three techniques is most effective for a time-dependent Stokes problem. The combination of the three techniques achieved almost a 10-fold decrease of the time-to-solution compared to a simple MGRIT implementation.

ABSTRACT. Parallel-in-time methods are a promising approach for reducing simulation times of time-dependent PDEs on modern high performance computers by introducing parallelism in the temporal dimension. Two examples are MGRIT and Parareal, which both use a multigrid approach in time. While time integration on fine grid levels is performed in parallel across temporal subdomains, on the coarsest grid, the entire time interval is solved using serial time stepping. The choice of this coarsest grid can be complicated. If one chooses the coarsest grid too fine, the serial part of the algorithm dominates. If this grid is chosen too coarse, the serial part is small, but very large time steps are not practical for some application problems. In this talk, we introduce a new two-level MGRIT/Parareal-type algorithm with a truncated overlapping coarse grid. This new method allows parallel computations on the coarse grid, thus enabling the use of fine time steps on the coarse grid while simultaneously reducing serial computations. We investigate the convergence theory for this new method based on existing two-level convergence theory for MGRIT/Parareal and present parallel results on challenging nonlinear problems.

ABSTRACT. The parallel-in-time methods multigrid reduction-in-time (MGRIT) and Parareal provide an attractive option for increasing concurrency when simulating time-dependent PDEs. While these methods have been very successful for some parabolic equations, their performance often suffers dramatically when applied to advection-dominated problems or purely hyperbolic PDEs when using standard rediscretization approaches on coarse grids. We apply MGRIT or Parareal to the constant-coefficient linear advection equation, replacing standard rediscretization on coarse grids with improved coarse-grid operators computed by approximately minimizing error estimates from convergence theory. For Runge-Kutta methods combined with finite-difference spatial discretizations, we obtain scalable convergence in just a handful of iterations as well as parallel speed-ups over sequential time-stepping.

ABSTRACT. We consider the problem of accelerating the numerical simulation of time dependent problems involving a multi-step time scheme by the parareal algorithm ([4]). A multi-step time scheme can potentially bring higher approximation orders than plain one-step methods but the initialisation of each time window needs to be appropriately chosen. This point was addressed in the context of the simulation of molecular dynamics([1]) and for multigrid in time methods in [2,3]. The parareal method is based on combining predictions made by two propagators: an accurate and expensive one used in a parallel way over the time windows and a coarse and cheaper one used in a sequential way. At convergence, the parareal algorithm provides a solution that has the fine solver’s accuracy. In the classical version of the parareal method, the local initial condition of each time window is corrected at every iteration. When the fine and/or coarse propagators is a multi-step time scheme, we need to choose a consistent approximation of the solutions involved in the initialisation of the fine solver at each time window. Otherwise, an initialisation error would be propagated over the whole time interval and would prevent the parareal algorithm to converge towards the solution with the desired accuracy. In an attempt to address this issue, we present a new variant of the parareal algorithm, adapted to this type of discretization, and that ensures to recover the target solution with a convergence rate similar to the one of the classical parareal algorithm. A special effort has been made to design an algorithm adapted to this type of discretization without being intrusive in the coarse or fine solvers. With regard to the initialisation procedure, the multi-step parareal algorithm is more consistent with the underlying time scheme. We show both theoretically and numerically that the accuracy and convergence of the multi-step parareal algorithm are very competitive when we choose carefully the initialisation of each time window. References: [1] C. Audouze, M. Massot, and S. Volz, Symplectic multi-time step parareal algorithms applied to molecular dynamics, (2009). http://hal.archives-ouvertes.fr/hal-00358459/fr/ [2] R. D. Falgout, S. Friedhoff, T. V. Kolev, S. P. MacLachlan, J. B. Schroder, and S. Vandewalle, Multigrid methods with space-time concurrency, Computing and Visualization in Science, 18, pp. 123-143 (2017). LLNL-JRNL-678572, http://dx.doi.org/10.1007/s00791-017-0283-9. [3] R. D. Falgout, M. Lecouvez, and C. S. Woodward, A parallel-in-time algorithm for variable step multistep methods, Journal of Computational Science, Vol. 37, https://doi.org/10.1016/j.jocs.2019.101029.(2019). [4] J.-L. Lions, Y. Maday, G. Turinici, Résolution par un schéma en temps "pararéel", C. R. Acad. Sci. Paris (2001)

ABSTRACT. Based on current trends in computer architectures, faster compute speeds must come from increased parallelism rather than increased clock speeds, which are stagnate. This situation has created 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 the scheme known as multigrid-reduction-in-time (MGRIT), but note that there exist other parallel-in-time methods such as parareal and the parallel full approximation scheme in space and time (PFASST). MGRIT is a full multi-level method applied to the time dimension and computes multiple time-steps in parallel. Like all multigrid methods, MGRIT relies on the complementary relationship between relaxation (weighted-Jacobi) on a fine-grid and a correction from the coarse grid to solve the problem. In this work, we analyze and select relaxation weights for MGRIT using a convergence analysis and find that this is beneficial since it improves the convergence rate and consequently improves the efficiency of computation. We note that choosing appropriate weights for relaxation (here weighted-Jacobi) has a long history for improving the convergence of spatial multigrid methods, and thus it is no surprise that such weight selection can be beneficial for MGRIT, too. Our numerical results demonstrate an improved convergence rate and lower iteration count for MGRIT when non-unitary weights are used for weighted-Jacobi.

ABSTRACT. Application of multigrid methods to wave propagation problems is typically complicated due to the indefinite systems arising from discretization of hyperbolic operators. However, minimum-residual finite element (FE) discretizations always produce Hermitian positive-definite discrete operators, so this difficulty can be circumvented by designing multigrid methods that operate on the 'ellipticized' minimum residual discrete system. The DPG-MG method [Petrides, S. and Demkowicz, L. An adaptive multigrid solver for DPG methods with applications in linear acoustics and electromagnetics. arXiv:2010.06793 (2020)] is one such minimum-residual multigrid method based on the discontinuous Petrov-Galerkin (DPG) method with optimal test functions. This work focuses on the parallelization and analysis of the DPG-MG solver. In particular, when applied to high-frequency wave propagation problems, the DPG-MG solver produces a series of 'sweeping' non-uniform refinements that accumulate near driving boundaries then travel in the direction of wave propagation. The non-uniform coarsening strategy based on these sweeping grids has been observed to produce nearly wavenumber-robust convergence. Use of these non-uniformly coarsened grids is crucial to multigrid performance, but can complicate efficient parallel implementation. This work reports on the ongoing development of a scalable implementation of the DPG-MG solver and convergence comparison for uniform and non-uniform coarsening strategies applied to high-frequency wave propagation.

ABSTRACT. Getting multigrid solvers to work for the Helmholtz equation has been an open problem in applied mathematics for years. Much effort has been dedicated to finding solution methods which can use multigrid components to obtain solvers with a linear time complexity.

In this work, we present one of the first stand-alone multigrid solvers for the Helmholtz equation using both a constant and non-constant wavenumber model problem. We use standard smoothing techniques and do not require any restrictions on the number of grid points per wavelength on the coarse-grid. As a result we are able to obtain a full V- and W-cycle algorithm.

The key features of the algorithm are the use of higher-order intergrid transfer operators, and a complex shift in the weighted Jacobi smoothing operator. The proposed algorithm provides an important step towards the perpetuating branch of research in finding scalable solvers for challenging wave propagation problems.

ABSTRACT. When constructing algorithms to compute the matrix exponential actions on a vector, we can employ a matrix exponential residual. It is defined with respect to the differential equation whose exact solution is the sought-after product of the matrix exponential and the given vector. In Krylov subspace methods, this exponential residual is known to be a product of a scalar time-dependent function and a constant vector. Finding an approximate correction by restricting the residual to a coarser mesh results in a method similar to a multigrid solver for linear systems, where Krylov subspace iterations are used as a smoother. However, there is an important difference which gives complications: for the matrix exponential, once a correction on a coarser mesh is computed, it is not easy to determine the residual on the original fine mesh. In this talk, we discuss some strategies to overcome this difficulty. Preliminary numerical results demonstrate that our approach leads to a significant reduction of computational costs in Krylov subspace evaluations of the matrix exponential actions.

ABSTRACT. We present an approach for building optimal preconditioners for algebraic linear systems coming from conforming finite element discretizations of partial differential equations. The preconditioners utilize the framework of auxiliary or fictitious space methods. Namely, the main idea is to reformulate the original problem in a nonconforming setting, using discontinuous elements across subdomains, obtaining the element-by-element assembly property. This is achieved by introducing additional unknowns associated with the interfaces between subdomains, which decouples the subdomains. The continuity is enforced weakly via interface penalty terms. The resulting nonconforming formulation (or a Schur complement (reduced) version of it, that "condenses" the formulation only to the interfaces) is used to precondition the original problem. The element-by-element assembly property can be useful in "matrix-free" computations for high order discretizations, since it minimizes the coupling across subdomains and interfaces. Also, this provides a natural setting to apply element-based algebraic multigrid (AMGe) techniques for solving the nonconforming formulation. The resulting decoupling and locality can be beneficial for parallel computing. The approach allows for directly obtaining coarse nonconforming formulations, or their reduced (Schur complement) versions. This largely reduces the cost of the "condensation" step.

ABSTRACT. The solution of linear systems of equations is a central task in several scientific and engineering applications. For large scale simulations, nowadays accounting for several millions or even billions of unknowns, the algebraic multigrid (AMG) methods are the most common choice as linear solvers because of their fast convergence even for large-size problems. In this communication, we propose Chronos, a massively parallel implementation of a novel AMG framework, specifically designed to address complex problems by adapting its components, from the smoother to the coarse grid correction and prolongation to the problem at hand. A set of real-world problems, including structural mechanics, CFD and underground applications, are solved to assess the efficiency and robustness of Chronos.

ABSTRACT. Time-dependent PDEs arise in many real-world applications, particularly in flows of complex fluids, including thermally driven flows and magnetohydrodynamics. Numerical simulation of such problems relies heavily on our ability to build efficient solvers for the linearizations that arise at each time-step in a flow simulation. Multigrid methods are among the most common and powerful solution schemes in use in practical settings, but their development has often been focused on low-order discretizations in space and time, or in multi-step, but not multi-stage time discretizations, such as for BDF schemes. In this talk, I will present recent work on developing reliable multigrid solvers for general implicit Runge-Kutta (IRK) discretization schemes. We make use of the “monolithic” multigrid framework to handle the coupling between stage values in an IRK discretization, extending coupled relaxation schemes from the classical fluid and solid dynamics literature to this setting. Numerical results are presented for several constrained time-dependent PDEs, discretized using mixed finite-elements and IRK schemes, and compared in both accuracy and efficiency to BDF schemes of similar accuracy.

ABSTRACT. Maxwell's equations are a system of partial differential equations that govern the laws of electromagnetic induction. We study a mimetic finite-difference (MFD) discretization of the equations which preserves important underlying physical properties. We show that, after mass-lumping and appropriate scaling, the MFD discretization is equivalent to a structure-preserving finite-element (FE) scheme. This allows for a transparent analysis of the MFD method using the FE framework, and provides an avenue for the construction of efficient and robust linear solvers for the discretized system. In particular, block preconditioners designed for FE formulations can be applied to the MFD system in a straightforward fashion. We present numerical tests which confirm the robustness of the preconditioners.

ABSTRACT. We present a multigrid-in-channels (MGIC) approach that tackles the quadratic growth of the number of parameters with respect to the number of channels in standard convolutional neural networks (CNNs). It has been shown that there is a redundancy in standard CNNs, as networks with light or sparse convolution operators yield similar performance to full networks. However, the number of parameters in the former networks also scales quadratically in width, while in the latter case, the parameters typically have random sparsity patterns, hampering hardware efficiency. Our approach for building CNN architectures scales linearly with respect to the network's width while retaining full coupling of the channels as in standard CNNs. To this end, we replace each convolution block with its MGIC block utilizing a hierarchy of lightweight convolutions. Our extensive experiments on image classification, segmentation, and point cloud classification show that applying this strategy to different architectures like ResNet and MobileNetV3 considerably reduces the number of parameters while obtaining similar or better accuracy. For example, we obtain 76.1% top-1 accuracy on ImageNet with a lightweight network with similar parameters and FLOPs to MobileNetV3.