SAMG

Fraunhofer Institute for Algorithms and Scientific Computing SCAI

Numerical Solution of Large Matrix Problems

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.


SAMG is available in the following versions:

  • SAMG, OpenMP parallel - best suited for today's multicore computers
  • SAMGp, MPI parallel - SAMG for computer clusters

SAMG-MODFLOW for the acceleration of groundwatersimulations is now available:

    Numerical Solution of Large Matrix Problems

Target Group

Target Group

Our work is dedicated to partners and customers involved in software development as well as applications. 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.

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.

Areas of Application:

  • fluid mechanics
  • structural mechanics
  • foundry technology
  • oil reservoir simulation
  • groundwater simulation
  • hydrothermal ore agglomeration simulation
  • process simulation in semiconductor physics
  • device simulation in semiconductor physics
  • circuit simulation

Background

In many applications of numerical simulation, for example in fluid flow and structural mechanics, structures and geometries are discretised by means of complex grids (see Figure). The finer the resolution such a grid has, the higher is the quality of the simulation. On the other hand, this also increases the size of the system of discretized equations which needs to be solved numerically. Due to the accuracy of simulation results required nowadays, the amount of time needed to solve these systems of equations has become a critical factor. Classical numerical solvers typically do not have the capability to solve such large systems of equations in an acceptable amount of time.

The solver module of SAMG is based on modern hierarchical techniques (Algebraic MultiGrid methods, AMG): Instead of working with the given (extremely large) system of equations, algebraic multigrid combines numerical information from a scale of increasingly coarse systems of equations in order to solve the given problem more rapidly. This coarsening process takes place automatically and is transparent for the SAMG user.

Parallel Version of SAMG

We also offer a parallel version of SAMG (based on MPI), which can be applied to each partition of the numerical grid. As long as the number of grid cells per process is large enough, SAMG delivers exceptional performance.

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


"I congratulate you on the very good product SAMG. It delivered what was promised, which is currently not an experience one always has." (translated) Prof. H.-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

 

 

For further Information about SAMG and the terms of licensing, please contact form to samg(at)scai.fraunhofer.de

Publications

Film

Informational Film SAMG

Paper

Thum, P.; Guvanasen, V.:The Algebraic Multigrid Method (AMG) for the Acceleration of Coupled Surface and Subsurface Flow and Transport Simulations; “MODFLOW and MORE”, Colorado School of Mines, Golden, Colorado, June 2-5, 2013.

Gries, S.; Stüben, K.; Brown, G.; Chen, D.; Collins, D.: Preconditioning for Efficiently Applying Algebraic Multigrid in Fully Implicit Reservoir Simulations. SPE Reservoir Simulation Symposium, SPE 163608, February 2013, The Woodlands, Texas.

Thum, P.: Algebraic Multigrid for the Multi-Ion Transport and Reaction Model - A Physics-Aware Approach. Logos-Verlag, ISBN 978-3-8325-3285-7, 2013 Dissertation at the University of Cologne 2012.

Zecchin, A. ; Thum, P. ; Simpson, A. and Tischendorf; C.: Steady-State Behavior of Large Water Distribution Systems: Algebraic Multigrid Method for the Fast Solution of the Linear Step. Journal of Water Resources Planning and Management, American Society of Civil Engineers, Vol. 138(6), 639-650, 2012.

Gries, S.; Stüben, K.; Brown, G.; Chen, D.; Collins, D.: Advanced AMG Application for Solving CPR-type Pressure Systems. "Mathematical Methods for Fluid Dynamics and Simulation of Giant Oil and Gas Reservoirs" Conference, September 2012, Istanbul

Gries, S.: SAMG @ CSMP: Parallelization Issues, CSMP Workshop, September 2012, Colleoli - Italy

Thum, P.; Stüben, K.: Advanced Multigrid Application for the Acceleration of Groundwater Simulations. “XIX International Conference on Water Resources (CMWR)”, University of Illinois at Urbana-Champaign, June 17-20, 2012.

Kraus, J.; Förster, Brandes, T.; Soddemann, T.: Using LAMA for efficient AMG on hybrid clusters. Computer Science - Research and Development, Springer, May 2012.

Kraus, J.; Förster, M.: Efficient AMG on Heterogeneous Systems. Book: Facing the Multicore - Challenge II, Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2012.

Thum, P.; Diersch, H.J.; Gründler, R.: SAMG – The Linear Solver for Groundwater Simulation. MODELCARE 2011. September 2011; Leipzig, Germany

Förster, M.; Kraus, J.: Scalable parallel AMG on ccNUMA machines with OpenMP. Computer Science - Research and Development, June 2011, Volume 26, Issue 3-4, pp 221-228.

Thum, P.; Hesch, W.; Stüben, K.: LMG2: Accelerating the SAMG Multigrid-Solver in MODFLOW. “MODFLOW and MORE”, Colorado School of Mines, Golden, Colorado, June 5-8, 2011.

Zaretskiy, Y.; Geiger, S.; Sorbie, K.; Förster, M.: Efficient flow and transport simulations in reconstructed 3D pore geometries. Advances in Water Resources, Volume 33, Issue 12, December 2010, Pages 1508-1516

Zaretskiy, Y.; Geiger, S.; Sorbie, K.; Förster, M.: Pore-scale Modeling of Chemically Induced Effects on Two-phase Flow. 12th European Conference on the Mathematics of Oil Recovery, Capillary and Surface Effects, 06. September 2010

Clees, T; Ganzer, L.: An Efficient Algebraic Multigrid Solver Strategy for Adaptive Implicit Methods in Oil-Reservoir Simulation. SPE Journal, Volume 15, Number 3, doi: 10.2118/105789-PA, 2010.

Thum, P.; Clees, T.; Weyns, G.; Nelissen, G.; Deconinck, J.: Efficient algebraic multigrid for migration-diffusion-convection-reaction systems arising in electrochemical simulations. Journal of computational physics, Vol. 229, Issue 19, pp. 7260-7276, doi:j.jcp.2010.06.011, 2010.

Naumovich, A.; Förster, M.; Dwight, R.: Algebraic multigrid within defect correction for the linearized Euler equations . Numerical Linear Algebra with Applications.  vol. 17, no 2-3,  pp. 307-324 , doi: 10.1002/nla.687, 2010.

Thum , P.; Clees, T.: Towards physics-oriented smoothing in algebraic multigrid for systems of partial differential equations arising in multi-ion transport and reaction models . Numerical Linear Algebra with Applications , vol. 17 , no 2-3 , pp 253-271, doi: 10.1002/nla.706, 2010 .

Batycky, R.P., Förster, M., Thiele, M.R., and Stüben, K.: Parallelization of a Commercial Streamline Simulator and Performance on Practical Models, SPE-REE (118684), 2010

Thum, P.: One for all – the new SAMG solver control within FEFLOW. 2nd international FEFLOW User Conference, Potsdam (Germany), 2009.

Stüben, K., Clees, T., Klie, H., Lou, B., Wheeler, M.F.: Algebraic Multigrid Methods (AMG) for the Efficient Solution of Fully Implicit Formulations in Reservoir Simulation, paper SPE 105832 presented at the 2007 SPE Reservoir Simulation Symposium, Houston, TX, Feb. 28–30, 2007.

Klie, H., Wheeler, M.F., Clees, T., Stüben, K.: Deflation AMG Solvers for Highly Ill-Conditioned Reservoir Simulation Problems, paper SPE 105820 presented at the 2007 SPE Reservoir Simulation Symposium, Houston, TX, Feb. 28–30, 2007.

Clees, T. and Ganzer, L.: An Efficient Algebraic Multi-Grid Solver Strategy for Adaptive Implicit Methods in Oil Reservoir Simulation, paper SPE 105789 presented at the 2007 SPE Reservoir Simulation Symposium, Houston, TX, Feb. 26-28, 2007.

Larson, G., Synder, D., Abeele, D., and Clees, T. Application of single-level, pointwise algebraic, and smoothed aggregation multigrid methods to direct numerical simulations of incompressible turbulent flows. ISSN 1432-9360 (Print) 1433-0369 (Online), DOI 10.1007/s00791-006-0055-4, Online First: SpringerLink Date Tuesday, January 09, 2007.

Stüben, K.: Solving Reservoir Simulation Equations. 9th International Forum on Reservoir Simulation, December 9-13, 2007, Abu Dhabi, United Arab Emirates.

Zitzmann, M., Clees, T., and Weigel, R.: Iterative methods for reluctance based PEEC models. In Proceedings of 17th International Zurich Symposium on Electromagnetic Compatibility (EMC-Zurich), Singapore 2006, Feb 27 - Mar 3, IEEE, pp. 81–84, 2006. IEEE Catalog No. 06EX1190C, ISBN 3-9522990-4-9.

Zitzmann, M., Grillmair, R., Clees, T., and Weigel, R.: Hybrid solver strategies in automotive emc simulation. In Proceedings of 17th International Zurich Symposium on Electromagnetic Compatibility (EMC-Zurich), Singapore 2006, Feb 27 - Mar 3, IEEE, pp. 340–343, 2006. IEEE Catalog No. 06EX1190C, ISBN 3-9522990-4-9.

Clees, T.: AMG Strategies for PDE Systems with Applications in Industrial Semiconductor Simulation. Aachen: Shaker Verlag, 2005 (Fraunhofer series in information and communication technology, 2005, 6). Zugl.: Köln, Univ., Diss., 2004.

Häfner, F.; Stüben, K: Simulation and Parameter Identification of Oswald’s Saltpool Experiments with the SAMG Multigrid-Solver in the Transport Code MODCALIF. FEM Modflow : International Conference on Finite Element Models, MODFLOW, and More. 13 - 16 September 2004, Karlovy Vary, Czech Republic. Prague, 2004

Stüben, K.; Delaney, P.; Chmakov, S.: Algebraic Multigrid (AMG) for Ground Water Flow and Oil Reservoir Simulation. Joint paper with Waterloo Hydrogeologic Inc. presented at the Groundwater Modeling Conference “MODFLOW and MORE”, Colorado School of Mines, Golden, Colorado, Sept 17-19, 2003.

Clees, T.; Stüben, K.: Algebraic Multigrid for Industrial Semiconductor Device Simulation. Proceedings of the First International Conference on Challenges in Scientific Computing, Berlin, Germany, Oct 2-5, 2002. Lecture Notes in Computational Science and Engineering 35, Springer, Heidelberg, Berlin, 2003.

Füllenbach, T.; Stüben, K.: Algebraic multigrid for selected PDE systems. Proceedings of the Fourth European Conference on Elliptic and Parabolic Problems, Rolduc (The Netherlands) and Gaeta (Italy), 2001. World Scientific, New Jersey, London, pp. 399-410, 2002.

Krechel, A.; Stüben, K.: Parallel algebraic multigrid based on subdomain blocking. Report on a parallel AMG approach. Appeared in: Parallel Computing 27, pp. 1009-1031, 2001.

Stüben, K.: A Review of Algebraic Multigrid. A short report on AMG and the basic solver technology. Appeared in: Journal of Computational and Applied Mathematics 128, pp. 281-309, 2001.

Stüben, K.: An Introduction to Algebraic Multigrid. Introduction to the AMG methodology for scalar applications, including many results and performance measurements. Appeared as an appendix in the book: „Multigrid“ by U. Trottenberg; C.W. Oosterlee; A. Schüller, Academic Press, pp. 413-532, 2001.

Füllenbach, T.; Stüben, K.; Mijalkovic, S.: Application of an algebraic multigrid solver to process simulation problems. Proceedings of the International Conference on Simulation of Semiconductor Processes and Devices, Seattle (WA), USA, Sep 6-8, 2000. IEEE, Piscataway (NJ), USA, pp. 225-228, 2000.

Krechel, A.; Stüben, K.: Operator Dependent Interpolation in Algebraic Multigrid. Lect Notes Comput Sci Eng, vol. 3. Springer, Berlin. pp. 189-211

Contact and Licenses

Technical Contact

Dr. Klaus Stüben

Telefon +49 2241 14-2749
Fax +49 2241 14-2102

 

Licenses

scapos AG

Phone +49 2241 14-2820 
Fax +49 2241 14-2817 

 

The SAMG-packages are available with different licenses:

  • A node-locked license enables unlimited use - i. e. any number of concurrent SAMG applications run by arbitrary users - on a single machine.
  • A floating license enables a dedicated number of concurrent SAMG applications run by arbitrary users on arbitrary machines in a certain IP-network.

In order to provide you with a suitable license we need some information on the environment intended to be used for SAMG applications.

This archive contains tools to determine the requested information. Usage instructions are provided here.