Search

Algebraic multigrid (AMG) is one of the most widely used solution techniques for linear systems of equations arising from discretized partial differential equations. The popularity of AMG stems from its potential to solve linear systems in almost linear time, that is with an O(n) complexity, where n is the problem size. This capability is crucial at the present, where the increasing availability of massive HPC platforms pushes for the solution of very large problems. The key for a rapidly converging AMG method is a good interplay between the smoother and the coarse-grid correction, which in turn requires the use of an effective prolongation. From a theoretical viewpoint, the prolongation must accurately represent near kernel components and, at the same time, be bounded in the energy norm. For challenging problems, however, ensuring both these requirements is not easy and is exactly the goal of this work. We propose a constrained minimization procedure aimed at reducing prolongation energy while preserving the near kernel components in the span of interpolation. The proposed algorithm is based on previous energy minimization approaches utilizing a preconditioned restricted conjugate gradients method, but has new features and a specific focus on parallel performance and implementation. It is shown that the resulting solver, when used for large real-world problems from various application fields, exhibits excellent convergence rates and scalability and outperforms at least some more traditional AMG approaches. [ABSTRACT FROM AUTHOR]

The solution of linear systems of equations is a central task in a number of scientific and engineering applications. In many cases the solution of linear systems may take most of the simulation time thus representing a major bottleneck in the further development of scientific and technical software. For large scale simulations, nowadays accounting for several millions or even billions of unknowns, it is quite common to resort to preconditioned iterative solvers for exploiting their low memory requirements and, at least potential, parallelism. Approximate inverses have been shown to be robust and effective preconditioners in various contexts. In this work, we show how adaptive Factored Sparse Approximate Inverse (aFSAI), characterized by a very high degree of parallelism, can be successfully implemented on a distributed memory computer equipped with GPU accelerators. Taking advantage of GPUs in adaptive FSAI set-up is not a trivial task, nevertheless we show through an extensive numerical experimentation how the proposed approach outperforms more traditional preconditioners and results in a close-to-ideal behavior in challenging linear algebra problems. [ABSTRACT FROM AUTHOR]

The numerical simulation of physical systems has become in recent years a fundamental tool to perform analyses and predictions in several application fields, spanning from industry to the academy. As far as large-scale simulations are concerned, one of the most computationally expensive tasks is the solution of linear systems of equations arising from the discretization of the partial differential equations governing physical processes. This work presents Chronos, a collection of linear algebra functions specifically designed for the solution of large, sparse linear systems on massively parallel computers. Its emphasis is on modern, effective, and scalable Algebraic Multigrid (AMG) preconditioners for high performance computing (HPC). This work describes the numerical algorithms and the main structures of this software suite, especially from an implementation standpoint. Several numerical results arising from practical mechanics and fluid dynamics applications with hundreds of millions of unknowns are addressed and compared with other state-of-the-art linear solvers, proving Chronos's efficiency and robustness. [ABSTRACT FROM AUTHOR]

One of the most time-consuming tasks in the procedures for the numerical study of PDEs is the solution to linear systems of equations. To that purpose, iterative solvers are viewed as a promising alternative to direct methods on high-performance computers since, in theory, they are almost perfectly parallelizable. Their main drawback is the need of finding a suitable preconditioner to accelerate convergence. The factorized sparse approximate inverse (FSAI), mainly in its adaptive form, has proven to be an effective parallel preconditioner for several problems. In the present work, we report about two novel ideas to dynamically compute, on graphics processing units (GPUs), the FSAI sparsity pattern, which is the main task in its setup. The first approach, borrowed from the CPU implementation, uses a global array as a nonzero indicator, whereas the second one relies on a merge-sort procedure of multiple arrays. We will show that the second approach requires significantly less memory and overcomes issues related to the limited global memory available on GPUs. Numerical tests prove that the GPU implementation of FSAI allows for an average speed-up of 7.5 over a parallel CPU implementation. Moreover, we will show that the preconditioner computation is still feasible using single precision arithmetic with a further 20% reduction of the setup cost. Finally, the strong scalability of the overall approach in shown in a multi-GPU setting. [ABSTRACT FROM AUTHOR]

The numerical simulation of modern engineering problems can easily incorporate millions or even billions of unknowns. In several applications, sparse linear systems with symmetric positive definite matrices need to be solved, and algebraic multigrid (AMG) methods represent common choices for the role of iterative solvers or preconditioners. The reason for their popularity relies on the fast convergence that these methods provide even in the solution of large size problems, which is a consequence of the AMG ability to reduce particular error components across their multilevel hierarchy. Despite carrying the name "algebraic," most of these methods still make assumptions on additional information other than the global assembled matrix, such as the knowledge of the operator's near kernel, which limits their applicability as black-box solvers. In this work, we introduce a novel AMG approach featuring the adaptive factored sparse approximate inverse (aFSAI) method as a flexible smoother, as well as three new approaches to adaptively compute the prolongation operator. We assess the performance of the proposed AMG through the solution of a set of model problems along with real-world engineering test cases. Moreover, we perform comparisons to other methods such as the aFSAI and BoomerAMG preconditioners, showing that our new method proves to be superior to the first strategy and comparable to the second one, if not better, as in the solution of linear elasticity models. [ABSTRACT FROM AUTHOR]

The use of factorized sparse approximate inverse (FSAI) preconditioners in a standard multilevel framework for symmetric positive deFInite (SPD) matrices may pose a number of issues as to the deFIniteness of the Schur complement at each level. The present work introduces a robust multilevel approach for SPD problems based on FSAI preconditioning, which eliminates the chance of algorithmic breakdowns independently of the preconditioner sparsity. The multilevel FSAI algorithm is further enhanced by introducing descending and ascending low-rank corrections, thus giving rise to the multilevel FSAI with low-rank corrections (MFLR) preconditioner. The proposed algorithm is investigated in a number of test problems. The numerical results show that the MFLR preconditioner is a robust approach that can significantly accelerate the solver convergence rate preserving a good degree of parallelism. The possibly large set-up cost, mainly due to the computation of the eigenpairs needed by low-rank corrections, makes its use attractive in applications where the preconditioner can be recycled along a number of linear solves. [ABSTRACT FROM AUTHOR]

Graphics Processing Units (GPUs) exhibit significantly higher peak performance than conventional CPUs. However, in general only highly parallel algorithms can exploit their potential. In this scenario, the iterative solution to sparse linear systems of equations could be carried out quite efficiently on a GPU as it requires only matrix-by-vector products, dot products, and vector updates. However, to be really effective, any iterative solver needs to be properly preconditioned and this represents a major bottleneck for a successful GPU implementation. Due to its inherent parallelism, the factored sparse approximate inverse (FSAI) preconditioner represents an optimal candidate for the conjugate gradient-like solution of sparse linear systems. However, its GPU implementation requires a nontrivial recasting of multiple computational steps. We present our GPU version of the FSAI preconditioner along with a set of results that show how a noticeable speedup with respect to a highly tuned CPU counterpart is obtained. [ABSTRACT FROM AUTHOR]

In recent years the growing popularity of supercomputers has fostered the development of algorithms able to take advantage of the massive parallelism offered by multiple processors. Direct methods, though robust and computationally efficient, hardly exploit high degrees of parallelism. By contrast, Krylov methods preconditioned by Factored Sparse Approximate Inverses (FSAI) provide, at least in principle, a perfectly parallel approach but are often thwarted by an excessive set-up cost. In this paper we extend the concept of supernode from sparse LU factorizations to approximate inverses, and use it to accelerate the computation of an FSAI-type preconditioner. The numerical experiments on real-world problems show that the overall FSAI efficiency can be significantly increased while preserving its intrinsic parallelism. [ABSTRACT FROM AUTHOR]

The Factorized Sparse Approximate Inverse (FSAI) is an efficient technique for preconditioning parallel solvers of symmetric positive definite sparse linear systems. The key factor controlling FSAI efficiency is the identification of an appropriate nonzero pattern. Currently, several strategies have been proposed for building such a nonzero pattern, using both static and dynamic techniques. This article describes a fresh software package, called FSAIPACK, which we developed for shared memory parallel machines. It collects all available algorithms for computing FSAI preconditioners. FSAIPACK allows for combining different techniques according to any specified strategy, hence enabling the user to thoroughly exploit the potential of each preconditioner, in solving any peculiar problem. FSAIPACK is freely available as a compiled library at http://www.dmsa.unipd.it/~janna/software.html, together with an open-source command language interpreter. By writing a command ASCII file, one can easily perform and test any given strategy for building an FSAI preconditioner. Numerical experiments are discussed in order to highlight the FSAIPACK features and evaluate its computational performance. [ABSTRACT FROM AUTHOR]

Adaptive block factorized sparse approximate inverse (FSAI) (ABF) is a novel algebraic preconditioner for the cost-effective parallel solution of symmetric positive definite linear systems. However, a main drawback stems from its reduced scalability, as the iteration count to convergence tends to grow when the number of processors increases. A domain decomposition Schur complement approach can enhance both the ABF performance and scalability. It is demonstrated that the enhanced ABF preconditioner is superior to the native block FSAI, reducing at the same time the construction and communication computational burden. Numerical results from different large size applications show that the proposed algorithm can improve significantly the preconditioner, allowing for its efficient use in massively parallel simulations as well. [ABSTRACT FROM AUTHOR]

Abstract: The Finite Element Method (FEM) is widely used in civil and mechanical engineering to simulate the behavior of complex structures and, more specifically, to predict stress and deformation fields of structural parts or mechanical bodies. In the former case, the coupling between different types of elements, such as beams, trusses, and shells, is often required, while in the latter fully 3D discretizations are typically used. For both, FEM leads to symmetric positive definite (SPD) matrices that, depending on the type of discretization and especially on the topology of the nodal connections, may be efficiently solved by either the Preconditioned Conjugate Gradient (PCG) or a direct solver such as the routine MA57 of the Harwell Software Library. Numerical experiments are shown and discussed where the effect of spatial discretization, different solution techniques, and a possible nodal reordering, is explored. The PCG preconditioner used is a variant of the incomplete Cholesky factorization with variable fill-in. It is shown that for structures with 1D or 2D connections, such as for example a bridge, MA57 performs usually better than PCG. In this case it is noted that some reorderings specifically designed and implemented for direct elimination methods can be very helpful for PCG as well as they yield a cheaper preconditioner and lead to a much faster PCG convergence. The main disadvantage is the need for an appropriate degree of fill-in for the preconditioner which turns out to be problem dependent and must be found empirically. However, in fully 3D problems, arising for example from the FE discretization of structural components or geomechanical structures, PCG outperforms MA57 while also requiring much less memory, and thus allowing for the use of much refined grids, if needed. With the aid of a large geomechanical problem it is shown that direct solvers may not be (even) used on serial computers due to their prohibitive computational cost with PCG the only viable alternative solver. [Copyright &y& Elsevier]

Abstract: Contact mechanics can be addressed numerically by finite elements using either a penalty formulation or the Lagrange multipliers. The penalty approach leads to a linearized symmetric positive definite system which can prove severely ill-conditioned, with the iterative solution to large 3D problems requiring expensive preconditioners to accelerate, or even to allow for, convergence. In the present paper a mixed constraint preconditioner (MCP) is developed and implemented for the iterative solution of contact problems based on the penalty approach. A theoretical bound for the eigenspectrum of the preconditioned matrix is provided depending on the user-specified parameters that control the preconditioner fill-in. The performance of MCP combined with the preconditioned conjugate gradient is studied in two real 3D test cases describing the geomechanics of faulted porous media and compared to a well-established preconditioner such as the incomplete Cholesky decomposition ILLT with optimal fill-in. Numerical results show that typically MCP outperforms ILLT especially in the most challenging problems where very large penalty parameters must be used. Finally, a modification aimed at simplifying the MCP implementation and increasing its robustness is developed and experimented with, showing that the modified MCP can be viewed as an efficient and viable alternative to both MCP and ILLT, especially in problems where the size of the contact surfaces is large with respect to the global domain. [Copyright &y& Elsevier]

This work discusses a general approach for preconditioning the block Jacobian matrix arising from the discretization and linearization of coupled multiphysics problem. The objective is to provide a fully algebraic framework that can be employed as a starting point for the development of specialized algorithms exploiting unique features of the specific problem at hand. The basic idea relies on approximately computing an operator able to decouple the different processes, which can then be solved independently one from the other. In this work, the decoupling operator is computed by extending the theory of block sparse approximate inverses. The proposed approach is implemented for two multiphysics applications, namely the simulation of a coupled poromechanical system and the mechanics of fractured media. The numerical results obtained in experiments taken from real-world examples are used to analyze and discuss the properties of the preconditioner. • A general framework is introduced for the block preconditioning of discrete systems arising from coupled multi-physics applications. • A decoupling operator is introduced by using the theory of block sparse approximate inverse preconditioners. • The framework is specialized for two applications: (i) coupled poromechanics, (ii) mechanics of fractured media. • Specific techniques for preserving the definiteness of the Schur complements are introduced for each application. • The preconditioners arising from the proposed general framework are used to solve real-world demanding applications. [ABSTRACT FROM AUTHOR]

The numerical simulation of structural mechanics applications via finite elements usually requires the solution of large-size linear systems, especially when accurate results are sought for derived variables, like stress or deformation fields. Such a task represents the most time-consuming kernel, and motivates the development of robust and efficient linear solvers for these applications. On the one hand, direct solvers are robust and easy to use, but their computational complexity in the best scenario is superlinear, which limits applicability according to the problem size. On the other hand, iterative solvers, in particular those based on algebraic multigrid (AMG) preconditioners, can reach up to linear complexity, but require more knowledge from the user for an efficient setup, and convergence is not always guaranteed, especially in ill-conditioned problems. In this work, we present a novel AMG method specifically tailored for ill-conditioned structural problems. It is characterized by an adaptive factored sparse approximate inverse (aFSAI) method as smoother, an improved least-squared based prolongation (DPLS) and a method for uncovering the near-null space that takes advantage of an already existing approximation. The resulting linear solver has been applied in the solution of challenging linear systems arising from real-world linear elastic structural problems. Numerical experiments prove the efficiency and robustness of the method and show how, in several cases, the proposed algorithm outperforms state-of-the-art AMG linear solvers. Even more important, the results show how the proposed method gives good results even assuming a default setup, making it fully adoptable also for non-expert users and commercial software. • An Adaptive AMG linear solver for ill-conditioned structural problems is presented. • Results on more than 10 realistic examples prove its robustness and high efficiency. • Its performance is comparable or superior to other renowned state-of-art solvers. • It does not require tuning of user-parameters to achieve excellent performances. [ABSTRACT FROM AUTHOR]