SPIKE: A parallel environment for solving banded linear systems. (English) Zbl 1181.76110
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 |
References:
| [1] | Polizzi E, Sameh A. A parallel hybrid system solver: the SPIKE algorithm. Parallel Comput 2005 [to appear].; 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, (Kuck, D.; Lawrie, D.; Sameh, A., High speed computer and algorithm organization (1977), Academic Press: Academic Press New York), 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.; 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, (Proc of NATO adv res workshop on high-speed comp. Proc of NATO adv res workshop on high-speed comp, Series F: computer and systems sciences, vol. 7 (1983), Springer: Springer Berlin), 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.; 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, (Handler, W.; etal., CONPAR 86, lecture notes in computer science (1986), Springer: Springer Berlin), 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.: 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.; 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, (Amestoy, P.; Berger, Ph.; Dayd, M.; Duff, I.; Frayss, V.; Giraud, L.; Ruiz, D., EuroPar ’99 parallel processing (1999), Springer: Springer Berlin), 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.: 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.; 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 |
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.
