James J. Brannick - US grants

Proposal Title: Collaborative Research: Multigrid QCD at the Petascale
Institution: Trustees of Boston University
Abstract Date: 10/10/07
0749300
Brower
0749202
Brannick
0749317
McCormick
Numerical solutions to Quantum Chromodynamcs on a lattice are critical to high
precision experimental tests of the standard model and an ab-initio understanding of
nuclear matter. The core of these calculations involves inverting a Dirac matrix which
becomes increasingly ill conditioned as the lattice is refined. Consequently while
Terascale computing hardware has exposed this new physics, it is incapable of fully
accommodating it. On the other hand, if lattice QCD algorithms are reformulated to
exploit and reveal the physics at this finer microsale, Petascale hardware does have the
potential for opening up a new era of physics discovery. This award brings together a
close collaboration of leading experts in applied mathematics and theoretical physics to
meet this challenge by the application of new multi-level algorithms for QCD
simulations. The central mission of the proposed Multigrid Quantum
Chromodynamics at the Petascale project (MGQCD) is: to develop new and significantly
more robust multigrid methods for enabling more complex and higher fidelity physics for
lattice QCD calculations; to support their migration into Petascale simulations; and to
engage the broader scientific community through collaborative research and
educational activities that highlight the multigrid methodology.
NATIONAL SCIENCE FOUNDATION
Proposal Abstract

The primary goal of this collaborative proposal is to develop
theoretically based algebraic multigrid (AMG) solvers for Hermitian
(and, where possible, non-Hermitian) positive-definite problems. The
team aims to improve understanding of the performance of the family of
AMG algorithms and, with this improved knowledge, to develop AMG
methods that offer provable, computable, a priori information on the
algorithm's performance. The project team represents a close
collaboration of experts in this area, each of whom has made
contributions in the field. Over the past several years, the team has
begun to work collectively on developing new multilevel solvers and
rigorous theoretical results for the convergence and complexity
analysis thereof. Together, the team will have the capability to take
a step toward answering some of the fundamental research questions
associated with these two essential aspects of the analysis and design
of efficient algorithms.

We expect the work proposed here to: (1) directly impact computational
simulation codes currently employing multi-level solvers, by providing
faster and more reliable computational tools for the numerical
computations at the core of physical simulations; and (2) allow for
simulation of phenomena for which suitable solvers are currently
unavailable. The results from the proposed research will, thus, have
a direct impact on scientific and engineering problems, including
those from energy, through both the simulation of particle physics and
processing of data from oil reservoir models, biophysics, in surgical
simulation, and the environment, in climate prediction and contaminant
remediation models. The algorithms to be investigated here are
already in use in many of these fields, but are often considered to be
"expert-only" tools. The goal of this proposal is to develop more
reliable and robust versions of these tools. The proposed research
will have a strong educational impact as well, as it provides for a
solid base for training of graduate students in the modern theoretical
and practical aspects of numerical methods for modeling of
applications arising in science and engineering.

The most common origin and manifestation of anomalous phenomena in complex fluids are different ``elastic'' effects. These can be ascribed to the elasticity of deformable particles, elastic repulsion between charged liquid crystals, polarization of colloids or multi-component phases, elastic effects due to microstructures formation, or bulk elastic effects due to the presence of polymer molecules in viscoelastic complex fluids. Mathematically, such elastic effects can be represented in terms of internal variables. Examples of such internal variables are: the orientational order parameter in liquid crystals, the distribution density function in the dumb-bell model for polymeric materials, the magnetic field in magnetohydrodynamic fluids, and the volume fraction in mixtures of different materials. The different rheological and hydrodynamic properties of these materials can in turn be attributed to the special coupling between the transport of these internal variables and the induced elastic stresses which typically manifest on all scales, and to a large extent determine the specific properties of the system, such as the stability and regularity of particle configurations and the likelihood of specific pattern formations in the system. The understanding of such complex mechanisms which couple different physical scales is crucial in designing accurate mathematical and numerical models and algorithms in order to simulate such systems. This workshop is based on the premise that gaining significant new results and thereby obtaining deeper insight and understanding of materials described by complex fluids (e.g., polymers, emulsions, liquid crystals, magnetorheological fluids, blood suspensions) requires a combined approach consisting of experiment, modeling, analysis, and simulation. The primary objective of the workshop is thus to gather students, junior faculty, and experts to discuss new integrated modeling techniques that properly address the fundamental unresolved issues common to studies of complex fluids: consistency of models with physics, rigorous analysis of the models, numerical and scientific computing issues, and the experimental verification and validation of the predictive capabilities of the mathematical and numerical models.

Modeling and simulating the rich pool of designer and smart materials described by complex fluids requires marshaling interdisciplinary research forces to develop and analyze mathematical models and computational tools for such problems. Recently, numerous methodologies and frameworks have been developed in an aim to capture the various time and length scales involved in studies of such complex materials. This workshop will gather key contributors to the development of these new multiscale modeling and simulations techniques, with the aim of introducing these ideas to students and young researchers and also promoting interdisciplinary research on complex fluids applications amongst participants in the future. The workshop will highlight topics from interrelated research areas for both deterministic and stochastic computational approaches, concentrating on: an Energetic Variational approach for multiscale modeling and simulation; computationally and experimentally guided model validation and further development of robust adaptive numerical models and solution methods.

The goal of this project is to develop and study a special class of multilevel methods that combine techniques from the Geometric Multigrid (GMG) and Algebraic Multigrid (AMG) methodologies, which we refer to as the "single-grid multilevel method" (SGML). The focus is discretized partial differential equations, for which detailed information on the underlying geometric grid is generally available to the user. The research team is designing solvers that use information from the finest grid (hence termed the single-grid method) to select a simple and fixed coarsening that allows for explicit control of the overall grid and operator complexities of the multilevel solver. The central new idea that we are investigating concerns the design and analysis of algorithms for adaptive construction of the MG relaxation scheme when used as a smoother. In contrast to existing AMG methods, in which the smoother is fixed and coarsening is the key component in the setup phase, SGML will construct the smoother in the setup phase to complement its simple geometry-based coarsening process. It should be noted that the algebraic construction of the smoother can also benefit from using properties of the geometric grid, for example, to obtain a suitable partitioning of the unknowns in parallel. The SGML approach (together with the many of the promising algebraic techniques for constructing the MG interpolations developed over the last decade) is also under consideration. The PI and co-PIs, though, are focusing on the SGML method because of its ability to explicitly control complexity, which in turn allows for (nearly) optimal load balancing and predictable communication patterns, such that the method is well suited for parallel computing.

Overall, the iterative solvers under development are designed to be implemented in open source parallel codes and made available to the scientific computing community. This will provide a computational framework for future algorithm research and development in related areas as well as powerful tools for simulation. In summary, the proposed methodology constructs solvers using all the information available to increase the efficiency of numerical modeling and simulation of physical phenomena on parallel multi-core computing architectures. Educational activities include the training of graduate students.

The goal of this research project is to combine ideas from the finite element and multigrid methodologies in order to develop an adaptive algebraic multigrid algorithmic framework with the potential to make an appreciable and broad impact on computational Quantum Chromodynamics (QCD). The proposed research is driven by three specific interrelated research goals: (1) To render the Galerkin adaptive algebraic multigrid methods currently being used to solve the Wilson-Dirac system more robust and more efficient; (2) To design and analyze new Petrov-Galerkin multigrid methods for solving the domain wall fermion system; (3) To discover and analyze relationships between lattice field theory and the rich theory that researchers have developed for the finite element method. This research encompasses a broad range of fundamental research in algebraic multigrid methods, including the design and analysis of new multigrid smoothers based on greedy (randomized) subspace correction methods, randomized methods for range approximation, adaptive multigrid methods for solving non-hermitian problems, and multilevel methods for computing eigenpairs and singular value triplets.

The intellectual merit of this project derives from its potential to make several distinct mathematical advances and to integrate those advances into multilevel algorithms and software for large-scale QCD applications. These advances are expected to significantly reduce the errors that arise in lattice calculations and, in turn, to make it possible to use simulations to test the full non-linearities of QCD and confront experimental data with ab initio predictions. The project's potential to make a broader impact will be realized by applying the proposed algorithmic solutions to a wide range of problems in areas beyond the primary focus on fundamental investigations into particle physics, such as lattice field theories of graphene, models involving Maxwell's equations, e.g., magnetohydrodynamics, large-scale graph applications, e.g., Markov chains as arise in various Stochastic models, and partial differential equations with random coefficients, as arise, for example, in uncertainty quantification for groundwater flow. Graduate students involved in the project will engage in interdisciplinary research led by the PI and have opportunities to visit and work with multiple collaborators from the US and Europe, such that they will receive advanced training in both the theory and practice of advanced mathematical algorithms and high-end scientific computing.

This grant supports travel of US researchers to attend the workshop on "Mutilevel methods and Optimization" from April 29 to May 2, 2013, at the Weizmann Institute of Science in Rehovot, Israel. The planned talks and panel discussions will cover classical problems such as partial differential equations, together with modern tasks such as web search and data mining. Speakers and participants in the workshop come from a variety of disciplines, including physics, biology, chemistry, economics, environment and earth sciences, computer science and engineering. A special two-hour panel "Challenges in Multilevel Computation: where should we be directing our efforts and our graduate students?" is planned for the second day.

Multilevel solution methods for simulation and optimization problems over very large number of variables is central and important to virtually all disciplines in the sciences and engineering. These methodologies are very powerful because they exploit the fact that most computational problems have multiple scales. This notion of multiple scales may take on many different guises, including time and space, pixels, particles, proteins, or web-pages. This multiplicity and disparity of scales is an essential source of computational complexity. The multilevel algorithms address the problem under consideration at a hierarchy of scales, typically treating each with a method that is local to that particular scale. The proposed workshop will bring together junior researchers and world-class experts, mainly from North America, Western Europe, and Israel, to exhibit and discuss their recent research on multilevel computational methods for simulation and optimization in a wide variety of topics and applications. Together, the diverse backgrounds of the participants in the workshop and the planned activities are expected to expose new research directions in multilevel computational methods and to identify the most pressing challenges in this diverse field.

The primary goal of this project is to develop a bootstrap multigrid algorithmic framework that has the potential to make an appreciable and broad impact on computational methods for numerically solving partial differential equations (PDEs). The intellectual merit of the project derives from its potential to make several distinct theoretical advances in the design and analysis of geometric and algebraic multigrid methods and to integrate those advances into algorithms and software for large-scale scientific applications that require solving coupled PDE systems and PDE eigenvalue problems. The broader impact of the project will be realized by applying these new algorithms to various problems in science and engineering. The graduate student and post doc involved in the project will engage in interdisciplinary research led by the PI and will have opportunities to visit and work with colleagues from industry and DOE labs.

This research project builds on recent advances by the PI in the development of multigrid solvers for systems of and PDE eigenvalue problems: (1) the successful development of adaptive and bootstrap algebraic multigrid as fast solvers for the Wilson-Dirac and Wilson-clover discretizations of the coupled Dirac PDE in lattice quantum chromodynamics (QCD); (2) the design and analysis of a robust bootstrap MG solver for the Laplace-Beltrami eigenvalue problem. Specifically, the project team will focus on two interrelated research goals: (1) to extend the bootstrap algebraic MG methods currently being used to solve various discretizations of the Dirac PDE to a general approach for solving systems of coupled PDEs and generalized algebraic eigenvalue problems; (2) to design and analyze new finite element bootstrap MG methods for solving PDE eigenvalue problems on surfaces.

Computer simulations and the mathematical methods supporting these are central to the modern study of engineering, biology, chemistry, physics, and other fields. Many simulations are computationally costly and require the large resources of modern supercomputers. New mathematical methods are urgently needed to efficiently utilize next generation supercomputers with millions to billions of processors. This project will develop new parallel-in-time algebraic multigrid methods for complex physical systems specifically designed for next generation computers. These new methods will add a new dimension of parallel scalability (time) and promise dramatically faster simulations in many important application areas, such as the gas and fluid dynamics problems considered (e.g., with relevance to wind turbines and viscoelastic flow). Graduate students will be involved and trained, and open source code will be developed.

This project will develop fast, parallel, and flexible space-time solvers for systems of partial differential equations (PDEs). The project will focus on algebraic multigrid (AMG) within block preconditioning traditionally appropriate for large adaptively refined spatial systems. These techniques will be extended to general space-time systems with a flexible approach that allows for adaptive space-time refinement. This adaptivity helps to accurately resolve lower dimensional features such as shocks at a fraction of the cost and storage of uniform refinement. Furthermore, the project will produce new practical AMG theory for non-SPD (symmetric positive definite) problems as well as solvers for adaptively refined space-time discretizations for a variety of parabolic and hyperbolic PDEs including the Euler and Navier-Stokes equations and Cahn-Hilliard system. The project will design, analyze, and tune parallel AMG solvers that are robust, efficient, and fast over a wide range of PDEs and parameters and will contribute to the widely used packages MFEM and hypre. The solvers will be developed and tested for applications in wind turbines, as well the high Weissenberg number problem in viscoelastic flows.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.