×

zbMATH — the first resource for mathematics

A multithreaded recursive and nonrecursive parallel sparse direct solver. (English) Zbl 1356.65117
Bazilevs, Yuri (ed.) et al., Advances in computational fluid-structure interaction and flow simulation. New methods and challenging computations. Based on the presentations at the conference, AFSI, Tokyo, Japan, March 19–21, 2014. Basel: Birkhäuser/Springer (ISBN 978-3-319-40825-5/hbk; 978-3-319-40827-9/ebook). Modeling and Simulation in Science, Engineering and Technology, 283-292 (2016).
Summary: Sparse linear system of equations often arises after discretization of the partial differential equations (PDEs) such as computational fluid dynamics, material science, and structural engineering. There are, however, sparse linear systems that are not governed by PDEs, some examples of such applications are circuit simulations, power network analysis, and social network analysis. For solution of sparse linear systems one can choose using either a direct or an iterative method. Direct solvers are based on some factorization of the coefficient matrix such as the LU, QR, or singular value decompositions and are known to be robust. Classical preconditioned iterative solvers, on the other hand, are not as robust as direct solvers and finding an effective preconditioner is often problem dependent. Due to their sequential nature, direct solvers often have limited parallel scalability. In this chapter, we present a new parallel recursive sparse direct solver that is based on the sparse DS factorization. We implement our algorithm using MIT’s Cilk programming language which is also a part of the Intel C++ compiler. We show the scalability and robustness of our algorithm and compare it to Pardiso direct solver.
For the entire collection see [Zbl 1356.76009].

MSC:
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amestoy, P., Duff, I., L’Excellent, J.Y., Koster, J.: Mumps: a general purpose distributed memory sparse solver. In: Sørevik, T., Manne, F., Gebremedhin, A., Moe, R. (eds.) Applied Parallel Computing. New Paradigms for HPC in Industry and Academia. Lecture Notes in Computer Science, vol. 1947, pp. 121–130. Springer, Berlin, Heidelberg (2001) · doi:10.1007/3-540-70734-4_16
[2] Bolukbasi, E.: A new multi-threaded and recursive direct algorithm for parallel solution of sparse linear systems. Master’s thesis, Middle East Technical University, Ankara (2013)
[3] Bolukbasi, E.S., Manguoglu, M.: A new multi-threaded and recursive direct algorithm for parallel solution of sparse linear systems. 5th International Conference of the ERCIM (European Research Consortium for Informatics and Mathematics) Working Group on Computing & Statistics (2012) · Zbl 1356.65117
[4] Davis, T.A., Hu, Y.: The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38 (1), 1:1–1:25 (2011). doi: 10.1145/2049662.2049663 . http://doi.acm.org/10.1145/2049662.2049663 · Zbl 1365.65123 · doi:10.1145/2049662.2049663
[5] Demmel, J.W., Eisenstat, S.C., Gilbert, J.R., Li, X.S., Liu, J.W.H.: A supernodal approach to sparse partial pivoting. SIAM J. Matrix Anal. Appl. 20 (3), 720–755 (1999) · Zbl 0931.65022 · doi:10.1137/S0895479895291765
[6] Gould, N.I.M., Scott, J.A., Hu, Y.: A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations. ACM Trans. Math. Softw. 33 (2) (2007). doi: 10.1145/1236463.1236465 . http://doi.acm.org/10.1145/1236463.1236465 · Zbl 1365.65129 · doi:10.1145/1236463.1236465
[7] Gupta, A.: WSMP: Watson sparse matrix package (part-i: direct solution of symmetric sparse systems). IBM TJ Watson Research Center, Yorktown Heights, NY. Technical Report, RC, vol. 21886 (2000)
[8] Gupta, A.: Wsmp: Watson sparse matrix package (part-ii: direct solution of general sparse systems). Technical Report, Technical Report RC 21888 (98472). IBM TJ Watson Research Center, Yorktown Heights, NY (2000). http://www.cs.umn.edu/ agupta/doc/wssmp-paper.ps
[9] HSL: A collection of Fortran codes for large scale scientific computation (2011). http://www.hsl.rl.ac.uk
[10] Intel. Intel MKL 10.3 release notes (2012). http://software.intel.com/en-us/articles/intel-mkl-103-release-notes
[11] Intel: Intel Cilk plus (2013). http://software.intel.com/en-us/intel-cilk-plus
[12] Intel: Intel math kernel library 11.0 (2013). http://software.intel.com/en-us/intel-mkl
[13] Karypis, G.: Metis - serial graph partitioning and fill-reducing matrix ordering (2013). http://glaros.dtc.umn.edu/gkhome/metis/metis/overview
[14] Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20 (1), 359–392 (1998). doi: 10.1137/S1064827595287997 . http://epubs.siam.org/doi/abs/10.1137/S1064827595287997 · Zbl 0915.68129 · doi:10.1137/S1064827595287997
[15] Li, X.S.: An overview of SuperLU: Algorithms, implementation, and user interface. ACM Trans. Math. Softw. 31 (3), 302–325 (2005) · Zbl 1136.65312 · doi:10.1145/1089014.1089017
[16] Manguoglu, M.: A domain-decomposing parallel sparse linear system solver. J. Comput. Appl. Math. 236 (3), 319–325 (2011) · Zbl 1228.65051 · doi:10.1016/j.cam.2011.07.017
[17] Manguoglu, M.: Parallel solution of sparse linear systems. In: High-Performance Scientific Computing, pp. 171–184. Springer, London (2012) · doi:10.1007/978-1-4471-2437-5_8
[18] Moore, G.E.: Cramming more components onto integrated circuits. IEEE Solid State Circuits Soc. Newsl. 11 (5), 33–35 (2006) [Reprinted from Electronics 38 (8), 114 ff. (1965)]. doi: 10.1109/N-SSC.2006.4785860 · doi:10.1109/N-SSC.2006.4785860
[19] Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003
[20] Sameh, A.H., Kuck, D.J.: On stable parallel linear system solvers. J. ACM 25 (1), 81–91 (1978) · Zbl 0364.68051 · doi:10.1145/322047.322054
[21] Sameh, A.H., Polizzi, E.: A parallel hybrid banded system solver: the spike algorithm. Parallel Comput. 32 (2), 177–194 (2006) · doi:10.1016/j.parco.2005.07.005
[22] Sameh, A.H., Polizzi, E.: Spike: a parallel environment for solving banded linear systems. Comput. Fluids 36 (1), 113–120 (2007) · Zbl 1181.76110 · doi:10.1016/j.compfluid.2005.07.005
[23] Schenk, O., Gärtner, K.: Solving unsymmetric sparse systems of linear equations with pardiso. Futur. Gener. Comput. Syst. 20 (3), 475–487 (2004) · doi:10.1016/j.future.2003.07.011
[24] Schenk, O., Gärtner, K.: On fast factorization pivoting methods for sparse symmetric indefinite systems. Electron. Trans. Numer. Anal. 23, 158–179 (2006) · Zbl 1112.65022
[25] Schenk, O., Wächter, A., Hagemann, M.: Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization. Comput. Optim. Appl. 36 (2–3), 321–341 (2007) · Zbl 1146.90055 · doi:10.1007/s10589-006-9003-y
[26] Schenk, O., Bollhöfer, M., Römer, R.A.: On large-scale diagonalization techniques for the Anderson model of localization. SIAM Rev. 50 (1), 91–112 (2008) · Zbl 1136.65044 · doi:10.1137/070707002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.