×

A tearing-based hybrid parallel sparse linear system solver. (English) Zbl 1193.65029

Summary: We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size of each overlap. Separating these blocks into independent linear systems with the constraint of matching the solution parts of neighboring blocks that correspond to the overlaps, we obtain a balance system. This balance system is not formed explicitly and has a size that is much smaller than the original system.
Our novel solver requires only a one-time factorization of each diagonal block, and in each outer iteration, obtaining only the upper and lower tips of a solution vector where the size of each tip is equal to that of the individual overlap. This scheme proves to be scalable on clusters of nodes in which each node has a multicore architecture. Numerical experiments comparing the scalability of our solver with direct and preconditioned iterative methods are also presented.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F10 Iterative numerical methods for linear systems
65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Schenk, O.; Gärtner, K., Solving unsymmetric sparse systems of linear equations with PARDISO, J. Future Gener. Comput. Syst., 20, 475-487 (2004) · Zbl 1062.65035
[2] Duff, I. S., MA57: a code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Software, 30, 118-144 (2004) · Zbl 1070.65525
[3] Arioli, M.; Demmel, J. W.; Duff, I. S., Solving sparse linear systems with sparse backward error, SIAM J. Matrix Anal. Appl., 10, 165-190 (1989) · Zbl 0684.65022
[4] Davis, T. A.; Duff, I. S., A combined unifrontal/multifrontal method for unsymmetric sparse matrices, ACM Trans. Math. Software, 25, 1-19 (1999) · Zbl 0962.65027
[5] Davis, T. A., Algorithm 832: UMFPACK, an unsymmetric-pattern multifrontal method, ACM Trans. Math. Software, 30, 196-199 (2004) · Zbl 1072.65037
[6] Barrett, R., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), SIAM: SIAM Philadelphia, PA
[7] Golub, G.; Van Loan, C. F., Matrix Computations (1996), The John Hopkins Univ. Press · Zbl 0865.65009
[8] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia, PA · Zbl 1011.65010
[9] Chan, T. C.; van der Vorst, H. A., Approximate and incomplete factorizations, Parallel Numer. Alg., 4, 167-202 (1997) · Zbl 0865.65015
[10] Benzi, M.; Haws, J. C.; Tuma, M., Preconditioning highly indefinite and nonsymmetric matrices, SIAM J. Sci. Comput., 22, 1333-1353 (2000) · Zbl 0985.65036
[13] Polizzi, E.; Sameh, A. H., A parallel hybrid banded system solver: the SPIKE algorithm, Parallel Comput., 32, 177-194 (2006)
[14] Polizzi, E.; Sameh, A. H., SPIKE: a parallel environment for solving banded linear systems, Comput. Fluids, 36, 113-120 (2007) · Zbl 1181.76110
[15] Naumov, M.; Sameh, A., A tearing-based hybrid parallel banded linear system solver, J. Comput. Appl. Math., 226, 306-318 (2009) · Zbl 1170.65025
[18] Liu, W.; Sherman, A. H., Comparative analysis of the Cuthill-McKee and the reverse Cuthill-McKee ordering algorithms for sparse matrices, SIAM J. Numer. Anal., 13, 198-213 (1976) · Zbl 0331.65022
[19] Fiedler, M., Algebraic connectivity of graphs, Czech. Math., 23, 298-305 (1973) · Zbl 0265.05119
[20] Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czech. Math., 25, 619-633 (1975) · Zbl 0437.15004
[21] Spielman, D. A.; Teng, S., Spectral partitioning works: planar graphs and finite element meshes, Linear Algebra Appl., 421, 284-305 (2007) · Zbl 1122.05062
[22] Benzi, M.; Golub, G.; Liensen, J., Numerical solution of saddle point problems, Acta Numer., 1-137 (2005)
[23] Horn, R. A.; Johnson, C. R., Matrix Analysis (1999), Cambridge University Press: Cambridge University Press New York, NY
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.