| Citation: |
Liang Zhao, Tingzhu Huang, Liangjian Deng. KRYLOV SUBSPACE METHODS WITH DEFLATION AND BALANCING PRECONDITIONERS FOR LEAST SQUARES PROBLEMS[J]. Journal of Applied Analysis & Computation, 2019, 9(1): 57-74. doi: 10.11948/2019.57
|
KRYLOV SUBSPACE METHODS WITH DEFLATION AND BALANCING PRECONDITIONERS FOR LEAST SQUARES PROBLEMS
-
Abstract
For solving least squares problems, the CGLS method is a typical method in the point of view of iterative methods. When the least squares problems are ill-conditioned, the convergence behavior of the CGLS method will present a deteriorated result. We expect to select other iterative Krylov subspace methods to overcome the disadvantage of CGLS. Here the GMRES method is a suitable algorithm for the reason that it is derived from the minimal residual norm approach, which coincides with least squares problems. Ken Hayami proposed BAGMRES for solving least squares problems in [GMRES Methods for Least Squares Problems, SIAM J. Matrix Anal. Appl., 31(2010), pp.2400-2430]. The deflation and balancing preconditioners can optimize the convergence rate through modulating spectral distribution. Hence, in this paper we utilize preconditioned iterative Krylov subspace methods with deflation and balancing preconditioners in order to solve ill-conditioned least squares problems. Numerical experiments show that the methods proposed in this paper are better than the CGLS method. -
-
References
[1] A. Björck, Numerical methods for least squares problems, SIAM, Philadelphia, 1996. [2] X. Cui, K. Hayami and J.-F. Yin, Greville's method for preconditioning least squares problems, in Proceeding of the ALGORITMY 2009, Podbanské, Slovakia, 2009. [3] L. J. Deng, T. Z. Huang and X. L. Zhao, Wavelet-based two-level methods for image restoration, Commu. Nonlinear Sci. and Num. Simu., 2012, 17, 5079-5087. doi: 10.1016/j.cnsns.2012.04.001 [4] Y. A. Erlangga and R. Nabben, Deflation and balancing preconditioners for Krylov subspace methods applied to nonsymmetric matrices, SIAM J. Matrix Anal. Appl., 2008, 30, 684-699. doi: 10.1137/060678257 [5] Y. A. Erlangga and R. Nabben, Multilevel projection-based nested Krylov iteration for boundary value problems, SIAM J. Sci. Comput., 2008, 30, 1572-1595. doi: 10.1137/070684550 [6] J. Frank and C. Vuik, On the construction of deflation-based preconditioners, SIAM J. Sci. Comput., 2001, 23, 442-462. doi: 10.1137/S1064827500373231 [7] R. Fletcher, Conjugate gradient methods for indefinite systems, Springer-Verlag, Berlin-Heidelberg-New York, 1976. [8] J. Huang, T. Z. Huang, X. L. Zhao, Z. Xu and X. G. Lv, Two soft-thresholding based iterative algorithms for image deblurring, Infor. Sci., 2014, 271, 179-195. doi: 10.1016/j.ins.2014.02.089 [9] K. Hayami and T. Ito, Solution of least squares problems using GMRES methods, Proc. Inst. Statist. Math., 2005, 53, 331-348 (in Japanese). [10] K. Hayami, J. Yin and T. Ito, GMRES Methods for least squares problems, SIAM J. Matrix Anal. Appl., 2010, 31, 2400-2430. doi: 10.1137/070696313 [11] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985. [12] T. Ito and K. Hayami, Preconditioned GMRES methods for least squares problems, Japan. J. Indust. Appl. Math., 2008, 25, 185-207. doi: 10.1007/BF03167519 [13] J. Mandel, Balancing domain decomposition, Comm. Numer. Methods Engrg., 1993, 9, 233-241. doi: 10.1002/cnm.1640090307 [14] L. Mansfield, Damped Jacobi preconditioning and coarse grid deflation for conjugate gradient iteration on parallel computers, SIAM J. Sci. Statist. Comput., 1991, 12, 1314-1323. doi: 10.1137/0912071 [15] R. A. Nicolaides, Deflation of conjugate gradients with applications to boundary value problems, SIAM J. Numer. Anal., 1987, 24, 355-365. doi: 10.1137/0724027 [16] R. Nabben and C. Vuik, A comparision of deflation and balancing preconditioner, SIAM J. Sci.Comput., 2006, 27, 1742-1759. doi: 10.1137/040608246 [17] C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of liear equations, SIAM J. Numer. Anal., 1975, 12, 617-629. doi: 10.1137/0712047 [18] D. L. Sun, T. Z. Huang, B. Carpentieri and Y. F. Jing, A new shifted block GMRES method with inexact breakdowns for solving multi-shifted and multiple right-hand sides linear systems, J. Sci. Comp., 2018. DOI: 10.1007/s10915-018-0787-6. [19] D. L. Sun, T. Z. Huang, Y. F. Jing and B. Carpentieri, A block GMRES method with deflated restarting for solving linear systems with multiple shifts and multiple right-hand sides, Num. Linear Alg. with App., 2018. DOI: 10.1002/nla.2148. [20] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003. [21] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 1986, 7, 865-869. [22] H. A. Van Der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, Cambridge, UK, 2003. [23] R. Weiss, Error-minimizing Krylov subspace methods, SIAM J. Sci. Comput., 1994, 15, 511-527. doi: 10.1137/0915034 [24] L. Zhao, T. Z. Huang, Y. F. Jing and L. J. Deng, A generalized product-type BiCOR method and its application in signal deconvolution, Computer & Math. with App., 2013, 66, 1372-1388. [25] L. Zhao, T. Z. Huang, L. Zhu and L. J. Deng, Golub-Kahan-Lanczos based preconditioner for least squares problems in overdetermined and underdetermined cases, J. Comput. Ana. & App., 2017, 23. [26] X. L. Zhao, W. Wang, T. Y. Zeng, T. Z. Huang and M. K. Ng, Total variation structured total least squares method for image restoration, SIAM J. Sci. Comp., 2013, 35, 1304šC-1320. doi: 10.1137/130915406 [27] X. L. Zhao, F. Wang and M. K. Ng, A new convex optimization model for multiplicative noise and blur removal, SIAM J. Imag. Sci., 2014, 7, 456-475. doi: 10.1137/13092472X [28] X. L. Zhao, T. Z. Huang, X. G. Lv, Z. B. Xu and J. Huang, Kronecker product approximations for image restoration with new mean boundary conditions, App. Math. Model., 2012, 36, 225-237. doi: 10.1016/j.apm.2011.05.050 -
-
Figures(6)
Export File
Citation
Liang Zhao, Tingzhu Huang, Liangjian Deng. KRYLOV SUBSPACE METHODS WITH DEFLATION AND BALANCING PRECONDITIONERS FOR LEAST SQUARES PROBLEMS[J]. Journal of Applied Analysis & Computation, 2019, 9(1): 57-74. doi: 10.11948/2019.57
Format
Content
DownLoad:
-
Figure 1.
$ \|A^{T}r\|_{2}/\|A^{T}b\|_{2} $ $ vs $ . iterations ($ m = 5000 $ ,$ n = 1000 $ , density = 0.01, condition number =$ 10^{6} $ ,$ r = 50 $ ) -
Figure 2.
$ \|A^{T}r\|_{2}/\|A^{T}b\|_{2} $ $ vs $ . iterations ($ m = 5000 $ ,$ n = 1000 $ , density = 0.01, condition number =$ 10^{6} $ ,$ r = 50 $ ) -
Figure 3.
$ \|A^{T}r\|_{2}/\|A^{T}b\|_{2} $ $ vs $ . iterations ($ m = 5000 $ ,$ n = 1000 $ , density = 0.01, condition number =$ 10^{6} $ ,$ r = 50 $ ) -
Figure 4.
$ \|A^{T}r\|_{2}/\|A^{T}b\|_{2} $ $ vs $ . iterations ($ m = 5000 $ ,$ n = 1000 $ , density = 0.01, condition number =$ 10^{8} $ ,$ r = 50 $ ) -
Figure 5.
$ \|A^{T}r\|_{2}/\|A^{T}b\|_{2} $ $ vs $ . iterations ($ m = 5000 $ ,$ n = 1000 $ , density = 0.01, condition number =$ 10^{8} $ ,$ r = 50 $ ) -
Figure 6.
$ \|A^{T}r\|_{2}/\|A^{T}b\|_{2} $ $ vs $ . iterations ($ m = 5000 $ ,$ n = 1000 $ , density = 0.01, condition number =$ 10^{8} $ ,$ r = 50 $ )