Abstract
This paper extends the idea of Brezinski’s hybrid acceleration procedure, for the solution of a system of linear equations with a symmetric coefficient matrix of dimension n, to a new context called cooperative computation, involving m agents (m ≪ n), each one concurrently computing the solution of the whole system, using an iterative method. Cooperation occurs between the agents through the communication, periodic or probabilistic, of the estimate of each agent to one randomly chosen agent, thus characterizing the computation as concurrent and asynchronous. Every time one agent receives solution estimates from the others, it carries out a least squares computation, involving a small linear system of dimension m, in order to replace its current solution estimate by an affine combination of the received estimates, and the algorithm continues until a stopping criterion is met. In addition, an autocooperative algorithm, in which estimates are updated using affine combinations of current and past estimates, is also proposed. The proposed algorithms are shown to be efficient for certain matrices, specifically in relation to the popular Barzilai–Borwein algorithm, through numerical experiments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Sparse matrix collection. Available at http://www.cise.ufl.edu/research/sparse/matrices/ (2009)
Abkowicz, A., Brezinski, C.: Acceleration properties of the hybrid procedure for solving linear systems. Appl. Math. 4(23), 417–432 (1996)
Akaike, H.: On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Stat. Math. 11, 1–16 (1959)
Ascher, U., van den Doel, K., Huang, H., Svaiter, B.: On fast integration to steady state and earlier times. Mathematical Modelling and Numerical Analysis 43, 689–708 (2009)
Barzilai, J., Borwein, J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 49, 141–148 (1988)
Bhaya, A., Bliman, P.A., Pazos, F.: Control-theoretic design of iterative methods for symmetric linear systems of equations. In: Proc. of the 48th IEEE Conference on Decision and Control, pp 115–120. Shanghai, China (2009)
Bhaya, A., Bliman, P.A., Pazos, F.: Cooperative parallel asynchronous computation of the solution of symmetric linear systems. In: Proc. of the 49th IEEE Conference on Decision and Control. Atlanta, USA (2010)
Bhaya, A., Kaszkurewicz, E.: Iterative methods as dynamical systems with feedback control. In: Proc. 42nd IEEE Conference on Decision and Control, pp 2374–2380. Maui, Hawaii, USA (2003)
Bhaya, A., Kaszkurewicz, E.: Control perspectives on numerical algorithms and matrix problems. Advances in Control. SIAM Philadelphia (2006)
Bhaya, A., Kaszkurewicz, E.: A control-theoretic approach to the design of zero finding numerical methods. IEEE Trans. Autom. Control 52(6), 1014–1026 (2007)
Brezinski, C.: Multiparameter descent methods. Linear Algebra Appl. 296, 113–141 (1999)
Brezinski, C.: Acceleration procedures for matrix iterative methods. Numerical Algorithms 25, 63–73 (2000)
Brezinski, C.: Block descent methods and hybrid procedures for linear systems. Numerical Agorithms 29, 21–32 (2002)
Brezinski, C., Chehab, J.P.: Nonlinear hybrid procedures and fixed point iterations. Numer. Funct. Anal. Optim. 19, 465–487 (1998)
Brezinski, C., Chehab, J.P.: Multiparameter iterative schemes for the solution of systems of linear and nonlinear equations. SIAM J. Sci. Comp. 20(6), 2140–2159 (1999)
Brezinski, C., Redivo-Zaglia, M.: Hybrid procedures for solving linear systems. Numer. Math. 67, 1–19 (1994)
Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22, 1–10 (2002)
van den Doel, K., Ascher, U.: The chaotic nature of faster gradient descent methods. J. Sci. Comput. 51, 560–581 (2012). doi:10.1007/s10915-011-9521-3
Fletcher, R.: A limited memory steepest descent method. Technical Report, Edinburgh Research Group in Optimization ERGO 09-014, Dept. of Mathematics, University of Dundee, Dundee DD1 4HN, Scotland UK (2009)
Friedlander, A., Martínez, J.M., Molina, B., Raydan, M.: Gradient method with retards and generalizations. SIAM J. Numer. Anal. 36(1), 275–289 (1999)
Greenbaum, A.: Iterative methods for solving linear systems. SIAM Philadelphia (1997)
Nedic, A., Ozdaglar, A.: Convex Optimization in Signal Processing and Communications, chap. Cooperative Distributed Multi-agent Optimization, pp. 340–386 Cambridge University Press (2010)
Pronzato, L., Wynn, H.P., Zhigljavsky, A.A.: Dynamical Search: Applications of Dynamical Systems in Search and Optimization. Chapman and Hall/CRC, Boca Raton (2000)
Strang, G.: Linear algebra and its applications, Harcourt Brace Jovanovich, San Diego California (1988)
Zhou, B., Gao, L., Dai, Y.H.: Gradient methods with adaptive step-sizes. Comput. Optim. Appl. 35, 69–86 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported in part by FAPERJ (CNE grant to the first author) and CNPq (BPP and EU grant to first author, as well as a PNPD fellowship to the third author). The second author’s work was supported by Inria. A preliminary version of this paper appeared in the IEEE Conference on Decision and Control, December 2010, Atlanta, USA [7].
Rights and permissions
About this article
Cite this article
Bhaya, A., Bliman, PA. & Pazos, F. Cooperative concurrent asynchronous computation of the solution of symmetric linear systems. Numer Algor 75, 587–617 (2017). https://doi.org/10.1007/s11075-016-0213-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-016-0213-9