Fulbright College of Arts & Sciences

Monday, April 5, 2021

The Impact of Computer Architectures on the Design of Algebraic Multigrid Methods

Ulrike Yang (Lawrence Livermore National Laboratory)

Algebraic multigrid (AMG) is a popular iterative solver and preconditioner for large sparse linear systems. When designed well, it is algorithmically scalable, enabling it to solve increasingly larger systems efficiently. While it consists of various highly parallel building blocks, the original method also consisted of various highly sequential components. A large amount of research has been performed over several decades to design new components that perform well on high performance computers. As a matter of fact, AMG has shown to scale well to more than a million processes. However, with single-core speeds plateauing, future increases in computing performance need to rely on more complicated, often heterogenous computer architectures, which provide new challenges for efficient implementations of AMG. To meet these challenges and yield fast and efficient performance, solvers need to exhibit extreme levels of parallelism, and minimize data movement. In this talk, we will give an overview on how AMG has been impacted by the various architectures of high-performance computers to date and discuss our current efforts to continue to achieve good performance on emerging computer architectures.

Preconditioned Iterative Methods for Linear Systems

Edmond Chow (Georgia Institute of Technology)

Iterative methods for the solution of linear systems of equations – such as stationery, semi-iterative, and Krylov subspace methods – are classical methods taught in numerical analysis courses, but adapting these methods to run efficiently at large-scale on high-performance computers is challenging and a constantly evolving topic. Preconditioners – necessary to aid the convergence of iterative methods – come in many forms, from algebraic to physics-based, are regularly being developed for linear systems from different classes of problems, and similarly are evolving with high-performance computers. This lecture will cover the background and some recent developments on iterative methods and preconditioning in the context of high-performance parallel computers. Topics include asynchronous iterative methods that avoid the potentially high synchronization cost where there are very large numbers of computational threads, parallel sparse approximate inverse preconditioners, parallel incomplete factorization preconditioners and sparse triangular solvers, and preconditioning with hierarchical rank-structured matrices for kernel matrix equations.

 Harnessing the Power of Mathematics for High Performance Computing

Public Lecturer: Ann Almgren (Lawrence Livermore National Lab)

Mathematics has always played a critical role in scientific discovery through computing. The increasing power and heterogeneity of modern computer architectures provide the opportunity to understand physical systems with higher and higher fidelity.  But as the range of length and time scales we want to probe becomes ever greater and the number of different types of physical processes we need to model becomes larger and more varied, the challenge of building effective simulation methodologies grows along with the opportunities.  Mathematics provides the key to meeting this challenge.  It allows us to decompose complex problems into their core elements and express how these elements are coupled. It allows us to abstract physical processes into equations and design algorithms to solve them. In addition, casting problems in the language of mathematics exposes the commonality between diverse applications. Exploiting this commonality enables us to capture complex algorithms in efficient high-performance software that provides building blocks for new algorithmic exploration and scientific discovery.

Tuesday, April 6, 2021

Recent Advances in Solving Large Systems of Linear Equations

Laura Grigori (Institut National de Recherche en Informatique et an Automatique (INRIA))

This talk will focus on recent advances in solving large linear systems of equations by using multilevel domain decomposition techniques and randomization.  We describe a multilevel technique based on Geneo that allows to bound the condition number of the preconditioned matrix and thus leads to a fast and robust convergence of an iterative method.  We then discuss randomization techniques for solving linear systems of equations by using GMRES.  These techniques are based on parallel sketching and a randomized Gram-Schmidt orthogonalization process.

This is joint work with H. Al Daas, O. Balabanov, M. Beaupère, P. Jolivet, P.-H. Tournier.

 The Road to Exascale and Legacy Software for Dense Linear Algebra

Jack Dongarra (University of Tennessee, Oak Ridge National Laboratory, and University of Manchester)

In this talk, we will look at the current state of high performance computing and look at the next stage of extreme computing. With extreme computing, there will be fundamental changes in the character of floating point arithmetic and data movement. In this talk, we will look at how extreme-scale computing has caused algorithm and software developers to change their way of thinking on implementing and program-specific applications.

Wednesday, April 7, 2021

Nonlinear Preconditioning Methods and Applications

Xiao-Chuan Cai (University of Macau and University of Colorado-Boulder)

We consider solving system of nonlinear algebraic equations arising from the discretization of partial differential equations. Inexact Newton is a popular technique for such problems. When the nonlinearities in the system are well-balanced, Newton's method works well, but when a small number of nonlinear functions in the system are much more nonlinear than the others, Newton may converge slowly or even stagnate. In such a situation, we introduce some nonlinear preconditioners to balance the nonlinearities in the system. The preconditioners are often constructed using a combination of some domain decomposition methods and nonlinear elimination methods. For the nonlinearly preconditioned problem, we show that fast convergence can be restored. In this talk we first review the basic algorithms, and then discuss some recent progress in the applications of nonlinear preconditioners for some difficult problems arising in computational mechanics including both fluid dynamics and solid mechanics.

 Recent Advances in Time Integration Methods and How They Can Enable Exascale Simulations

Carol Woodward (Lawrence Livermore National Laboratory)

To prepare for exascale systems, scientific simulations are growing in physical realism and thus complexity.  This increase often results in additional and changing time scales. Time integration methods are critical to efficient solution of these multiphysics systems.  Yet, many large-scale applications have not fully embraced modern time integration methods nor efficient software implementations.  Hence, achieving temporal accuracy with new and complex simulations has proved challenging.  We will overview recent advances in time integration methods, including additive IMEX methods, multirate methods, and parallel-in-time approaches, expected to help realize the potential of exascale systems on multiphysics simulations.  Efficient execution of these methods relies, in turn, on efficient algebraic solvers, and we will discuss the relationships between integrators and solvers.  In addition, an effective time integration approach is not complete without efficient software, and we will discuss effective software design approaches for time integrators and their uses in application codes.  Lastly, examples demonstrating some of these new methods and their implementations will be presented.

This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344.  LLNL-ABS- 819501.

Thursday, April 8, 2021

Thick-Restart Lanczos with Explicit External Deflation for Computing Many Eigenpairs and its Communication-Avoiding Variant

Zhaojun Bai (University of California-Davis)

There are continual and compelling needs for computing many eigenpairs of very large Hermitian matrix in physical simulations and data analysis. Though the Lanczos method is effective for computing a few eigenvalues, it can be expensive for computing a large number of eigenvalues. To improve the performance of the Lanczos method, in this talk, we will present a combination of explicit external deflation (EED) with an s-step variant of thick-restart Lanczos (s-step TRLan). The s-step Lanczos method can achieve an order of s reduction in data movement while the EED enables to compute eigenpairs in batches along with a number of other advantages.

 A low-rank factorization framework for building scalable algebraic solvers and preconditioners

Sherry Li (Lawrence Berkeley National Laboratory)

Factorization based preconditioning algorithms, most notably incomplete LU (ILU) factorization, have been shown to be robust and applicable to wide ranges of problems. However, traditional ILU algorithms are not amenable to scalable implementation. In recent years, we have seen a lot of investigations using low-rank compression techniques to build approximate factorizations.
A key to achieving lower complexity is the use of hierarchical matrix algebra, stemming from the H-matrix research. In addition, the multilevel algorithm paradigm provides a good vehicle for a scalable implementation. The goal of this lecture is to give an overview of the various hierarchical matrix formats, such as hierarchically semi-separable matrix (HSS), hierarchically off-diagonal low-rank matrix (HODLR) and Butterfly matrix, and explain the algorithm differences and approximation quality. We will illustrate many practical issues of these algorithms using our parallel libraries STRUMPACK and ButterflyPACK, and demonstrate their effectiveness and scalability while solving the very challenging problems, such as high frequency wave equations.

Friday, April 9, 2021

Hierarchically Low Rank and Kroenecker Methods

Rio Yokota (Tokyo Institute of Technology)

Exploiting structures of matrices goes beyond identifying their non-zero patterns. In many cases, dense full-rank matrices have low-rank submatrices that can be exploited to construct fast approximate algorithms. In other cases, dense matrices can be decomposed into Kronecker factors that are much smaller than the original matrix. Sparsity is a consequence of the connectivity of the underlying geometry (mesh, graph, interaction list, etc.), whereas the rank-deficiency of submatrices is closely related to the distance within this underlying geometry. For high dimensional geometry encountered in data science applications, the curse of dimensionality poses a challenge for rank-structured approaches. On the other hand, models in data science that are formulated as a composition of functions, lead to a Kronecker product structure that yields a different kind of fast algorithm. In this lecture, we will look at some examples of when rank structure and Kronecker structure can be useful.

 Randomized Algorithms for Least Squares Problems

Ilse Ipsen (North Carolina State University)

The emergence of massive data sets, over the past twenty or so years, has lead to the development of Randomized Numerical Linear Algebra. Randomized matrix algorithms perform random sketching and sampling of rows or columns, in order to reduce the problem dimension or compute low-rank approximations. We review randomized algorithms for the solution of least squares/regression problems, based on row sketching from the left, or column sketching from the right. These algorithms tend to be efficient and accurate on matrices that have many more rows than columns. We present probabilistic bounds for the amount of sampling required to achieve a user-specified error tolerance. Along the way we illustrate important concepts from numerical analysis (conditioning and pre-conditioning), probability (coherence, concentration inequalities), and statistics (sampling and leverage scores). Numerical experiments illustrate that the bounds are informative even for small problem dimensions and stringent success probabilities. To stress-test the bounds, we present algorithms that generate 'adversarial' matrices' for user-specified coherence and leverage scores. If time permits, we discuss the additional effect of uncertainties from the underlying Gaussian linear model in a regression problem.