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]

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]

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]

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]