ABSTRACT. In this paper, we present a novel isogeometric multigrid approach to the numerical solution of the classical Navier-Stokes equations. This formulation utilizes divergence-conforming B-spline basis functions which respect the underlying de Rham cohomology, in particular, the relationship between the pressure and velocity variables through differential operators. Schwarz-style smoothers in conjunction with overlapping subdomains respecting this de Rham sequence are employed for use in a geometric multigrid method. Numerical results for Darcy-Stokes and generalized Oseen flows, arising through explicit and semi-implicit Navier-Stokes discretizations, are presented in both two- and three-dimensions. These results demonstrate the robustness of the geometric multigrid method through the invariance of convergence rates with respect to grid resolution and flow parameters.

ABSTRACT. Since the Nobel prize has been awarded in 2010 for the isolation of graphene, research on this miraculous 2-dimensional material has flourished. In order to calculate the electronic properties of graphene structures a tight-binding approach can be used. The tight-binding formulation leads to linear systems of equations which are maximally indefinite and can be seen both as a discretization of a system of PDEs or a staggered discretization. In this talk we present a geometric multigrid method for this problem and the results of the two-level convergence analysis obtained by local Fourier analysis. Numerical tests show the exactness of the local Fourier analysis and the scalability of the multigrid method.

ABSTRACT. The discontinuous Petrov-Galerkin (DPG) methodology of Demkowicz and Gopalakrishnan guarantees the optimality of the solution in an energy norm, and provides several features facilitating adaptive schemes. A key question that has not yet been answered in general—though there are some results for Poisson, e.g.—is how best to precondition the DPG system matrix, so that iterative solvers may be used to allow solution of large-scale problems.

In this presentation, we detail a strategy for preconditioning the DPG system matrix using geometric multigrid, which we have implemented as part of the Camellia finite element library, and demonstrate through numerical experiments its effectiveness in the context of several variational formulations. We observe that in some of our experiments, the behavior of the preconditioner is closely tied to the discrete test space enrichment.

We include experiments involving adaptive meshes with hanging nodes for lid-driven cavity flow, demonstrating that the preconditioners can be applied in the context of challenging problems. We also include a scalability study demonstrating that the approach—and our implementation—scales well to many MPI ranks.

ABSTRACT. In our development of a global atmospheric model, there arises the need to solve a highly anisotropic, elliptic 3D equation. To increase concurrency, we use FFT to decompose the problem into a set of Helmholtz equations on 2D slices through the sphere. We use cell-centered finite difference discretizations and we develop a GMG solver for the resulting linear systems, which are non-symmetric and may be highly ill-conditioned. With pure, homogeneous Neumann boundary conditions, the equation corresponding to the zero harmonic becomes singular Poisson. In that case, we propose using TQRCP or TSVD as the coarse-grid solver. We present some physical justifications for the method and analyze its performance in comparison with other coarse-grid solvers, such as GMRES.

ABSTRACT. When solving nonlinear partial differential equations using the Finite Element Method, the inner linear-system solves are often the bottleneck in computation. In general, multilevel methods provide efficient solvers for these systems that are optimal and scalable to large, parallel machines. In this talk, we discuss parallel geometric multigrid methods that utilize operator-dependent coarse spaces through an AMGe-type mechanism. In particular, the coarse operator-dependent spaces can have approximation properties of the same order as the fine-grid spaces. We show results for a collection of geometric multilevel preconditioners for solving mixed formulations of Darcy problems in a distributed computing environment.

ABSTRACT. Problems from graph drawing, spectral clustering, network flow and graph partitioning all can be expressed as Laplacian matrices. Theoretically fast approaches to solving these problems exist, but in practice these techniques are slow. Three practical approaches have been proposed and work well in serial. However, as problem sizes increase and single core speeds stagnate, parallelism is essential to solve problems quickly. We present an unsmoothed aggregation Multigrid method for solving graph Laplacians in distributed memory setting. Our solver scales up to 64 compute nodes and achieves speedups of up to 83x over the existing serial solutions.

ABSTRACT. Many computational models in science and in machine learning respect locality defined on graphs that may be more general than conventional meshes. If we could define a useful distance-like measure between graphs, we could for example use graph grammars to define the structure of exponentially-growing sequences of graphs (we call them graph lineages) that are relatively close to each other in that distance measure, and relatively far from graphs in other such sequences, and we could use these relationships to study the scaling of scientific models. To this end we theoretically and computationally investigate inter-graph distance-like measures that are defined in terms of prolongation/restriction matrices that optimally match the effects of diffusion processes within the two graphs. We suggest that these prolongation/restriction matrices may be derived while computing graph-graph distance and then used to relate successive graphs in a graph lineage, and thereby to define multiscale dynamical models. In a second portion of this work we assume several graph lineages (defined by graph grammars) are each well controlled in this manner, and define efficient lineage-level operations that can produce new graph lineages from old ones, such as a “skeletal product” which is much more space-efficient (particularly for high-dimensional problems) than conventional graph products. We measure critical indices of Ising models on skeletal product graphs.

ABSTRACT. We present a parallelizable direct method for computing the solution to graph Laplacian-based linear systems derived from graphs that can be hierarchically bipartitioned with small edge cuts. For a graph of size n that can be recursively partitioned into equal-sized sets with constant-size edge cuts, our method decomposes a graph Laplacian in time O(n log n), and then uses that decomposition to perform a linear solve in time O(n \log n).

Many real-world graphs, however, do not possess this property. So, we use this technique to design a preconditioner for graph Laplacians that do not have this property. Finally, we augment this preconditioner with a two-grid method that accounts for much of the preconditioner's weaknesses. We present an analysis of this method, as well as a general theorem for the condition number of a general class of two-grid support graph-based preconditioners. Numerical experiments illustrate the performance of the studied methods.

ABSTRACT. In this talk, we will discuss coarsening procedures for graph Laplacian problems written in a mixed saddle-point form. In that form in addition to the original vertex degrees of freedom (dofs), we also have edge degrees of freedom. We extend the previously developed aggregation-based coarsening procedures applied to both sets of dofs [Vassilevski and Zikatanov, Commuting projections on graphs, Numer. Lin. Alg. Appl., 21 (2014), pp. 297--315], now to allow more than one coarse vertex dof per aggregate, by solving local spectral problems. The pair of coarse spaces are constructed such that the inf–sup stability on coarse levels is maintained, and they have provable approximation properties. We will demonstrate applications of the method to partitioning a general graph and to numerically coarsen reservoir models.

ABSTRACT. Classical spectral clustering is based on a spectral decomposition of a graph Laplacian, obtained from a graph adjacency matrix representing positive graph edge weights describing similarities of graph vertices. In signed graphs, the graph edge weights can be negative to describe disparities of graph vertices, for example, negative correlations in the data. Negative weights lead to possible negative spectrum of the standard graph Laplacian, which is cured by defining a signed Laplacian. We follow [1] to compare the standard and signed Laplacians and numerically evaluate LOBPCG [2] with algebraic multigrid preconditioning, for spectral clustering of signed graphs.

[1] A. Knyazev, Signed Laplacian for Spectral Clustering Revisited, https://arxiv.org/abs/1701.01394, 5 Jan 2017. [2] A. Knyazev, Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method. SIAM Journal on Scientific Computing. 23 (2): 517, 2001.

ABSTRACT. As the number of cores increases on current and future architectures, the natural sequential approach to time integration is becoming a more serious bottleneck for achieving high scalability. One alternative to overcome this problem is the use of multigrid-in-time algorithms such as MGRIT [1]. Although first designed for one-step methods, we apply the MGRIT algorithm to multistep BDF methods for the integration of fully implicit non linear Differential Algebraic Equations (DAE) using adaptive refinement in time. The DAEs presented here arise from power system simulations, for which variable step-size methods are useful to deal with discontinuities. Another approach using root-finding capabilities is investigated. This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract DE-AC52-07NA27344. Lawrence Livermore National Security, LLC. LLNL-ABS-681082.

[1] R. D. Falgout, S. Friedhoff, T. V. Kolev, S. P. MacLachlan, and J. B. Schroder, ``Parallel time integration with multigrid'',SIAM J. Sci. Comput., vol. 36, no 6, pp. C635--C661, 2014, LLNL-JRNL-645325.

ABSTRACT. Fractional calculus has become increasingly popular in recent years due to their frequent appearance in various applications. Due to the nonlocal property of fractional differential operators, numerical methods usually generate systems of equations where the coefficient matrix is dense. The standard solution of such systems requires a very high computational cost in addition to a high storage cost. This is quite different from the integer differential operators, which typically yield sparse coefficient matrices that can be efficiently solved by fast iterative methods with $O(N)$ complexity, being $N$ the number of grid points. Therefore, the design of efficient solvers for the numerical simulation of these problems is a difficult task. In this work, we propose a parallel-in-time algorithm based on the waveform relaxation approach, whose application to time-fractional problems seems very natural. This is due to the fact that the fractional derivative at each spatial point depends on the values of the function at this point at all earlier times. Exploiting the Toeplitz-like structure of the coefficient matrix, the computational complexity of the proposed multigrid waveform relaxation method is $O(N M \log(M))$, where $M$ is the number of time steps and $N$ is the number of spatial grid points. Moreover, a semi-algebraic mode analysis is used to theoretically confirm the good results obtained.

ABSTRACT. In this talk, we will present some numerical studies on algebraic multigrid methods for solving the linear algebraic equations arising from a space-time finite element discretization of parabolic problems using adaptivity on tetrahedral meshes. The finite element discretization is based on the recent results [O.~Steinbach: Space-time finite element methods for parabolic problems, Comput. Methods Appl. Math., 15:551-566, 2015]. As an extension, we will mainly focus on $h$-adaptivity using the residual-based a posteriori error estimation. We study the algebraic multigrid methods for solving the space-time finite element equations.This is a joint work with O.~Steinbach.

ABSTRACT. Fluid-structure interaction (FSI) phenomena are present in many different fields of application, such as biomedical engineering. Even with simplistic mathematical models, numerical simulations of a studied time-dependent system may yield significant computational cost. For example, simulating periodic FSI problems usually requires running multiple cycles to achieve periodic steady-state. For real-world engineering problems, the time-to-solution may often be undesirably large and conflict with required fast turn-around. Thus, parallelization techniques are the key to decrease the wall clock time of a given algorithm.

Spatial parallelization techniques, such as domain decomposition methods, are commonly used to speed up computations by distributing the work load per time step amongst a number of available processors. However, spatial parallelization saturates with increasing communication tasks and an optimum number of processors (for example, with respect to parallel efficiency or minimum runtime) may not fully utilize the available resources. A further reduction of the time-to-solution may be achieved by, for example, parallelization in the temporal domain.

In this talk, we will present a multigrid-reduction-in-time (MGRIT) algorithm [1] for the solution of a time-dependent and generally nonlinear system. The MGRIT algorithm is a true multilevel approach based on multigrid techniques applied to the temporal domain and thus introduces a grid hierarchy of fine and coarse time grids. It solves the global space-time problem iteratively by employing multigrid cycling (e.g. V- and F-cycles), FC relaxation and coarse-grid updates. The algorithm uses multiple temporal levels and allows re-use of optimized and efficient solvers. Further, temporal parallelization may be complemented with spatial parallelization to solve the spatial problem for each time point more effectively. The MGRIT algorithm provides a non-intrusive way to achieve speedups beyond the speedups that are observed for purely space-parallel methods.

To provide a thorough basis for further investigations of multi-physics problems, we study the application of the MGRIT algorithm to single-physics problems, such as flow over a moving domain. Here, we focus on properties of the space-time solver (e.g. scalability) and demonstrate that traditional time stepping schemes (i.e. direct temporal solvers) and the MGRIT solver (i.e. iterative temporal solver) solve the same system of equations. We further extend this approach in the context of FSI, demonstrating efficacy using FSI benchmark problems.

[1] R.D. Falgout, S. Friedhoff, Tz.V. Kolev, S. MacLachlan and J. Schroder, “Parallel Time Integration with Multigrid”, SIAM J. Sci. Comput., Vol. 36, pp. C635-C661, (2014).

ABSTRACT. Multigrid methods have been developed for both structured and unstructured grids. In terms of exascale computing, memory, and setup time, there are significant potential advantages to structured mesh approaches over unstructured schemes. Further, multigrid algorithms that take advantage of structure can exhibit superior convergence rates when compared with their unstructured multigrid counterparts. Unfortunately, the types of applications that can be addressed with structured meshes are quite limited. In many circumstances, however, an application may only require complex unstructured meshes within small sub-regions of the overall domain to accurately capture important physical features. For these applications, we aim to develop multigrid methods that leverage the structure present over most of the domain while employing more general techniques only within regions where complex unstructured meshes are truly needed.

ABSTRACT. Computer simulations of multiphysics problems not only grow in size but also in complexity including more and more types of physics and coupling equations. Multi-physics systems typically characterized by multi-scale temporal and spatial mechanisms often demand implicit time integration and the solution of large coupled linear systems represented by blocked operators.

While multigrid methods are known to be efficient for certain classes of single-field problems, the design and handling of fully coupled physics-based multigrid preconditioners for multiphysics problems remains a challenge. MueLu is a multigrid framework in Trilinos which allows one to flexibly build and extend application-specific block preconditioners based on aggregation-based algebraic multigrid methods. It can be used in combination with the existing block preconditioning package Teko from Trilinos in a very flexible way: MueLu either provides the multigrid capability used within Teko block preconditioners, or MueLu can use the Teko implementation of block preconditioners as block smoothers within its multiphysics multigrid preconditioners.

Furthermore, MueLu allows the definition of simple user interfaces with a minimum of user parameters for application-specific multiphysics preconditioners. This helps end users to apply the preconditioners in a production environment without suffering from the complexity of modern physics-based blocked multigrid preconditioners.

We demonstrate the design principles and usage of the MueLu framework for resistive MHD problems and compare the performance.​

ABSTRACT. The Multiphysics Object Oriented Simulation Environment (MOOSE) is a parallel finite element, multiphysics framework, which has the capability to simulate fully coupled multiphysics from a wide range of physical processes including fluid dynamics, solid mechanics, phase field fracture, and neutronics. Fully coupled multiphysics present unique numerical challenges due to the large number of disparate properties involved on different time and spatial scales. To overcome this difficulty, we present a class of parallel hybrid algorithms based on field-splitting, algebraic multigrid (AMG) and additive Schwarz methods (ASM). Field-splitting, AMG and ASM have been individually explored thoroughly but the use of them in combination for coupled multiphysics has not fully realized. We design and implement a class of parallel hybrid algorithms in MOOSE to explore optimal combinations of field-splitting AMG and ASM for improving simulation efficiency. We show that these parallel hybrid algorithms are scalable and efficient for multiphysics problems in parallel.

ABSTRACT. The interaction between fluid flow and a deformable porous medium is a complicated multi-physics problem which can be described by a coupled model based on the Stokes and poroelastic equations. A monolithic multigrid method together with a coupled Vanka smoother and a decoupled Uzawa smoother is employed as an efficient numerical technique for the linear discrete system obtained by finite volumes on staggered grids. A novelty in our modeling approach is that at the interface of the fluid and poroelastic medium, two unknowns from the different subsystems are defined at the same grid point. We propose a special discretization at or near the points in the interface, which combines the approximation of the governing equations and the considered interface conditions. In the decoupled Uzawa smoother, Local Fourier analysis (LFA) helps us to select optimal values of the relaxation parameter appearing. To implement the monolithic multigrid method, grid partitioning is used to deal with the interface updates when communications are required between two subdomains. Numerical experiments show that the proposed numerical method provides an excellent convergence. The efficiency and robustness of the method are confirmed in numerical experiments with typically small values of the physical coefficients.

ABSTRACT. We apply a multigrid reduction in time algorithm to hyperbolic partial differential equations. This study is motivated by the observation that sequential time stepping is an obvious computational bottleneck when attempting to implement highly concurrent algorithms, thus parallel-in-time methods are particularly desirable. In the case of explicit time stepping, spatial coarsening may be necessary to ensure stability conditions are satisfied on all levels, and it may be useful for implicit time stepping by producing cheaper multigrid cycles. Unfortunately, classical spatial coarsening results in extremely slow convergence when the wave speed is near zero, even if only locally. We present an adaptive spatial coarsening strategy which addresses this issue for 1D linear advection and implicit time stepping. Numerical results show that this offers significant improvements over classical coarsening. Future improvements and extensions to explicit time stepping are discussed.

ABSTRACT. Often real-world graphs are directed, meaning that information flows from a vertex to another vertex in one direction, such as hyperlink graphs, biological neural networks and electrical power grids. There are many applications where data scientists are interested in solving linear systems associated with directed graphs. Currently, data scientists are using preconditioned GMRES and LSQR to solve linear systems involving directed graph associated matrix representations (e.g. graph Laplacian). However, these methods tend to be unacceptably slow as the number of edges grows. We propose a new algebraic multigrid algorithm, Nonsymmetric Lean Algebraic Multigrid (NS-LAMG), that uses ideas from undirected graph Laplacian multigrid solvers, nonsymmetric Smoothed Aggregation and Markov chain stationary probability vector multigrid solvers. We redefine low-degree elimination proposed in Lean Algebraic Multigrid for undirected graphs to directed graphs and numerically show that low-degree elimination increases NS-LAMG performance. We adapt the transfer operators from nonsymmetric Smoothed Aggregation by using the null-space vectors of the problem matrix and numerically show that NS-LAMG out performs GMRES(k) for real-world, directed graph Laplacian linear systems.