TWO CSCS-BASED ITERATION METHODS FOR SOLVING ABSOLUTE VALUE EQUATIONS

Xianming Gu; Tingzhu Huang; Houbiao Li; Shengfeng Wang; Liang Li

doi:10.11948/2017082

2017 Volume 7 Issue 4

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2017 > 7(4): 1336-1356

Next Article Previous Article

Xianming Gu, Tingzhu Huang, Houbiao Li, Shengfeng Wang, Liang Li. TWO CSCS-BASED ITERATION METHODS FOR SOLVING ABSOLUTE VALUE EQUATIONS[J]. Journal of Applied Analysis & Computation, 2017, 7(4): 1336-1356. doi: 10.11948/2017082

Citation:

Xianming Gu, Tingzhu Huang, Houbiao Li, Shengfeng Wang, Liang Li. TWO CSCS-BASED ITERATION METHODS FOR SOLVING ABSOLUTE VALUE EQUATIONS[J]. Journal of Applied Analysis & Computation, 2017, 7(4): 1336-1356. doi: 10.11948/2017082

TWO CSCS-BASED ITERATION METHODS FOR SOLVING ABSOLUTE VALUE EQUATIONS

School of Mathematical Sciences, University of Electronic Science and Technology of China, No. 2006, Xiyuan Avenue, 611731 Chengdu, China

Fund Project:

Abstract

Abstract

Recently, two families of HSS-based iteration methods are constructed for solving the system of absolute value equations (AVEs), which is a class of non-differentiable NP-hard problems. In this study, we establish the Picard-CSCS iteration method and the nonlinear CSCS-like iteration method for AVEs involving the Toeplitz matrix. Then, we analyze the convergence of the Picard-CSCS iteration method for solving AVEs. By using the theory about nonsmooth analysis, we particularly prove the convergence of the nonlinear CSCS-like iteration solver for AVEs. The advantage of these methods is that they do not require the storage of coefficient matrices at all, and the sub-system of linear equations can be solved efficiently via the fast Fourier transforms (FFTs). Therefore, computational cost and storage can be saved in practical implementations. Numerical examples including numerical solutions of nonlinear fractional diffusion equations are reported to show the effectiveness of the proposed methods in comparison with some existing methods.
- Absolute value equation /
- CSCS-based iteration /
- toeplitz matrix /
- nonsmooth analysis /
- fast Fourier transform
MSC: 65F12;65L05;65N22

FullText(HTML)

References

[1]	J. Y. Bello Cruz, O. P. Ferreira and L. F. Prudente, On the global convergence of the inexact semi-smooth Newton method for absolute value equation, Comput. Optim. Appl., 2016, 65(1), 93-108. Google Scholar
[2]	Z. Z. Bai, G. H. Golub and M. K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 2003, 24(3), 603-626. Google Scholar
[3]	Z. Z. Bai, G. H. Golub and M. K. Ng, On successive overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations, Numer. Linear Algebra Appl., 2007, 14(4), 319-335. Google Scholar
[4]	Z. Z. Bai, G. H. Golub and C. K. Li, Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices, Math. Comp., 2007, 76(257), 287-298. Google Scholar
[5]	Z. Z. Bai and X. Yang, On HSS-based iteration methods for weakly nonlinear systems, Appl. Numer. Math., 2009, 59(12), 2923-2936. Google Scholar
[6]	H. W. Choi, S. K. Chung and Y. J. Lee, Numerical solutions for space fractional dispersion equations with nonlinear source terms, Bull. Korean Math. Soc., 2010, 47(6), 1225-1234. Google Scholar
[7]	L. Caccetta, B. Qu and G. Zhou, A globally and quadratically convergent method for absolute value equations, Comput. Optim. Appl., 2011, 48(1), 45-58. Google Scholar
[8]	F. H. Clarke, Optimization and Nonsmooth Analysis, SIAM, Philadelphia, USA, 1990. Google Scholar
[9]	M. Chen, On the solution of circulant linear systems, SIAM J. Numer. Anal., 1987, 24(3), 668-683. Google Scholar
[10]	R. W. Freund, A transpose-free quasi-minimum residual algorithm for nonHermitian linear systems, SIAM J. Sci. Comput., 1993, 14(2), 470-482. Google Scholar
[11]	X. M. Gu, T. Z. Huang, H. B. Li, L. Li and W. H. Luo, On k-step CSCSbased polynomial preconditioners for Toeplitz linear systems with application to fractional diffusion equations, Appl. Math. Lett., 2015, 42, 53-58. Google Scholar
[12]	S. L. Hu and Z. H. Huang, A note on absolute value equations, Optim. Lett., 2010, 4(3), 417-424. Google Scholar
[13]	S. L. Lei and H. W. Sun, A circulant preconditioner for fractional diffusion equations, J. Comput. Phys., 2013, 242, 715-725. Google Scholar
[14]	O. L. Mangasarian, Absolute value equation solution via concave minimization, Optim. Lett., 2007, 1(1), 3-8. Google Scholar
[15]	H. Moosaei, S. Ketabchi, M. A. Noor, J. Iqbal and V. Hooshyarbakhsh, Some techniques for solving absolute value equations, Appl. Math. Comput., 2015, 268(C), 696-705. Google Scholar
[16]	O. L. Mangasarian, Knapsack feasibility as an absolute value equation solvable by successive linear programming, Optim. Lett., 2009, 3(2), 161-170. Google Scholar
[17]	O. L. Mangasarian and R. R. Meyer, Absolute value equations, Linear Algebra Appl., 2006, 419(2-3), 359-367. Google Scholar
[18]	O. L. Mangasarian, Primal-dual bilinear programming solution of the absolute value equation, Optim. Lett., 2012, 6(7), 1527-1533. Google Scholar
[19]	O. L. Mangasarian, A generalized Newton method for absolute value equations, Optim. Lett., 2009, 3(1), 101-108. Google Scholar
[20]	R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 1977, 15(6), 959-972. Google Scholar
[21]	M. M. Meerschaert and C. Tadjeran, Finite difference approximations for twosided space-fractional partial differential equations, Appl. Numer. Math., 2006, 56(1), 80-90. Google Scholar
[22]	M. A. Noor, J. Iqbal, K. I. Noor and E. Al-Said, On an iterative method for solving absolute value equations, Optim. Lett., 2012, 6(5), 1027-1033. Google Scholar
[23]	M. K. Ng, Iterative Methods for Toeplitz Systems, Oxford University Press, UK, 2004. Google Scholar
[24]	M. K. Ng, Circulant and skew-circulant splitting methods for Toeplitz systems, J. Comput. Appl. Math., 2003, 159(1), 101-108. Google Scholar
[25]	J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, Philadelphia, USA, 2000. Google Scholar
[26]	O. Prokopyev, On equivalent reformulations for absolute value equations, Comput. Optim. Appl., 2009, 44(3), 363-372. Google Scholar
[27]	J. S. Pang and L. Qi, Nonsmooth equations:motivation and algorithms, SIAM J. Optim., 1993, 3(3), 443-465. Google Scholar
[28]	L. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Programming, 1993, 58(1), 353-367. Google Scholar
[29]	L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 1993, 18(1), 227-244. Google Scholar
[30]	W. Qu, S. L. Lei and S. W. Vong, Circulant and skew-circulant splitting iteration for fractional advection-diffusion equations, Int. J. Comput. Math., 2014, 91(10), 2232-2242. Google Scholar
[31]	J. Rohn, A theorem of the alternatives for the equation Ax + B\|x\|=b, Linear and Multilinear Algebra, 2004, 52(6), 421-426. Google Scholar
[32]	J. Rohn, V. Hooshyarbakhsh and R. Farhadsefat, An iterative method for solving absolute value equations and sufficient conditions for unique solvability, Optim. Lett., 2014, 8(1), 35-44. Google Scholar
[33]	D. K. Salkuyeh, The Picard-HSS iteration method for absolute value equations, Optim. Lett., 2014, 8(8), 2191-2202. Google Scholar
[34]	Y. Saad and M. H. Schultz, GMRES:A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 1986, 7(3), 856-869. Google Scholar
[35]	S. L. Wu and P. Guo, On the unique solvability of the absolute value equation, J. Optim. Theory Appl., 2016, 169(2), 705-712. Google Scholar
[36]	H. F. Walker and P. Ni, Anderson acceleration for fixed-point iterations, SIAM J. Numer. Anal., 2011, 49(4), 1715-1735. Google Scholar
[37]	L. Yong, Particle swarm optimization for absolute value equations, J. Comput. Inf. Syst., 2010, 6(7), 2359-2366. Google Scholar
[38]	C. Zhang and Q. J. Wei, Global and finite convergence of a generalized Newton method for absolute value equations, J. Optim. Theory Appl., 2009, 143(2), 391-403. Google Scholar
[39]	J. J. Zhang, The relaxed nonlinear PHSS-like iteration method for absolute value equations, Appl. Math. Comput., 2015, 265, 266-274. Google Scholar
[40]	M. Z. Zhu and G. F. Zhang, On CSCS-based iteration methods for Toeplitz system of weakly nonlinear equations, J. Comput. Appl. Math., 2011, 235(17), 5095-5104. Google Scholar