×

A proportional-derivative control strategy for restarting the GMRES(\(m\)) algorithm. (English) Zbl 1524.65144

Summary: Restarted GMRES (or GMRES(\(m\))) is normally used for solving large linear systems \(A x = b\) with a general, possibly nonsymmetric, matrix \(A\). Although, the restarted GMRES consumes less computational time than its counterpart full GMRES, if the restarting parameter is not correctly chosen its convergence cannot be guaranteed and the method may converge slowly. Unfortunately, it is difficult to know how to choose this parameter a priori. In this article, we regard the GMRES(\(m\)) method as a control problem, in which the parameter \(m\) is the controlled variable and propose a new control-inspired strategy for choosing the parameter \(m\) adaptively at each iteration. The advantage of this control strategy method is that only a few additional vectors need to be stored and the controller has the capacity to modify the dimension of the Krylov subspace whenever any convergence problem is detected. Numerical experiments, based on benchmark problems, show that the proposed control strategy accelerates the convergence of GMRES(\(m\)).

MSC:

65F10 Iterative numerical methods for linear systems

Software:

SparseMatrix
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Saad, Y.; Schultz, M. H., GMRES: a generalized minimal residual method for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[2] Ipsen, I. C.F.; Meyer, C. D., The idea behind Krylov methods, Amer. Math. Monthly, 105, 889-899 (1997) · Zbl 0982.65034
[3] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1002.65042
[4] Greenbaum, A., Iterative Methods for Solving Linear Systems (1997), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 0883.65022
[5] Simoncini, V.; Szyld, D. B., Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14, 1, 1-59 (2007) · Zbl 1199.65112
[6] Baker, A. H.; Jessup, E. R.; Manteuffel, T., A technique for accelerating the convergence of restarted GMRES, SIAM J. Matrix Anal. Appl., 26, 4, 962-984 (2005) · Zbl 1086.65025
[7] Gonçalez, T.; da Cunha, R., Seleção dinâmica da dimensão do subespaço de Krylov no método GMRES \((m)\) e suas variantes, TEMA: Tend. Mat. Apl. Comput., 7, 277-286 (2006) · Zbl 1208.65043
[8] Embree, M., The tortoise and the hare restart GMRES, SIAM Rev., 45, 259-266 (2003) · Zbl 1027.65039
[9] Zítko, J., Some remarks on the restarted and augmented GMRES method, Electron. Trans. Numer. Anal. - ETNA, 31, 221-227 (2008) · Zbl 1171.65024
[10] Eiermann, M.; Ernst, O. G.; Schneider, O., Analysis of acceleration strategies for restarted minimal residual methods, J. Comput. Appl. Math., 123, 261-292 (2000) · Zbl 0968.65016
[11] Joubert, W., On the convergence behavior of the restarted GMRES algorithm for solving nonsymmetric linear systems, Numer. Linear Algebra Appl., 1, 5, 427-447 (1994) · Zbl 0838.65029
[12] Schaerer, C. E.; Kaszkurewicz, E., The shooting method for the solution of ordinary differential equations: a control-theoretical perspective, Int. J. Syst. Sci., 32, 8, 1047-1053 (2001) · Zbl 1040.93019
[13] Bhaya, A.; Kaszkurewicz, E., Control Perspectives on Numerical Algorithms and Matrix Problems (2006), SIAM, Philadelphia: SIAM, Philadelphia Philadelphia, PA, USA · Zbl 1128.93001
[14] Bhaya, A.; Kaszkurewicz, E., A control-theoretic approach to the design of zero finding numerical methods, IEEE Trans. Automat. Control, 52, 6, 1014-1026 (2007) · Zbl 1366.93171
[15] Karafyllis, I., Feedback stabilization methods for the solution of nonlinear programming problems, J. Optim. Theory Appl., 161, 783-806 (2014) · Zbl 1312.90075
[16] Goh, B.; Leong, W.; Teo, K., Robustness of convergence proofs in numerical methods in unconstrained optimization, (Optimization and Control Methods in Industrial Engineering and Construction. Intelligent Systems, Control and Automation: Science and Engineering, Vol. 72 (2014), Springer), 1-9
[17] Pazos, F.; Bhaya, A., Adaptive choice of the Tikhonov regularization parameter to solve ill-posed linear algebraic equations via Liapunov optimizing control, J. Comput. Appl. Math., 279, 123-132 (2015) · Zbl 1306.65194
[18] Gustafsson, K.; Lundh, M.; Söderlind, G., A PI stepsize control for the numerical solution of ordinary differential equations, BIT, 28, 2, 270-287 (1988) · Zbl 0645.65039
[19] Kashima, K.; Yamamoto, Y., System theory for numerical analysis, Automatica, 43, 7, 1156-1164 (2007) · Zbl 1123.93016
[20] Yang, Y.; Ding, S. X., A control-theoretic study on iterative solutions to nonlinear equations for applications in embedded systems, Automatica, 48, 583-594 (2012) · Zbl 1238.93042
[21] Kaszkurewicz, E.; Bhaya, A.; Ramos, P. R.V., A control-theoretic view of diagonal preconditioners, Int. J. Syst. Sci., 26, 9, 1659-1672 (1995) · Zbl 0830.93037
[22] U. Helmke, J. Jordan, A. Lanzon, A control theory approach to linear equation solvers, in: Proceedings 17th International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, 2006, pp. 1401-1407.; U. Helmke, J. Jordan, A. Lanzon, A control theory approach to linear equation solvers, in: Proceedings 17th International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, 2006, pp. 1401-1407.
[23] Helmke, U.; Jordan, J., Control and stabilization of linear equation solvers, (Willems, J. C.; Hara, S.; Ohta, Y.; Fujioka, H., Perspectives in Mathematical System Theory, Control, and Signal Processing: A Festschrift in Honor of Yutaka Yamamoto on the Occasion of his 60th Birthday (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 73-82 · Zbl 1198.93093
[24] Xie, L.; Liu, Y.; Yang, H., Gradient based and least squares based iterative algorithms for matrix equations \(A X B + C X^T D = F\), Appl. Math. Comput., 217, 2191-2199 (2010) · Zbl 1210.65097
[25] Zhang, H.; Ding, F., Iterative algorithms for \(X + A^T X^{- 1} A = I\) by using the hierarchical identification principle, J. Franklin Inst. B, 353, 1132-1146 (2016) · Zbl 1336.93066
[26] Gomes-Ruggiero, M. A.; Lopes, V. L.R.; Toledo-Benavides, J. V., A safeguard approach to detect stagnation of GMRES \((m)\) with applications in Newton - Krylov methods, Comput. Appl. Math., 27, 175-199 (2008) · Zbl 1158.65036
[27] Brezinski, C., Hybrid methods for solving systems of equations, (Althaus, G. W.; Spedicato, E., Algorithms for Sparse Large Scale Linear Algebraic Systems (1998)), 271-290 · Zbl 0898.65017
[28] Baker, A.; Jessup, E.; Kolev, T., A simple strategy for varying the restart parameter in GMRES \((m)\), J. Comput. Appl. Math., 230, 2, 751-761 (2009) · Zbl 1169.65024
[29] Sosonkina, M.; Watson, L. T.; Kapania, R. K.; Walker, H. F., A new adaptive GMRES algorithm for achieving high accuracy, Numer. Linear Algebra Appl., 5, 4, 275-297 (1998) · Zbl 0937.65037
[30] M. Habu, T. Nodera, GMRES \((m\); M. Habu, T. Nodera, GMRES \((m\) · Zbl 1017.65026
[31] Moriya, K.; Nodera, T., New adaptive GMRES \((m)\) method with choosing suitable restart cycle \(m\), (Wyrzykowski, R.; Dongarra, J.; Paprzycki, M.; Waśniewski, J., Parallel Processing and Applied Mathematics: 5th International Conference, PPAM 2003, Czestochowa, Poland, September 7-10, 2003 (2004), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 1105-1113 · Zbl 1128.65303
[32] L. Zhang, T. Nodera, A new adaptive restart for GMRES \((m\); L. Zhang, T. Nodera, A new adaptive restart for GMRES \((m\) · Zbl 1078.65536
[33] Morgan, R. B., A restarted GMRES method augmented with eigenvectors, SIAM J. Matrix Anal. Appl., 16, 4, 1154-1171 (1995) · Zbl 0836.65050
[34] Morgan, R. B., Implicitly restarted GMRES and Arnoldi methods for nonsymmetric systems of equations, SIAM J. Matrix Anal. Appl., 21, 4, 1112-1135 (2000) · Zbl 0963.65038
[35] Strecj, V., State Space Theory of Discrete Linear Control (1981), John Wiley & Sons
[36] Ding, F.; Liu, X.; Ma, X., Kalman state filtering based least squares iterative parameter estimation for observer canonical state space systems using decomposition, J. Comput. Appl. Math., 301, 135-143 (2016) · Zbl 1382.93032
[37] Eiermann, M.; Ernst, O., Geometric aspects of the theory of Krylov subspace methods, Acta Numer., 10, 251-312 (2001) · Zbl 1105.65328
[38] Zhong, B.; Morgan, R. B., Complementary cycles of restarted GMRES, Numer. Linear Algebra Appl., 15, 6, 559-571 (2008) · Zbl 1212.65147
[39] Visioli, A., Practical PID Control (Advances in Industrial Control) (2006), Springer-Verlag
[40] Xu, L., A proportional differential control method for a time-delay system using Taylor expansion approximation, Appl. Math. Comput., 236, 391-399 (2014) · Zbl 1334.93125
[41] Xu, L., Application of the Newton iteration algorithm to the parameter estimation for dynamical systems, J. Comput. Appl. Math., 288, 33-43 (2015) · Zbl 1314.93062
[42] Ding, F.; Zhang, H., Gradient-based iterative algorithm for a class of the coupled matrix equations related to control systems, IET Control Theory Appl., 8, 1588-1595 (2014)
[43] Xu, L.; Ding, F., The parameter estimation algorithms for dynamical response signals based on the multi-innovation theory and the hierarchical principle, IET Signal Process., 11, 2, 228-237 (2017)
[44] Ding, F.; Liu, X.; Gu, Y., An auxiliary model based least squares algorithm for a dual-rate state space system with time-delay using the data filtering, J. Franklin Inst. B, 353, 2, 398-408 (2016) · Zbl 1395.93530
[45] Davis, T. A.; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38, 1, 1:1-1:25 (2011) · Zbl 1365.65123
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.