zbMATH — the first resource for mathematics

Parallel hybrid sparse linear system solvers. (English) Zbl 1453.65087
Grama, Ananth (ed.) et al., Parallel algorithms in computational science and engineering. Cham: Birkhäuser. Model. Simul. Sci. Eng. Technol., 95-120 (2020).
Summary: In this chapter, we present the SPIKE family of algorithms for solving banded linear systems and its multithreaded implementation as well as direct-iterative hybrid variants for solving general sparse linear system of equations.
For the entire collection see [Zbl 1446.65003].
65F50 Computational methods for sparse matrices
65F08 Preconditioners for iterative methods
65Y05 Parallel numerical computation
Full Text: DOI
[1] SPIKE openMP package. http://www.spike-solver.org/.
[2] E. ANDERSON, Z. BAI, C. BISCHOF, S. BLACKFORD, J. DEMMEL, J. DONGARRA, J. DU CROZ, A. GREENBAUM, S. HAMMARLING, A. MCKENNEY, AND D. SORENSEN, LAPACK Users’ Guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, third ed., 1999.
[3] E. S. BOLUKBASI AND M. MANGUOGLU, A multithreaded recursive and nonrecursive parallel sparse direct solver, in Advances in Computational Fluid-Structure Interaction and Flow Simulation, Springer, 2016, pp. 283-292. · Zbl 1356.65117
[4] U. V. CATALYUREK AND C. AYKANAT, Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication, IEEE Transactions on parallel and distributed systems, 10 (1999), pp. 673-693.
[5] I. CUGU AND M. MANGUOGLU, A parallel multithreaded sparse triangular linear system solver, Computers & Mathematics with Applications, (2019).
[6] T. A. DAVIS AND Y. HU, The University of Florida Sparse Matrix Collection, ACM Transactions on Mathematical Software (TOMS), 38 (2011), p. 1. · Zbl 1365.65123
[7] T. A. DAVIS AND Y. HU, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Softw., 38 (2011), pp. 1:1-1:25. · Zbl 1365.65123
[8] I. S. DUFF AND J. KOSTER, The design and use of algorithms for permuting large entries to the diagonal of sparse matrices, SIAM Journal on Matrix Analysis and Applications, 20 (1999), pp. 889-901. · Zbl 0947.65048
[9] M. FIEDLER, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 23 (1973), pp. 298-305. · Zbl 0265.05119
[10] E. GALLOPOULOS, B. PHILIPPE, AND A. H. SAMEH, Parallelism in matrix computations, Springer, 2016. · Zbl 1341.65011
[11] G. KARYPIS AND V. KUMAR, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on scientific Computing, 20 (1998), pp. 359-392. · Zbl 0915.68129
[12] D. H. LAWRIE AND A. H. SAMEH, The computation and communication complexity of a parallel banded system solver, ACM Transactions on Mathematical Software (TOMS), 10 (1984), pp. 185-195. · Zbl 0534.68027
[13] L. LIU, Z. LI, AND A. H. SAMEH, Analyzing memory access intensity in parallel programs on multicore, in Proceedings of the 22nd annual international conference on Supercomputing, ACM, 2008, pp. 359-367.
[14] M. MANGUOGLU, A domain-decomposing parallel sparse linear system solver, Journal of computational and applied mathematics, 236 (2011), pp. 319-325. · Zbl 1228.65051
[15] ——, A parallel sparse solver and its relation to graphs, in CEM’11 Computational Electromagnetics International Workshop, IEEE, 2011, pp. 91-94.
[16] M. MANGUOGLU, E. COX, F. SAIED, AND A. SAMEH, TRACEMIN-Fiedler: A Parallel Algorithm for Computing the Fiedler Vector, High Performance Computing for Computational Science-VECPAR 2010, (2011), pp. 449-455. · Zbl 1323.65130
[17] M. MANGUOGLU, F. SAIED, A. SAMEH, AND A. GRAMA, Performance models for the spike banded linear system solver, Scientific Programming, 19 (2011), pp. 13-25.
[18] M. MANGUOGLU, A. H. SAMEH, AND O. SCHENK, Pspike: A parallel hybrid sparse linear system solver, in European Conference on Parallel Processing, Springer, 2009, pp. 797-808.
[19] K. MENDIRATTA AND E. POLIZZI, A threaded spike algorithm for solving general banded systems, Parallel Computing, 37 (2011), pp. 733-741. 6th International Workshop on Parallel Matrix Algorithms and Applications (PMAA’10).
[20] C. C. K. MIKKELSEN AND M. MANGUOGLU, Analysis of the truncated SPIKE algorithm, SIAM Journal on Matrix Analysis and Applications, 30 (2008), pp. 1500-1519. · Zbl 1176.65028
[21] M. NAUMOV, M. MANGUOGLU, AND A. H. SAMEH, A tearing-based hybrid parallel sparse linear system solver, J. Computational Applied Mathematics, 234 (2010), pp. 3025-3038. · Zbl 1193.65029
[22] M. NAUMOV AND A. H. SAMEH, A tearing-based hybrid parallel banded linear system solver, Journal of Computational and Applied Mathematics, 226 (2009), pp. 306-318. · Zbl 1170.65025
[23] E. POLIZZI AND A. SAMEH, SPIKE: A parallel environment for solving banded linear systems, Computers & Fluids, 36 (2007), pp. 113-120. Challenges and Advances in Flow Simulation and Modeling. · Zbl 1181.76110
[24] E. POLIZZI AND A. H. SAMEH, A parallel hybrid banded system solver: the SPIKE algorithm, Parallel computing, 32 (2006), pp. 177-194.
[25] Y. SAAD, Iterative methods for sparse linear systems, vol. 82, siam, 2003. · Zbl 1031.65046
[26] A. SAMEH AND Z. TONG, The trace minimization method for the symmetric generalized eigenvalue problem, J. Comput. Appl. Math., 123 (2000), pp. 155-175. · Zbl 0964.65038
[27] A. H. SAMEH AND D. J. KUCK, On stable parallel linear system solvers, Journal of the ACM (JACM), 25 (1978), pp. 81-91. · Zbl 0364.68051
[28] A. H. SAMEH AND J. A. WISNIEWSKI, A trace minimization algorithm for the generalized eigenvalue problem, SIAM Journal on Numerical Analysis, 19 (1982), pp. 1243-1259. · Zbl 0493.65017
[29] O. SCHENK AND K. GäRTNER, Solving unsymmetric sparse systems of linear equations with PARDISO, Future Generation Computer Systems, 20 (2004), pp. 475-487.
[30] O. SCHENK, M. MANGUOGLU, A. SAMEH, M. CHRISTEN, AND M. SATHE, Parallel scalable PDE-constrained optimization: antenna identification in hyperthermia cancer treatment planning, Computer Science-Research and Development, 23 (2009), pp. 177-183.
[31] B.
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.