SAMG – Efficiently solving large Linear Systems of Equations


  • 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.

Description of SAMG

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 versions:

For today's multicore computers

  • 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



Special add-on features

SAMG offers certain add-on features and interfaces for some specific application areas. Please contact us if these are of interest for you. Currently, the following add-ons are available:


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



Specialized setups that dedicatedly target at challenging linear elasticity problems.


Interface for full, coupled Jacobians from FIM/AIM reservoir simulations.



LMG interface for the direct usage with Modflow.

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


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.


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