Abstract
A block iterative method is used for solving linear least squares problems. The subproblems are solved asynchronously on a distributed memory multiprocessor. It is observed that an increased number of processors results in deteriorating rate of convergence. This deteriorating convergence is illustrated by numerical experiments. The deterioration of the convergence can be explained by contamination of the residual. Our purpose is to show that the residual is contaminated by old information. The issues investigated here are the effect of the number of processors, the role of essential neighbors, and synchronization. The characterization of old information remains an open problem.
This research is supported by The Research Council of Norway.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baudet, G. M.: Asynchronous Iterative Methods for Multiprocessors. Journal of the ACM. 25 (1978) 226–244
Bertsekas, D. P., Tsitsiklis, J. N.: Parallel and Distributed Computation, Numerical Methods. Prentice-Hall Inc., Englewood Cliffs, N. J. (1989)
Björck, Å.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia, PA (1996)
Dennis, J. E. Jr., Steihaug, T.: On the Successive Projections Approach to Least Squares Problems. SIAM J. Numer. Anal. 23 (1986) 717–733
Duff, I., Grimes, R. G., Lewis, J0. G.: User's Guide for the Harwell-Boeing Sparse Matrix Collection. Technical Report TR/PA/92/86, CERFACS (1992)
Elsner, L., Neumann, M., Vemmer, B.: The Effect of the Number of Processors on the Convergence of the Parallel Block Jacobi Method. Lin. Alg. Appl. 154-156 (1991) 311–330
George, J. A., Heath, M. T.: Solution of Sparse Linear Least Squares Problems Using Givens Rotations. Lin. Alg. Appl. 34 (1980) 69–83
Kolm, P., Arbenz, P., Gander, W.: Generalized Subspace Correction Methods for Parallel Solution of Linear Systems. Technical Report TRITA-NA-9509, C2M2, Nada, KTH, Sweden (1995)
Savari, S. A., Bertsekas, D. P.: Finite Termination of Asynchronous Iterative Algorithms. Parallel Computing. 22 (1996) 39–56
Steihaug, T., Yalçinkaya, Y.: Asynchronous Methods and Least Squares: An Example of Deteriorating Convergence. Technical Report No. 131. Department of Informatics, University of Bergen, Bergen, Norway (1997)
Yalçinkaya, Y.: Asynchronous Solution of Linear Least Squares Problems Using Generalized Group Iterative Methods. Master's thesis. University of Bergen, Norway (1995)
Yalçinkaya, Y., Steihaug, T.: Asynchronous Methods and Least Squares: An Example of Deteriorating Convergence. Proceedings of the 15th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics, August 24–29, 1997, Berlin, Germany (to appear) [part of [10]]
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Steihaug, T., Yalçinkaya, Y. (1997). Deteriorating convergence for asynchronous methods on linear least squares problems. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002809
Download citation
DOI: https://doi.org/10.1007/BFb0002809
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive