×

A sparse linear system solver used in a distributed and heterogeneous grid computing environment. (English) Zbl 1188.68019

Čiegis, Raimondas (ed.) et al., Parallel scientific computing and optimization. Advances and applications. New York, NY: Springer (ISBN 978-0-387-09706-0/hbk). Springer Optimization and Its Applications 27, 47-56 (2009).
Summary: Many scientific applications need to solve very large sparse linear systems in order to simulate phenomena close to the reality. Grid computing is an answer to the growing demand of computational power. In a grid computing environment, communication times are significant and the bandwidth is variable, therefore frequent synchronizations slow down performances. Thus it is desirable to reduce the number of synchronizations in a parallel direct algorithm. Inspired from multisplitting techniques, the GREMLINS (GRid Efficient Methods for LINear Systems) solver we developed consists of solving several linear problems obtained by splitting. The principle of the balancing algorithm is presented, and experimental results are given.
For the entire collection see [Zbl 1151.65001].

MSC:

68M10 Network design and communication in computer systems
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amestoy, P. R.; Duff, I. S.; Koster, J.; L’Excellent, J. Y., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM Journal of Matrix Analysis and Applications, 23, 1, 15-41 (2001) · Zbl 0992.65018 · doi:10.1137/S0895479899358194
[2] Bahi, J., Couturier, R.: Parallelization of direct algorithms using multisplitting methods in grid environm ents. In: IPDPS 2005, pp. 254b, 8 pages. IEEE Computer Society Press (2005)
[3] Bahi, J. M.; Contassot-Vivier, S.; Couturier, R., Evaluation of the asynchronous iterative algorithms in the context of distant heterogeneous clusters, Parallel Computing, 31, 5, 439-461 (2005) · doi:10.1016/j.parco.2005.02.009
[4] Bahi, J. M.; Contassot-Vivier, S.; Couturier, R.; Vernier, F., A decentralized convergence detection algorithm for asynchronous parallel iterative algorithms, IEEE Transactions on Parallel and Distributed Systems, 1, 4-13 (2005)
[5] Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice Hall, Englewood Cliffs, NJ (1989) · Zbl 0743.65107
[6] Bolze, R.; Cappello, F.; Caron, E.; Dayd, M.; Desprez, F.; Jeannot, E.; Jgou, Y.; Lanteri, S.; Leduc, J.; Melab, N.; Mornet, G.; Namyst, R.; Primet, P.; Quetier, B.; Richard, O.; Talbi, E. G.; Touche, I., Grid’5000: A large scale and highly reconfigurable experimental grid testbed, International Journal of High Performance Computing Applications, 20, 4, 481-494 (2006) · doi:10.1177/1094342006070078
[7] Bruch, J.C.J.: Multisplitting and domain decomposition. In: L.C. Wrobel, C.A. Brebia (eds.) Computational Mechanics International Series On Computational Engineering. Computational methods for free and moving boundary problems in heat and fluid flow, pp. 17-36, Computational Mechanics, Inc. (1993)
[8] Cuthill, E., McKee, J.: Reducing the bandwidth of sparse symmetric matrices. In: Proceedings of the 1969 24th National Conference, pp. 157-172, ACM Press, New York, NY, USA (1969)
[9] Denis, C., Boufflet, J.-P., Breitkopf, P.: A load balancing method for a parallel application based on a domain decomposition. In: International Parallel and Distributed Processing Symposium, 2005. Proceedings 19th IEEE international. pp. 17a - 17a, ISBN: 0-7695-2312-9 (2005). DOI 10.1109/IPDPS.2005.36
[10] Dongarra, J., Lumsdaine, A., Pozo, R., Remington, K.: A sparse matrix library in C++ for high performance architectures. In: Proceedings of the 2nd Annual Object - Oriented Numerics Conference (00N-SKI ’94, Sun River, OR, Apr.), pp. 214-218 (1994)
[11] Karypis, G.; Kumar, V., Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, 48, 96-129 (1988) · doi:10.1006/jpdc.1997.1404
[12] Li, X. S.; Demmel, J. W., SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software, 29, 2, 110-140 (2003) · Zbl 1068.90591 · doi:10.1145/779359.779361
[13] O’Leary, D. P.; White, R. E., Multi-splittings of matrices and parallel solution of linear systems, Journal on Algebraic and Discrete Mathematic, 6, 630-640 (1985) · Zbl 0582.65018 · doi:10.1137/0606062
[14] Scott, J. A., Parallel frontal solvers for large sparse linear systems. ACM Trans, Math. Softw., 29, 4, 395-417 (2003) · Zbl 1072.65041 · doi:10.1145/962437.962440
[15] Scott, N. S.; Jezequel, F.; Denis, C.; Chesneaux, J. M., Numerical ‘health check’ for scientific codes: the cadna approach, Computer Physics Communications, 176, 507-521 (2007) · doi:10.1016/j.cpc.2007.01.005
[16] Verwer, J. G.; Blom, J. G.; Hundsdorfer, W., An implicit-explicit approach for atmospheric transport-chemistry problems, Appl. Numer. Math., 20, 191-209 (1996) · Zbl 0853.76092 · doi:10.1016/0168-9274(95)00126-3
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.