Sparse solvers are one of the building blocks of any technology for reliable and high-performance scientific and engineering computing. In this paper we present a software package which implements an efficient multigrid sparse solver running on Graphics Processing Units. The package is a branch of a wider initiative of software development for sparse Linear Algebra computations on emergent HPC architectures involving a large research group working in many application projects over the last ten years.

Linear solvers for large and sparse systems are a key element of scientific applications, and their efficient implementation is necessary to harness the computational power of current computers. Algebraic Multigrid (AMG) Preconditioners are a popular ingredient of such linear solvers; this is the motivation for the present work where we examine some recent developments in a package of AMG preconditioners to improve efficiency, scalability, and robustness on extreme-scale problems. The main novelty is the design and implementation of a new parallel coarsening algorithm based on aggregation of unknowns employing weighted graph matching techniques; this is a completely automated procedure, requiring no information from the user, and applicable to general symmetric positive definite (s.p.d.) matrices. The new coarsening algorithm improves in terms of numerical scalability at low operator complexity over decoupled aggregation algorithms available in previous releases of the package. The preconditioners package is built on the parallel software framework PSBLAS, which has also been updated to progress towards exascale. We present weak scalability results on two of the most powerful supercomputers in Europe, for linear systems with sizes up to O(10^10) unknowns.

Many scientific applications require the solution of large and sparse linear systems of equations using Krylov subspace methods; in this case, the choice of an effective preconditioner may be crucial for the convergence of the Krylov solver. Algebraic MultiGrid (AMG) methods are widely used as preconditioners, because of their optimal computational cost and their algorithmic scalability. The wide availability of GPUs, now found in many of the fastest supercomputers, poses the problem of implementing efficiently these methods on high-throughput processors. In this work we focus on the application phase of AMG preconditioners, and in particular on the choice and implementation of smoothers and coarsest-level solvers capable of exploiting the computational power of clusters of GPUs. We consider block-Jacobi smoothers using sparse approximate inverses in the solve phase associated with the local blocks. The choice of approximate inverses instead of sparse matrix factorizations is driven by the large amount of parallelism exposed by the matrix-vector product as compared to the solution of large triangular systems on GPUs. The selected smoothers and solvers are implemented within the AMG preconditioning framework provided by the MLD2P4 library, using suitable sparse matrix data structures from the PSBLAS library. Their behaviour is illustrated in terms of execution speed and scalability, on a test case concerning groundwater modelling, provided by the Julich Supercomputing Center within the Horizon 2020 Project EoCoE.

Graph Laplacian is a popular tool for analyzing graphs, in particular in graph partitioning and clustering. Given a notion of similarity (via an adjacency matrix), graph clustering refers to identifying different groups such that vertices in the same group are more similar compared to vertices across different groups. Data clustering can be reformulated in terms of a graph clustering problem when the given set of data is represented as a graph, also known as similarity graph. In this context, eigenvectors of the graph Laplacian are often used to obtain a new geometric representation of the original data set which generally enhances cluster properties and improves cluster detection. In this work, we apply a bootstrap Algebraic MultiGrid (AMG) method which constructs a set of vectors associated with the graph Laplacian. These vectors, referred to as algebraically smooth ones, span a low-dimensional euclidean space, which we use to represent the data, enabling cluster detection both in synthetic and in realistic well-clustered graphs. We show that in the case of a good quality bootstrap AMG, the computed smooth vectors employed in the construction of the final AMG operator, which by construction is spectrally equivalent to the originally given graph Laplacian, accurately approximate the space in the lower portion of the spectrum of the preconditioned operator. Thus, our approach can be viewed as a spectral clustering technique associated with the generalized spectral problem (Laplace operator versus the final AMG operator), and hence it can be seen as an extension of the classical spectral clustering which employs a standard eigenvalue problem.

This paper proposes improving the solve time of a bootstrap algebraic multigrid (AMG) designed previously by the authors. This is achieved by incorporating the information, a set of algebraically smooth vectors, generated by the bootstrap algorithm, in a single hierarchy by using sufficiently large aggregates, and these aggregates are compositions of aggregates already built throughout the bootstrap algorithm. The modified AMG method has good convergence properties and shows significant reduction in both memory and solve time. These savings with respect to the original bootstrap AMG are illustrated on some difficult (for standard AMG) linear systems arising from discretization of scalar and vector function elliptic partial differential equations in both 2D and 3D.

Editorial Introduction of a special issue

This paper has two main objectives: one is to describe some extensions of an adaptive Algebraic Multigrid (AMG) method of the form previously proposed by the first and third authors, and a second one is to present a new software framework, named BootCMatch, which implements all the components needed to build and apply the described adaptive AMG both as stand-alone solver and as preconditioner in a Krylov method. The adaptive AMG presented is meant to handle general symmetric and positive definite (SPD) sparse linear systems, without assuming any a priori information of the problem and its origin; the goal of adaptivity is to achieve a method with a prescribed convergence rate. The presented method exploits a general coarsening process based on aggregation of unknowns, obtained by a maximum weight matching in the adjacency graph of the system matrix. More specifically, a maximum product matching is employed to define an effective smoother subspace (complementary to the coarse space), a process referred to as compatible relaxation, at every level of the recursive two-level hierarchical AMG process. Results on a large variety of test cases and comparisons with related work demonstrate the reliability and efficiency of the method and of the software.

We focus on the extension of the MLD2P4 package of parallel Algebraic MultiGrid (AMG) preconditioners, with the objective of improving its robustness and efficiency when dealing with sparse linear systems arising from anisotropic PDE problems on general meshes. We present a parallel implemen- tation of a new coarsening algorithm for symmetric positive definite matrices, which is based on a weighted matching approach. We discuss preliminary re- sults obtained by combining this coarsening strategy with the AMG components available in MLD2P4, on linear systems arising from applications considered in the Horizon 2020 Project "Energy oriented Centre of Excellence for computing applications" (EoCoE).

This presentation describes activities developed by CNR within EoCoE

Computing eigenvectors of graph Laplacian is a main computational kernel in data clustering, i.e., in identifying different groups such that data in the same group are similar and points in different groups are dissimilar with respect to a given notion of similarity. Data clustering can be reformulated in terms of a graph partitioning problem when the given set of data is represented as a graph, also known as similarity graph. In this context, eigenvectors of the graph Laplacian are used to obtain a new geometric representation of the original data set which generally enhances cluster properties and improves cluster detection. In this work we apply a bootstrap Algebraic MultiGrid (AMG) method to compute an approximation of the eigenvectors corresponding to small eigenvalues of the graph Laplacian and analyse their ability to catch clusters both in synthetic and in realistic graphs.

This paper proposed improving the solve time of the bootstrap AMG proposed previously by the authors. This is achieved by incorporating the information, set of algebraically smooth vectors, generated by the bootstrap algorithm, in a single hierarchy by using sufficiently large aggregates, and these aggregates are compositions of aggregates already built throughout the bootstrap algorithm. The modified AMG method has comparable convergence properties to the original bootstrap one, however with better efficiency. The improvement in solve time with respect to the original bootstrap AMG is illustrated on some difficult linear systems arising from discretization of vector function elliptic Partial Differential Equations (PDEs) in both 2d and 3d.

Software package in C

Midterm Working Report for EoCoE Project

Release 2.1 of MLD2P4 package

This poster describes some activities developed by CNR and its third party within EoCoE