SAMG – Efficiently solving large Linear Systems of Equations

Benefits:

  • Library of subroutines for the highly efficient solution of large linear equations

    The calculation effort with SAMG is only linearly dependent on the number of unknowns.
 

Library SAMG

SAMG (Algebraic Multigrid Processes for Systems) is a library of subroutines for the highly efficient solution of large linear equations systems with thinly occupied matrices.

Product description

SAMG (Algebraic Multigrid Methods for Systems) is a library of subroutines for the highly efficient solution of large linear systems of equations with sparse matrices. Such systems of equations form the numerical kernel of most simulation software packages. Usually, the numerical solution of these linear systems of equations needs most of the computational time of the whole simulation.

Compared to classical methods (e.g., the ILU-preconditioned conjugate gradient method), SAMG has the advantage of being almost unconditionally numerically scalable. This means that the computational cost using SAMG depends only linearly on the number of unknowns. Depending on the application and problem size, the computational cost can be reduced by one to two orders of magnitude. SAMG can be incorporated into an existing software package as easily as any classical method.

Our solver library is available in the following flavors:

For today's multicore computers

For non-MPI codes: SAMG

  • OpenMP parallel

For computer clusters

For parallel codes: SAMGp

  • MPI / OpenMP hybrid parallel

For non-parallel codes: XSAMG

  • MPI / OpenMP hybrid parallel with automatic data distribution from sequential codes

Licenses

 

SAMG Extension Modules

In addition to the SAMG base package, we offer certain SAMG Extension Modules that enable dedicatedly optimized use of SAMG in several specific application areas.

Please contact us for more detailed information.

Currently, the following SAMG Extension Modules (and specifically tailored SAMG packages) are available:

SAMG-Constraints

 

Special Uzawa-smoothing and Schur-Complement approaches to handle constraints in the linear systems.

Extension Module SAMG-Constraints targets at linear systems that feature a saddle-point structure. This also holds for systems with a lot of constraints, at maybe different scales. Classical iterative solver approaches may no longer be applicable: the different parts of the system may require individual handling and round-off effects may be triggered by differences in scale. SAMG-Constraints provides specialized smoothing and further techniques to overcome such difficulties.

SAMG-Elasticity

 

Specialized setups that dedicatedly target at challenging linear elasticity problems.

Extension Module SAMG-Elasticity provides specialized setup approaches that target at highly ill-conditioned linear systems from linear elasticity problems. 
Classical, general AMG setup approaches may no longer work properly in such cases, while enhancing the setup by additional information provides a way out.

SAMG-MPP

 

Special feature for the computationally efficient exploitation of large numbers of processes with SAMG's numerically efficient AMG approach.

Extension Module SAMG-MPP targets at applications with a high number of MPI processes. In these cases, the AMG setup can be adjusted to more lean versions that allow to significantly reduce the amount of communication. The user can adjust all settings to receive an application-suited balance between numerical robustness and computational performance.

SAMG-Oil

 

Extension Module with solver approaches for full, coupled Jacobians from FIM/AIM reservoir simulations.

With Extension Module SAMG-Oil included, SAMG adjusts itself to the type of simulation.

This can be used for mere Black-Oil and various flavors of compositional simulations. However, this is also available for non-isothermal problems and, combined with Extension Module SAMG-Constraints, for coupled geomechanics.

SAMG-Modflow

 

SAMG-Modflow implements usage of SAMG in U.S.G.S.'s modular hydrologic model MODFLOW's solver package LMG ("Link-AMG").

SAMG-Modflow is available for MODFLOW-2000, MODFLOW-2005, MODFLOW-USG and MODFLOW 6.

Target Group

Our work is dedicated to partners and customers involved in software development as well as applications of large scale numerical simulations. In addition to our solver technology, we offer analysis and advice on application problems as well as tailoring our software to the customers computer systems, especially parallel computers.

Grundwasser Simulation
© DHI Wasy

Applications

Algebraic multigrid methods are a generalization of Geometric MultiGrid methods (GMG) which are used to solve discretized elliptic differential equations. In contrast to GMG, algebraic multigrid methods can directly be applied to the linear system without the need of geometrical background information. Hence, algebraic multigrid methods are perfectly suited to solve Partial Differential Equations (PDEs) on unstructured two- and three-dimensional grids as well as linear systems with similar properties.

Why SAMG?

In many applications of numerical simulation, such as flow and structural mechanics, the structures and geometries are discretized by complex gratings (see picture). The finer the resolution of such a lattice is, the more accurate is the simulation in general, but the greater the numerical solution systems resulting from the discretization process. In the simulation accuracies required today, the time during which these equation systems can be solved is a critical parameter. Classical numerical solution methods are not capable of solving equations of this size in an economically justifiable computation time.

SAMG's solution modules are based on modern hierarchical approaches (algebraic multi-lattice methodology, AMG). Instead of using only the given (extremely large) equation system, algebraic multi-lattice methods combine the numerical information of a hierarchy of increasingly coarse system equations to solve the given problem more quickly. The underlying coarsening process is automatic and transparent to the user of SAMG.


Parallel Versions of SAMG
We offer SAMG for different parallel programming models. All variants support the exploitation of multicore CPUs via OpenMP. The SAMGp library also offers a hybrid MPI/OpenMP parallelization that can be applied on any given distributed partition of the discretization grid.
In addition to that, XSAMG allows the simulator developer to exploit parallel hardware architectures for the solution of the linear problems, without any need for developing parallel software hisself.

Customer Response

»SAMG has been the key to improving both the robustness and performance of our General Purpose Research Simulator – GPRS. With SAMG as the workhorse linear solver, we now routinely solve problems that were simply beyond our reach. SAMG is indispensable for reservoir flow simulation of large-scale, highly heterogeneous, unstructured reservoir models.«
Prof. Hamdi Tchelepi, Petroleum Engineering Department, Stanford University

 

»For our applications, SAMG is the fastest solver in the world. SAMG has enabled us to tackle large problems faster than ever before and attempt larger problems that were ever possible – for the first time we can make multi-million cell simulations routine where we properly capture the reservoir structure.« 
Prof. Martin Blunt, Petroleum Engineering, Imperial College

 


(Translated from German:)»My congratulations to the very good product SAMG. It could provide what it promised – an experience that not always granted today.«
Prof. H.-J. G. Diersch, WASY GmbH, Berlin

 

»Experience has indicated that .... execution times ..... are typically 2 to 25 times faster than execution times using MODFLOW‘s PCG2 Package .....« 
User Guide to the LMG Package, US Geological Survey, Boulder, Colorado

 

»SAMG is in a world of its own when it comes to linear solvers. It is robust, fast, and easy to implement on any platform, and has given our company a clear competitive edge. It has been a reliable work requiring little or no maintenance, allowing us to concentrate on our core business. Small or big, simple or complex, sparse or full, structured or unstructured – SAMG will solve it. Anybody contemplating using a linear solver need look no further than SAMG and its friendly and helpful author, Dr. Klaus Stueben.« 
Marco Thiele, co-founder & President StreamSim Technologies