×

A new stopping criterion for linear perturbed asynchronous iterations. (English) Zbl 1196.65070

Summary: A new stopping criterion is proposed for asynchronous linear fixed point methods in finite precision. The case of absolute error is considered. The originality of this stopping criterion relies on the fact that all tests are made within the same macroiteration.

MSC:

65F10 Iterative numerical methods for linear systems
65G50 Roundoff error
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bahi, J. M.; Contassot-Vivier, S.; Couturier, R., Performance comparison of parallel programming environments for implementing AIAC algorithms, J. Supercomputing, 35, 3, 227-244 (2006)
[2] Bahi, J. M.; Contassot-Vivier, S.; Couturier, R.; Vernier, F., A decentralized convergence detection algorithm for asynchronous parallel iterative algorithms, IEEE Trans. Parallel Distributed Systems, 16, 1, 4-13 (2005)
[3] Baudet, G., Asynchronous iterative methods for multiprocessors, J. Assoc. Comput. Math., 25, 226-244 (1978) · Zbl 0372.68015
[4] Bertsekas, D. P., Distributed asynchronous computation of fixed points, Math. Programming, 27, 107-120 (1983) · Zbl 0521.90089
[5] Bertsekas, D. P.; Tsitsiklis, J. N., Parallel and Distributed Computation: Numerical Methods (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[6] Bertsekas, D. P.; Tsitsiklis, J. N., Parallel and distributed iterative algorithms: a selective survey, Automatica, 25, 3-21 (1991) · Zbl 0728.65041
[7] Blathras, K.; Szyld, D. B.; Shi, Y., Timing models and local criteria for asynchronous iterative algorithms, J. Parallel Distributed Comput., 58, 446-465 (1999)
[8] Chazan, D.; Miranker, W., Chaotic relaxation, Linear Algebra Appl., 2, 455-469 (1969) · Zbl 0225.65043
[9] Chikohora, S.; Evans, D. J., Convergence testing on a distributed network of processors, Internat J. Comput. Math., 70, 357-378 (1998) · Zbl 0918.65021
[10] El Baz, D., A method of terminating asynchronous iterative algorithms on message passing systems, Parallel Algorithms Appl., 5, 187-205 (1996)
[11] D. El Baz, An efficient termination method for asynchronous iterative algorithms on message passing architectures, in: Proceedings of the International Conference on Parallel and Distributed Computing Systems,vol. 1, Dijon, 1996, pp. 1-7.; D. El Baz, An efficient termination method for asynchronous iterative algorithms on message passing architectures, in: Proceedings of the International Conference on Parallel and Distributed Computing Systems,vol. 1, Dijon, 1996, pp. 1-7.
[12] El Baz, D.; Spiteri, P.; Miellou, J. C.; Jarraya, M., Mathematical study of perturbed asynchronous iterations for designed termination, Internat. Math. J., 1, 5, 491-503 (2002) · Zbl 1221.65134
[13] El Tarazi, M. N., Some convergence results for asynchronous algorithms, Numer. Math., 39, 325-340 (1982) · Zbl 0479.65030
[14] C. Engelmann, A. Geist, Super-scalable algorithms for computing on 100 000 processors, in: Proceedings of the 5th International Conference on Computational Science (ICCS) 2005, May 22-25, Atlanta, GA, Part I, Lecture Notes in Computer Science; vol. 3514, 2005, 313-320.; C. Engelmann, A. Geist, Super-scalable algorithms for computing on 100 000 processors, in: Proceedings of the 5th International Conference on Computational Science (ICCS) 2005, May 22-25, Atlanta, GA, Part I, Lecture Notes in Computer Science; vol. 3514, 2005, 313-320.
[15] Frommer, A.; Schwandt, H.; Szyld, D., Asynchronous weighted additive Schwarz methods, ETNA, 5, 48-61 (1997) · Zbl 0890.65027
[16] Frommer, A.; Szyld, D., On asynchronous iterations, J. comput. Appl. Math., 123, 201-216 (2000) · Zbl 0967.65066
[17] Golub, G. H.; Van Loan, C. F., Matrix Computations (1989), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0733.65016
[18] G. Kollias, E. Gallopoulos, D. Szyld, Asynchronous Iterative Computations With Web Information Retrieval Structures: The Pagerank Case, John von Neumann Institute for Computing, NIC Series, vol. 33 (2006) pp. 309-316.; G. Kollias, E. Gallopoulos, D. Szyld, Asynchronous Iterative Computations With Web Information Retrieval Structures: The Pagerank Case, John von Neumann Institute for Computing, NIC Series, vol. 33 (2006) pp. 309-316.
[19] Miellou, J. C., Itérations chaotiques \(\overset{`}{a}\) retards, RAIRO, R1, 55-82 (1975) · Zbl 0329.65038
[20] Miellou, J. C.; Cortey-Dumont, P.; Boulbrachêne, M., Perturbation of fixed point iterative methods, Adv. Parallel Comput., I, 81-122 (1990)
[21] Miellou, J. C.; Spiteri, P.; El Baz, D., Stopping criteria, forward and backward errors for perturbed asynchronous linear fixed point methods in finite precision, IMA J. Numer. Anal., 25, 429-442 (2005) · Zbl 1079.65032
[22] Rigal, J. L.; Gaches, J., On the compatibility of a given solution with the data of a linear system, J. Assoc. Comput. Math., 14, 3, 543-548 (1967) · Zbl 0183.17704
[23] Savari, S. A.; Bertsekas, D. P., Finite termination of asynchronous iterative algorithms, Parallel Comput., 22, 1, 39-56 (1996) · Zbl 0873.65018
[24] Spiteri, P.; Miellou, J. C.; El Baz, D., Perturbation of parallel asynchronous linear iterations by floating point errors, Electron. Trans. on Numer. Anal., 13, 55-63 (2002) · Zbl 1024.65028
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.