SAMG

Matrixprobleme effizient lösen

SAMG (Algebraische Mehrgitterverfahren für Systeme) ist eine Bibliothek von Unterroutinen zur hocheffizienten Lösung großer linearer Gleichungssysteme mit dünnbesetzten Matrizen. Solche Gleichungssysteme bilden den numerischen Kern der meisten Simulationssoftwarepakete. In der Regel macht die numerische Lösung dieser linearen Gleichungssysteme den bei weitem rechenintensivsten Teil einer kompletten Simulation aus.

Gegenüber klassischen Verfahren (zum Beispiel durch ILU vorkonditionierten Verfahren der konjugierten Gradienten) hat SAMG den großen Vorteil einer weitestgehend numerischen Skalierbarkeit. Das bedeutet, dass der Rechenaufwand mit SAMG nur linear von der Anzahl der Unbekannten abhängig ist. Je nach Anwendung und Problemgröße kann der dadurch bedingte Rechenzeitgewinn ein bis zwei Größenordnungen ausmachen. Dabei lässt sich SAMG genauso einfach in ein existierendes Simulationspaket integrieren wie ein klassisches Verfahren.


Unsere Löserbibliothek ist in folgenden Versionen verfügbar:

  • SAMG, OpenMP parallel - ideal für heutige Multicore-Rechner
  • SAMGp, MPI/OpenMP hybrid parallel - SAMG für Multicore-Cluster

SAMG-MODFLOW für die Beschleunigung von Grundwassersimulationen ist jetzt erhältlich:

 

SAMG in der Praxis

Bei der Ölreservoir- und Grundwassersimulation sind klassische Verfahren zur Lösung der zugrundeliegenden linearen Gleichungssysteme sehr ineffizient. Speziell in der Ölreservoirsimulation ist SAMG mittlerweile ein etabliertes Tool für viele Softwareprovider sowie bedeutende Ölfirmen geworden.

Kundenbereich

Login

 

Flyer

SAMG: ANNOUNCMENT

Zielgruppe

Mit unseren Arbeiten sprechen wir Partner und Kunden aus der Software-Entwicklung und -Anwendung an. Zusätzlich zu unserer Lösertechnologie bieten wir auch Analyse und Beratung zu Anwendungsproblemen sowie die Anpassung unserer Software auf kundenseitig betriebene Rechnersysteme, speziell Parallelrechner, an.

Anwendungen

Algebraische Mehrgitterverfahren sind aus der Idee heraus entstanden, »geometrische« Mehrgitterverfahren zur Lösung diskretisierter elliptischer Differentialgleichungen so zu verallgemeinern, dass sie direkt auf lineare Gleichungssysteme angewendet werden können, ohne geometrische Eigenschaften direkt zu benutzen. Algebraische Mehrgitterverfahren sind daher besonders zur Lösung partieller Differentialgleichungen auf unstrukturierten zwei- oder dreidimensionalen Problemen geeignet, oder aber zur Lösung von Gleichungssystemen mit strukturell ähnlichen Eigenschaften.

Anwendungsbereiche:

  • Strömungsmechanik
  • Strukturmechanik
  • Gießereitechnik
  • Ölreservoirsimulation
  • Grundwassersimulation
  • Hydrothermale Erzanlagerungssimulation
  • Prozess-Simulation in der Halbleiterphysik
  • Device-Simulation in der Halbleiterphysik
  • Schaltkreissimulation

Hintergrund

In vielen Anwendungen der numerischen Simulation, zum Beispiel der Strömungs- und Strukturmechanik, werden die Strukturen und Geometrien durch komplexe Gitter diskretisiert (siehe Bild). Je feiner die Auflösung eines solchen Gitters ist, desto genauer ist im Allgemeinen die Simulation, umso größer sind aber auch die aus dem Diskretisierungsprozess resultierenden, numerisch zu lösenden Gleichungssysteme. Bei den heute verlangten Simulationsgenauigkeiten ist die Zeit, in der diese Gleichungssysteme gelöst werden können, eine kritische Größe. Klassische numerische Lösungsverfahren sind nicht in der Lage, Gleichungssysteme dieser Größe in einer ökonomisch vertretbaren Rechenzeit zu lösen.

Die Lösungsmodule von SAMG basieren auf modernen hierarchischen Verfahrensansätzen (algebraische Mehrgittermethodik, AMG): Anstatt nur mit dem gegebenen (extrem großen) Gleichungssystem zu arbeiten, kombinieren algebraische Mehrgitterverfahren die numerische Information einer Hierarchie immer gröberer Gleichungssysteme, um das gegebene Problem schneller zu lösen. Der zugrunde liegende Vergröberungsprozess ist automatisch und für den Benutzer von SAMG transparent.

Parallele Version von SAMG

SAMG bieten wir auch als parallele Version an (basierend auf MPI), die sich auf jede Partitionierung des Rechengitters anwenden läßt. So lange die Zahl der Gitterzellen pro Prozess groß genug ist, bietet auch das parallele SAMG eine außergewöhnliche Leistung.

 

Kundenstimmen

»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

 


 

»Ich gratuliere zu dem sehr guten Produkt SAMG. Es hat das gehalten, was es versprochen hat, eine heute nicht mehr in jedem Falle übliche Erfahrung.«
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

Publikationen

Image booklet

 

Artikel

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

Kontakt und Lizenzen

Technischner Ansprechpartner

Dr. Klaus Stüben

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

Lizenzen

scapos AG

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

 

Die SAMG-Produkte sind mit node-locked oder floating Lizenzen verfügbar:

  • Eine node-locked Lizenz ermöglicht die uneingeschänkte Nutzung - d. h. beliebig viele gleichzeitige SAMG Läufe von beliebigen Nutzern - auf einem einzigen Rechner.
  • Eine floating Lizenz ermöglicht eine bestimmte Anzahl von gleichzeitigen SAMG Läufen beliebiger Nutzer auf beliebigen Rechnern in einem bestimmten IP-Netz.

Zum Ausstellen einer Lizenz benötigen wir Informationen über die Umgebung, in der die SAMG-Anwendungen laufen sollen.

Dieses Archiv enthält Tools zum Ermitteln dieser Informationen; die entsprechende Benutzungsanleitung finden Sie hier.