
[Illinois] Multigrid Methods Conference
04 Feb 2016  Workshops
HIGHLIGHTED TOPICS
Uncertainty Quantification
Optimization and Inverse Problems
Data Mining, Large Graphs, and Markov Chains
Nonsymmetric and Indefinite Problems
Krylov Accelerators
Hybrid DirectIterative Linear Solvers
Parallel Multigrid on Multicore Systems and Heterogeneous Architectures
Time Parallel Methods
Iterative Methods in Applications (e.g., Electromagnetics, Energy, Environmental, MHD, Neutronics, Transport/Reaction)

[Illinois] A Massively Parallel Semicoarsening Multigrid for 3D Reservoir Simulation on Multicore and MultiGPU Architectures
04 Feb 2016  Online Presentations  Contributor(s): Abdulrahman Manea
In this work, we have designed and implemented a massively parallel version of the Semicoarsening Black Box Multigrid Solver [1], which is capable of handling highly heterogeneous and anisotropic 3D reservoirs, on a parallel architecture with multiple GPU’s. For comparison purposes, the same algorithm was also implemented on a sharedmemory multicore parallel architecture using OpenMP. The parallel implementation exploits the parallelism in every module of the original Multigrid...

[Illinois] On the Design of a Finite Element Multigrid Solver for Mimetic Finite Difference Schemes
04 Feb 2016  Online Presentations  Contributor(s): Carmen Rodrigo
The focus of this work is to study the relation between mimetic finite difference schemes on triangular grids and some finite element methods for two model problems based on curlrot and graddiv operators. With this purpose, modified Nédélec and RaviartThomas finite element methods are derived respectively. This connection allows us to design an efficient multigrid method for the curlrot problem, by considering canonical intergrid transfer operators arising from the finite...

[Illinois] LeastSquares Finite Element Method and Nested Iteration for Electromagnetic TwoFluid Plasma Models
04 Feb 2016  Online Presentations  Contributor(s): Christopher Leibs
Efforts are currently being directed towards a fully implicit, electromagnetic, JFNKbased solver, motivating the necessity of developing a fluidbased, electromagnetic, preconditioning strategy [1]. The twofluid plasma (TFP) model is an ideal approximation to the kinetic Jacobian. The TFP model couples both an ion and an electron fluid with Maxwell's equations. The fluid equations consist of the conservation of momentum and number density. A Darwin approximation of Maxwell is used to...

[Illinois] A Multigrid Method for the SelfAdjoint Angular Flux Form of the RadiationTransport Equation Based on Cellwise Block Jacobi Iteration
04 Feb 2016  Online Presentations  Contributor(s): Jeffrey Densmore
Cellwise block Jacobi iteration is a technique for radiationtransport calculations in which the angular flux for all directions is solved for simultaneously within a spatial cell with the angular flux in neighboring cells held fixed. Each step of the iteration then involves the inversion of a small to moderatesized matrix for every cell. The resulting arithmetic intensity may make cellwise block Jacobi iteration suitable for advanced, heterogeneous computing architectures. However, the...

[Illinois] Understanding the Propagation of Silent Data Corruption in Algebraic Multigrid
04 Feb 2016  Online Presentations  Contributor(s): Jon Calhoun
Sparse linear solvers from a fundamental kernel in high performance computing (HPC). Exascale systems are expected to be more complex than systems of today being composed of thousands of heterogeneous processing elements that operate at nearthresholdvoltage to meet power constraints. The combination of near nearthresholdvoltage and number of processing elements required to reach exascale increases the rate of silent data corruption (SDC). With the rate of SDC expected to be higher,...

[Illinois] A Performance Comparison of Algebraic Multigrid Preconditioners on GPUs and MIC
04 Feb 2016  Online Presentations  Contributor(s): Karl Rupp
Algebraic multigrid (AMG) preconditioners for accelerators such as graphics processing units (GPUs) and Intel's manyintegrated core (MIC) architecture typically require a careful, problemdependent tradeoff between efficient hardware use, robustness, and convergence rate in order to minimize timetosolution. Several variants of AMG with finegrained parallelism have been proposed recently, but a comparison across different hardware architectures is difficult since the proposed...

[Illinois] Monolithic Multigrid Methods for Coupled MultiPhysics Problems
04 Feb 2016  Online Presentations  Contributor(s): Scott Maclachlan
While blockdiagonal and approximate blockfactorization preconditioners are often considered for coupled problems, monolithic approaches can offer improved performance, particularly when the coupling between equations is strong. In this talk, we discuss the extension of BraessSarazin relaxation techniques to the linear systems resulting from the linearization and finiteelement discretization of such coupled systems. Defining an easytoinvert approximation to the (1,1) block of the system...

[Illinois] Application of Multigrid Techniques to Magnetic and Electromagnetic Systems
04 Feb 2016  Online Presentations  Contributor(s): Benjamin Cowan
We discuss the use of multigrid techniques for several novel systems related to electromagnetics. One of these is the magnetostatic problem, in which systems can involve highly anisotropic and nonlinear materials. We describe the linear problems arising in several variations of this problem, including fully static, hysteretic, and eddycurrent. We show results of tests of several AMG methods for solving these systems in 2D and 3D. We then discuss the challenges in solving the nonlinear...

[Illinois] Geometric Multigrid for MHD Simulations with Nedelec Finite Elements on Tetrahedral Grids
04 Feb 2016  Online Presentations  Contributor(s): Chris Hansen
The MagnetoHydroDynamic (MHD) model is used extensively to simulate macroscopic plasma dynamics in Magnetic Confinement Fusion (MCF) devices. In these simulations, the span of time scales from fast wave dynamics to the desired evolution of equilibrium due to transport processes is large, resulting in stiff linear systems for implicit time advance. Many existing codes leverage toroidal symmetry, a common feature of many MCF devices, to develop efficient preconditioners for the linearized...

[Illinois] Parallel Multigrid Preconditioner Based on Automatic 3D Tetradedric Meshes
04 Feb 2016  Online Presentations  Contributor(s): Frederic Vi
Multigrid methods are efficient for solving large sparse linear systems. Geometric (GMG) and Algebraic Multigrid (AMG) have both their own benefits and limitations. Combining the simplicity of AMG with the efficiency of GMG lead us to the development of an Hybrid Multigrid preconditionner. From an initial fine mesh we first build coarser unnested meshes and then deduce interpolation and restriction matrices based on interpolation of a mesh into a coarser one. We finally use Galerkin relation...

[Illinois] HPGMG: Benchmarking Computers Using Multigrid
04 Feb 2016  Online Presentations  Contributor(s): Jed Brown
HPGMG (https://hpgmg.org) is a geometric multigrid benchmark designed to measure the performance and versatility of computers. For a benchmark to be representative of applications, good performance on the benchmark should be sufficient to ensure good performance on most important applications and only those system features necessary for some important applications should be stressed by the benchmark. Moreover, the specification should be scalefree and the method should solve a...

[Illinois] A Scalable Algorithm for Inverse Medium Problems with Multiple Sources
04 Feb 2016  Online Presentations  Contributor(s): Keith Kelly
We consider the problem of acoustic scattering as described by the freespace, timeharmonic scalar wave equation given by
(0.1)
along with radiation boundary conditions. Here, is a point in , is the source term, and is the wavenumber. Our formulation is based on potential theory. First we write as , where is a constant value, is a known function of space, and is the unknown medium perturbation. Then,...

[Illinois] Support Graph Smoothing Techniques
04 Feb 2016  Online Presentations  Contributor(s): Alyson Fox
Many tasks in largescale network analysis and simulation require efficient approximation of the solution to the linear system $ Lx=b$, where $ L$ is a graph Laplacian. However, due to the large size and complexity of scalefree graphs, standard iterative methods do not perform optimally. The use of support graph techniques for preconditioning graph Laplacian systems has been studied, but efficiently finding optimal preconditioners is challenging for general scalefree graphs. An attractive...

[Illinois] TaskGraph and Functional Programming Models: The New Paradigm
04 Feb 2016  Online Presentations  Contributor(s): Ben Bergen
The Message Passing Interface (MPI) is an example of a distributedmemory communication model that has served us well through the CISC processor era. However, because of MPI's lowlevel interface, which requires the user to manage raw memory buffers, and its bulksynchronous communication model, MPI will have great difficulty in scaling to exascale systems and beyond. Additionally, the MPI model cannot be easily extended to include the fault tolerance and resilience features that will be...

[Illinois] A Fast Multigrid Approach for Solving the Helmholtz Equation with a Point Source
04 Feb 2016  Online Presentations  Contributor(s): Eran Treister
Solving the discretized Helmholtz equations with high wave numbers in large dimensions is a challenging task. However, in many scenarios, the solution of these equations is required for a point source. In this case, the problem can be be reformulated and split into two parts: one in a solution of the eikonal equation for the travel time, and the second is a solution of a complexvalued advectiondiffusionreaction (ADR) equation for the amplitude. The eikonal equation for the travel time can...

[Illinois] Compatible Relaxation Based GeometricAlgebraic Multigrid
04 Feb 2016  Online Presentations  Contributor(s): Fei Cao
We develop compatible relaxation algorithms for smoothed aggregationbased multigrid coarsening. In the proposed method, we use the geometry of the given discrete problem on the finest level to coarsen the system together with compatible relaxation to from the sparsity structure of the interpolation operator and then apply energy minimization techniques to compute its entries. Of particular interest in this work is the idea to use a geometric coarsening algorithm based on a new more sharp...

[Illinois] Hub Snub: Removing Vertices with High Degree from Coarsegrid Correction
04 Feb 2016  Online Presentations  Contributor(s): Geoffry Sanders
Network scientists often employ numerical solutions to linear systems as subroutines of data mining algorithms. Due to the illconditioned nature of the systems, obtaining solutions with standard iterative methods is often prohibitively costly; current research aims to automatically construct preconditioners that are optimally efficient and scalable for a very broad class of graph associated matrices and network topologies. Frequently, networks encountered have skewed degree distribution and...

[Illinois] On the Preconditioning of a HighOrder RDGbased AllSpeed NavierStokes Solver
04 Feb 2016  Online Presentations  Contributor(s): Brian Weston
We investigate the preconditioning of an allspeed NavierStokes solver, based on the orthogonalbasis Reconstructed Discontinuous Galerkin (RDG) space discretization, and integrated using a highorder fullyimplicit time discretization method. The work is motivated by applications in Additive Manufacturing (AM), requiring simulations of laserinduced powder melting with formation and subsequent solidification of liquid metal pools, with numerous numerically challenging issues. These include...

[Illinois] Is the Ideal Approximation Operator Always "Ideal" for a Particular C/F Splitting?
04 Feb 2016  Online Presentations  Contributor(s): Erin Molloy
Given a coarse grid, the ideal prolongation operator is defined by , where the weight matrix, , interpolates a set of fine grid variable (points) from a set of coarse grid variable (points), and the identity matrix, , represents the injection of points to and from the coarse grid (Falgout and Vassilevski, 2004). In this talk, we consider , constructed from both traditional splittings and splittings corresponding to aggregates, for...

[Illinois] Reducing Communication Costs for Sparse Matrix Multiplication within Algebraic Multigrid
04 Feb 2016  Online Presentations  Contributor(s): Grey Ballard
We consider the sequence of sparse matrixmatrix multiplications performed during the setup phase of algebraic multigrid. In particular, we show that the most commonly used parallel algorithm is often not the most communicationefficient one for all of the matrix multiplications involved. By using an alternative algorithm, we show that the communication costs are reduced (in theory and practice), and we demonstrate the performance benefit for both model and real problems on largescale...

[Illinois] Spacetime constrained FOSLS with AMGe upscaling
04 Feb 2016  Online Presentations  Contributor(s): Panayot Vassilevski
We consider timedependent PDEs discretized in combined spacetime domains. We first reduce the PDE to a first order system. Very often in practice, one of the equations of the reduced system involves the divergence operator (in spacetime). The popular FOSLS (first order system leastsquares) method is then applied modified by keeping the divergence equation as a constraint which we refer to as CFOSLS (constrained FOSLS). Applying finite elements to discretize the CFOSLS problem leads to a...

[Illinois] Multilevel Markov Chain Monte Carlo for Uncertainty Quantification in Subsurface Flow
04 Feb 2016  Online Presentations  Contributor(s): Christian Ketelsen
The multilevel Monte Carlo method has been shown to be an effective variance reduction technique for quantifying uncertainty in subsurface flow simulations when the random conductivity field can be represented by a simple prior distribution. In stateoftheart subsurface simulation the stochastic model of the conductivity field must be conditioned on observe physical data. Sampling from this complicated distribution is carried out by the Markov chain Monte Carlo method. In this talk we...

[Illinois] Discretization of Elliptic Differential Equations Using Sparse Grids and Prewavelets
04 Feb 2016  Online Presentations  Contributor(s): Christoph Pflaum
Sparse grids can be used to discretize second order elliptic differential equations on a ddimensional cube. Using Galerkin discretization, we obtain a linear equation system with unknowns. The corresponding discretization error is in the norm. A major difficulty in using this sparse grid discretization is complexity of the related stiffness matrix. Consequently, only differential equations with constant coefficients could be efficiently discretized using sparse...

[Illinois] High Dimensional Uncertainty Quantification via Multilevel Monte Carlo
04 Feb 2016  Online Presentations  Contributor(s): Hillary Fairbanks
Multilevel Monte Carlo (MLMC) has been shown to be a cost effective way to compute moments of desired quantities of interest in stochastic partial differential equations when the uncertainty in the data is highdimensional. In this talk, we investigate the improved performance of MLMC versus standard Monte Carlo. While both methods converge at a rate independent of the dimension of the stochastic input, the use of a series of nested grids in MLMC allows us to improve the convergence by...