On the evaluation of general sparse hybrid linear solvers. (English) Zbl 07675618
Summary: General sparse hybrid solvers are commonly used kernels for solving wide range of scientific and engineering problems. This work addresses the current problems of efficiently solving general sparse linear equations with direct/iterative hybrid solvers on many core distributed clusters. We briefly discuss the solution stages of Maphys, HIPS, and PDSLin hybrid solvers for large sparse linear systems with their major algorithmic differences. In this category of solvers, different methods with sophisticated preconditioning algorithms are suggested to solve the trade off between memory and convergence. Such solutions require a certain hierarchical level of parallelism more suitable for modern supercomputers that allow to scale for thousand numbers of processors using Schur complement framework. We study the effect of reordering and analyze the performance, scalability as well as memory for each solve phase of PDSLin, Maphys, and HIPS hybrid solvers using large set of challenging matrices arising from different actual applications and compare the results with SuperLU\(\_\)DIST direct solver. We specifically focus on the level of parallel mechanisms used by the hybrid solvers and the effect on scalability. Tuning and Analysis Utilities (TAU) is employed to assess the efficient usage of heap memory profile and measuring communication volume. The tests are run on high performance large memory clusters using up to 512 processors.
MSC:
| 65F50 | Computational methods for sparse matrices |
Keywords:
additive Schwarz; direct methods; high performance computing; HIPS; iterative methods; LU factorization; Maphys; parallel sparse hybrid linear solver; partitioning; PDSLin; preconditioners; preconditioning; scalability; Schur complement; sparse matrix; SuperLU\(\_\)DISTReferences:
| [1] | DavisTA. Direct methods for sparse linear systems. Philadelphia: SIAM; 2006. · Zbl 1119.65021 |
| [2] | LiX. Direct solvers for sparse matrices. Technical report. Berkeley, CA: Lawrence Berkeley National Laboratory; 2022. https://portal.nersc.gov/project/sparse/superlu/SparseDirectSurvey.pdf |
| [3] | DavisTA, RajamanickamS, Sid‐LakhdarWM. A survey of direct methods for sparse linear systems. Acta Numer. 2016;25:383-566. · Zbl 1346.65011 |
| [4] | GuptaA. Recent advances in direct methods for solving unsymmetric sparse systems of linear equations. ACM Trans Math Softw (TOMS). 2002;28(3):301-24. · Zbl 1072.65039 |
| [5] | GouldNI, ScottJA, HuY. A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations. ACM Trans Math Softw (TOMS). 2007;33(2):10-es. · Zbl 1365.65129 |
| [6] | AmestoyPR, DuffIS, L’excellentJY, LiXS. Analysis and comparison of two general sparse solvers for distributed memory computers. ACM Trans Math Softw (TOMS). 2001;27(4):388-421. · Zbl 1072.65035 |
| [7] | YamazakiI, LiXS. On techniques to improve robustness and scalability of the Schur complement method. 2010;421-34. https://portal.nersc.gov/project/sparse/xiaoye‐web/vecpar10.pdf |
| [8] | NakovS. On the design of sparse hybrid linear solvers for modern parallel architectures. France: Université de Bordeaux; 2015. |
| [9] | HénonP, SaadY. A parallel multistage ILU factorization based on a hierarchical graph decomposition. SIAM J Sci Comput. 2006;28(6):2266-93. · Zbl 1126.65028 |
| [10] | GiraudL, HaidarA. Parallel algebraic hybrid solvers for large 3D convection‐diffusion problems. Numer Algorithms. 2009;51(2):151-77. · Zbl 1167.65355 |
| [11] | GaidamourJ, HénonP. HIPS: a parallel hybrid direct/iterative solver based on a Schur complement approach. Proceedings of PMAA. 2008;v1:hal‐00353595. |
| [12] | DemmelJW, EisenstatSC, GilbertJR, LiXS, LiuJW. A supernodal approach to sparse partial pivoting. SIAM J Matrix Anal Appl. 1999;20(3):720-55. · Zbl 0931.65022 |
| [13] | DuIS. Sparse numerical linear algebra: direct methods and preconditioning. Du and Watson [DW97]; 1996. p. 27-62. |
| [14] | SmithBF. PE Bjorstad, and WD Gropp, domain decomposition: parallel multilevel methods for elliptic partial differential equations. New York, NY: Cambridge University Press; 1996. · Zbl 0857.65126 |
| [15] | SaadY. Iterative methods for sparse linear systems. Philadelphia: SIAM; 2003. · Zbl 1031.65046 |
| [16] | GiraudL, TuminaroR. Algebraic domain decomposition preconditioners. In: MagoulesF (ed.), editor. Mesh partitioning techniques and domain decomposition methods. Saxe‐Coburg Publications; 2007. pp. 187-216. |
| [17] | HaidarA.On the parallel scalability of hybrid linear solvers for large 3D problems; 2008. |
| [18] | CarvalhoLM, GiraudL, MeurantG. Local preconditioners for two‐level non‐overlapping domain decomposition methods. Numer Linear Algebra Appl. 2001;8(4):207-27. · Zbl 1051.65051 |
| [19] | GiraudL, HaidarA, SaadY. Sparse approximations of the Schur complement for parallel algebraic hybrid linear solvers in 3D. INRIA; 2010. |
| [20] | YamazakiI, NgE, LiX. PDSLin user guide. Berkeley, CA: Lawrence Berkeley National Lab.(LBNL); 2011. |
| [21] | SaadY, SuchomelB. ARMS: an algebraic recursive multilevel solver for general sparse linear systems. Numer Linear Algebra Appl. 2002;9(5):359-78. · Zbl 1071.65001 |
| [22] | GiraudL, HaidarA, PraletS. Using multiple levels of parallelism to enhance the performance of hybrid linear solvers. Parallel Comput. 2010;36(5‐6):285-96. · Zbl 1204.68262 |
| [23] | AgulloE, GiraudL, ZounonM. Maphys user’s guide 0.9.6.0; 2017. |
| [24] | KarypisG, SchloegelK, KumarV. Parmetis: parallel graph partitioning and sparse matrix ordering library; 1997. |
| [25] | KarypisG, KumarV. METIS: a software package for partitioning unstructured graphs, partitioning meshes, and computing fill‐reducing orderings of sparse matrices; 1997. |
| [26] | PellegriniF, RomanJ. Scotch: a software package for static mapping by dual recursive bipartitioning of process and architecture graphs; 1996. |
| [27] | BalayS, AbhyankarS, AdamsM, BrownJ, BruneP, BuschelmanK, et al. PETSc users manual, Technical Report. Lemont, IL: Argonne National Laboratory; 2019. |
| [28] | FraysséV, GiraudL, GrattonS, LangouJ. A set of GMRES routines for real and complex arithmetics. Citeseer; 1997. http://www.cerfacs.fr/algor/Softs/GMRES/index.html. |
| [29] | YamazakiI, LiXS, RouetF, UçarB. Partitioning, ordering, and load balancing in a hierarchically parallel hybrid linear solver. Institut National Polytechnique de Toulouse, Toulouse, France, Technical Report RT‐APO‐12‐2. 2011. |
| [30] | StathopoulosA, McCombsJR. PRIMME: PReconditioned iterative multi‐method Eigensolver—Methods and software description. ACM Trans Math Softw (TOMS). 2010;37(2):1-30. · Zbl 1364.65087 |
| [31] | CelebiMS, DuranA, OztoprakF, TuncelM, AkaydinB. On the improvement of a scalable sparse direct solver for unsymmetrical linear equations. J Supercomput. 2017;73(5):1852-904. |
| [32] | ButtariA, LangouJ, KurzakJ, DongarraJ. A class of parallel tiled linear algebra algorithms for multicore architectures. Parallel Comput. 2009;35(1):38-53. |
| [33] | DavisTA, HuY. The University of Florida sparse matrix collection. ACM Trans Math Softw (TOMS). 2011;38(1):1-25. · Zbl 1365.65123 |
| [34] | NaumovM, ManguogluM, SamehAH. A tearing‐based hybrid parallel sparse linear system solver. Journal of Computational and Applied Mathematics. 2010;234(10):3025-3038. · Zbl 1193.65029 |
| [35] | HernandezV, RomanJE, VidalV. SLEPc: a scalable and flexible toolkit for the solution of eigenvalue problems. ACM Trans Math Softw (TOMS). 2005;31(3):351-362. · Zbl 1136.65315 |
| [36] | BroquedisF, Clet‐OrtegaJ, MoreaudS, FurmentoN, GoglinB, MercierG, et al. hwloc: a generic framework for managing hardware affinities in HPC applications. Proceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network‐based Processing. IEEE; 2010. p. 180-6. |
| [37] | ShendeSS, MalonyAD. The TAU parallel performance system. Int J High Perform Comput Appl. 2006;20(2):287-311. |
| [38] | LiuJW. Modification of the minimum‐degree algorithm by multiple elimination. ACM Trans Math Softw (TOMS). 1985;11(2):141-53. · Zbl 0568.65015 |
| [39] | DavisTA, GilbertJR, LarimoreSI, NgEG. A column approximate minimum degree ordering algorithm. ACM Trans Math Softw (TOMS). 2004;30(3):353-76. · Zbl 1073.65039 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
