SPIKE: A parallel environment for solving banded linear systems. (English) Zbl 1181.76110

Polizzi, Eric; Sameh, Ahmed

Comput. Fluids 36, No. 1, 113-120 (2007).

Summary: The hybrid banded linear solver SPIKE is proposed as a parallel environment for solving banded systems that are either dense or sparse within the band. The SPIKE algorithm is a domain decomposition technique that allows performing independent calculations on each subdomain or partition of the original linear system. The interface problem leads to a reduced linear system of much smaller size than that of the original system. Three different members of the SPIKE family are described. Each handles the reduced system in a different way depending on the characteristics of the system and the architecture of the high-end parallel computing platform. Numerical experiments are presented that demonstrate the effectiveness of our parallel scheme. Comparison with the corresponding algorithms of ScaLAPACK are also provided for those banded systems that are dense within the band. A SPIKE scheme with multi-level parallelism is also introduced for solving large banded systems that are sparse within the band.

MSC:

76M25	Other numerical methods (fluid mechanics) (MSC2010)
65Y05	Parallel numerical computation
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

LAPACK; SuperLU-DIST; SPIKE; MUMPS; ScaLAPACK

References:

[1]	Polizzi E, Sameh A. A parallel hybrid system solver: the SPIKE algorithm. Parallel Comput 2005 [to appear].
[2]	Sameh, A.H., Numerical parallel algorithms – a survey, (), 207-228
[3]	Sameh AH, Kuck DJ. Parallel direct linear system solvers – a survey. In: IMACS (AICA)-GI-symp. on parallel computers – parallel mathematics; 1977. p. 25-30.
[4]	Sameh, A.H.; Kuck, D.J., On stable parallel linear system solvers, J ACM, 25, 81-91, (1978) · Zbl 0364.68051
[5]	Sameh, A.H., On two numerical algorithms for multiprocessors, (), 311-328
[6]	Lawrie, D.H.; Sameh, A.H., The computation and communication complexity of a parallel banded system solver, ACM trans math software, 10, 2, 185-195, (1984) · Zbl 0534.68027
[7]	Sameh A. Parallel linear system solvers. In: Proc. of the conf. on vector and parallel processors for scientific computation; 1985.
[8]	Berry, M.; Gallivan, K.; Harrod, W.; Jalby, W.; Lo, S.; Meier, U., Parallel algorithms on the CEDAR system, (), 25-39
[9]	Berry, M.; Sameh, A., Multiprocessor schemes for solving block tridiagonal linear systems, Int J supercomput appl, 2, 3, 37-57, (1988)
[10]	Gallivan, K.; Gallopoulos, E.; Sameh, A., Cedar: an experiment in parallel computing, Comput math appl, 1, 1, 77-98, (1994) · Zbl 0860.68015
[11]	Blackford, L.S.; Choi, J.; Cleary, A.; D’Azevedo, E.; Demmel, J.; Dhillon, I., Scalapack user’s guide, (1997), Society for Industrial and Appl. Math. Philadelphia, PA · Zbl 0886.65022
[12]	Cleary A, Dongarra J. Implemantation in ScaLAPACK of divide-and-conquer algorithms for banded and tridiagonal linear systems. University of Tennessee Computer Science Technical Report, UT-CS-97-358; 1997.
[13]	Arbenz, P.; Cleary, A.; Dongarra, J.; Hegland, M., A comparison of parallel solvers for diagonally dominant and general narrow-banded linear systems, Parallel distribut comput pract, 2, 385-400, (1999)
[14]	Arbenz, P.; Cleary, A.; Dongarra, J.; Hegland, M., A comparison of parallel solvers for diagonally dominant and general narrow-banded linear systems II, (), 1078-1087
[15]	Anderson, E.; Bai, Z.; Bischof, C.; Blackford, S.; Demmel, J.; Dongarra, J., LAPACK user’s guide, (1999), Society for Industrial and Appl. Math. Philadelphia, PA · Zbl 0934.65030
[16]	Demko, S.; Moss, W.F.; Smith, P.W., Decay rates for inverses of band matrices, Math comput, 43, 168, 491-499, (1984) · Zbl 0568.15003
[17]	Li, X.S.; Demmel, J.W., Superlu_DIST: a scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM trans math software, 29, 2, 110-140, (2003) · Zbl 1068.90591
[18]	Amestoy, P.R.; Duff, I.S.; L’Excellent, J.-Y.; Koster, K., A fully asynchronous multifrontal solver using distributed dynamic scheduling, A SIAM J matrix anal appl, 23, 21, 15-49, (2001) · Zbl 0992.65018
[19]	Gartner K, Schenk O. PARDISO: the current state and algorithmic goals for the future. In: Proceedings of the workshop on state-of-the-art in scientific computing, PARA’04; 2004.
[20]	Polizzi, E.; Ben Abdallah, N., Self-consistent three dimensional models for quantum ballistic transport in open systems, Phys rev B, 6, 245301-245309, (2002)
[21]	Tezduyar, T.E.; Sathe, S., Enhanced-approximation linear solution technique (EALST), Comput method appl mech eng, 193, 2033-2049, (2004) · Zbl 1067.76574
[22]	Tezduyar, T.E.; Sathe, S., Enhanced-discretization successive update method (EDSUM), Int J numer methods fluids, 47, 633-654, (2005) · Zbl 1134.76445
[23]	Stein, K.; Tezduyar, T.E.; Benney, R., Automatic mesh update with the solid-extension mesh moving technique, Comput methods appl mech eng, 193, 2019-2032, (2004) · Zbl 1067.74587