• Previous Article
    A hybrid parametrization approach for a class of nonlinear optimal control problems
  • NACO Home
  • This Issue
  • Next Article
    $ \theta $ scheme with two dimensional wavelet-like incremental unknowns for a class of porous medium diffusion-type equations
December  2019, 9(4): 483-492. doi: 10.3934/naco.2019033

A preconditioned SSOR iteration method for solving complex symmetric system of linear equations

Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

*Corresponding author

Received  August 2018 Revised  April 2019 Published  May 2019

We present a preconditioned version of the symmetric successive overrelaxation (SSOR) iteration method for a class of complex symmetric linear systems. The convergence results of the proposed method are established and conditions under which the spectral radius of the iteration matrix of the method is smaller than that of the SSOR method are analyzed. Numerical experiments illustrate the theoretical results and depict the efficiency of the new iteration method.

Citation: Tahereh Salimi Siahkolaei, Davod Khojasteh Salkuyeh. A preconditioned SSOR iteration method for solving complex symmetric system of linear equations. Numerical Algebra, Control and Optimization, 2019, 9 (4) : 483-492. doi: 10.3934/naco.2019033
References:
[1]

O. Axelsson and A. Kucherov, Real valued iterative methods for solving complex symmetric linear systems, Numer. Linear Algebra Appl., 7 (2000), 197-218.  doi: 10.1002/1099-1506(200005)7:4<197::AID-NLA194>3.0.CO;2-S.

[2]

Z.-Z. BaiM. Benzi and F. Chen, Modified HSS iteration methods for a class of complex symmetric linear systems, Computing, 87 (2010), 93-111.  doi: 10.1007/s00607-010-0077-0.

[3]

Z.-Z. BaiM. Benzi and F. Chen, On preconditioned MHSS iteration methods for complex symmetric linear systems, Numer. Algor., 56 (2011), 297-317.  doi: 10.1007/s11075-010-9441-6.

[4]

Z.-Z. Bai, Rotated block triangular preconditioning based on PMHSS, Sci. China Math., 56 (2013), 2523-2538.  doi: 10.1007/s11425-013-4695-9.

[5]

Z.-Z. BaiG. H. Golub and M. K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM. J. Matrix Anal. Appl., 24 (2003), 603-626.  doi: 10.1137/S0895479801395458.

[6]

Z.-Z. BaiM. BenziF. Chen and Z.-Q. Wang, Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems, IMA J. Numer. Anal., 33 (2013), 343-369.  doi: 10.1093/imanum/drs001.

[7]

Z.-Z. BaiB. N. Parlett and Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102 (2005), 1-38.  doi: 10.1007/s00211-005-0643-0.

[8]

M. Benzi and D. Bertaccini, Block preconditioning of real-valued iterative algorithms for complex linear systems, IMA J. Numer. Anal., 28 (2008), 598-618.  doi: 10.1093/imanum/drm039.

[9]

M. Benzi and G. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26 (2004), 20-41.  doi: 10.1137/S0895479802417106.

[10]

M. BenziG. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numerica, 14 (2005), 1-137.  doi: 10.1017/S0962492904000212.

[11]

A. Bunse-Gerstner and R. Stover, On a conjugate gradient-type method for solving complex symmetric linear systems, Linear Algebra Appl., 287 (1999), 105-123.  doi: 10.1016/S0024-3795(98)10091-5.

[12]

M. DehghanM. M. Dehghani and M. Hajarian, A generalized preconditioned MHSS method for a class of complex symmetric linear systems, J. Math. Model. Anal., 18 (2013), 561-576.  doi: 10.3846/13926292.2013.839964.

[13]

V. EdalatpourD. Hezari and D. K. Salkuyeh, Two efficient inexact algorithms for a class of large sparse complex linear systems, Mediterr. J. Math., 13 (2016), 2301-2318.  doi: 10.1007/s00009-015-0621-4.

[14]

G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996.

[15]

D. HezariD. K. Salkuyeh and V. Edalatpour, A new iterative method for solving a class of complex symmetric system of linear equathions, Numer. Algor., 73 (2016), 927-955.  doi: 10.1007/s11075-016-0123-x.

[16]

D. HezariV. Edalatpour and D. K. Salkuyeh, Preconditioned GSOR iterative method for a class of complex symmetric system of linear equations, Numer. Linear Algebera Appl., 22 (2015), 761-776.  doi: 10.1002/nla.1987.

[17]

Z.-Z. Liang and G.-F. Zhang, On SSOR iteration method for a class of block two-by-wo linear systems, Numer. Algor., 71 (2016), 655-671.  doi: 10.1007/s11075-015-0015-5.

[18]

D. K. SalkuyehD. Hezari and V. Edalatpour, Generalized successive overrelaxation iterative method for a class of complex symmetric linear system of equations, Int. J. Comput. Math., 92 (2015), 802-815.  doi: 10.1080/00207160.2014.912753.

[19]

D. K. Salkuyeh and T. S. Siahkolaei, Two-parameter TSCSP method for solving complex symmetric system of linear equations, Calcolo, 55 (2018), 8. doi: 10.1007/s10092-018-0252-9.

[20]

G.-F. Zhang and Z. Zheng, A parameterized splitting iteration methods for complex symmetric linear systems, Jpn. J. Indust. Appl. Math., 31 (2014), 265-278.  doi: 10.1007/s13160-014-0140-x.

show all references

References:
[1]

O. Axelsson and A. Kucherov, Real valued iterative methods for solving complex symmetric linear systems, Numer. Linear Algebra Appl., 7 (2000), 197-218.  doi: 10.1002/1099-1506(200005)7:4<197::AID-NLA194>3.0.CO;2-S.

[2]

Z.-Z. BaiM. Benzi and F. Chen, Modified HSS iteration methods for a class of complex symmetric linear systems, Computing, 87 (2010), 93-111.  doi: 10.1007/s00607-010-0077-0.

[3]

Z.-Z. BaiM. Benzi and F. Chen, On preconditioned MHSS iteration methods for complex symmetric linear systems, Numer. Algor., 56 (2011), 297-317.  doi: 10.1007/s11075-010-9441-6.

[4]

Z.-Z. Bai, Rotated block triangular preconditioning based on PMHSS, Sci. China Math., 56 (2013), 2523-2538.  doi: 10.1007/s11425-013-4695-9.

[5]

Z.-Z. BaiG. H. Golub and M. K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM. J. Matrix Anal. Appl., 24 (2003), 603-626.  doi: 10.1137/S0895479801395458.

[6]

Z.-Z. BaiM. BenziF. Chen and Z.-Q. Wang, Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems, IMA J. Numer. Anal., 33 (2013), 343-369.  doi: 10.1093/imanum/drs001.

[7]

Z.-Z. BaiB. N. Parlett and Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102 (2005), 1-38.  doi: 10.1007/s00211-005-0643-0.

[8]

M. Benzi and D. Bertaccini, Block preconditioning of real-valued iterative algorithms for complex linear systems, IMA J. Numer. Anal., 28 (2008), 598-618.  doi: 10.1093/imanum/drm039.

[9]

M. Benzi and G. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26 (2004), 20-41.  doi: 10.1137/S0895479802417106.

[10]

M. BenziG. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numerica, 14 (2005), 1-137.  doi: 10.1017/S0962492904000212.

[11]

A. Bunse-Gerstner and R. Stover, On a conjugate gradient-type method for solving complex symmetric linear systems, Linear Algebra Appl., 287 (1999), 105-123.  doi: 10.1016/S0024-3795(98)10091-5.

[12]

M. DehghanM. M. Dehghani and M. Hajarian, A generalized preconditioned MHSS method for a class of complex symmetric linear systems, J. Math. Model. Anal., 18 (2013), 561-576.  doi: 10.3846/13926292.2013.839964.

[13]

V. EdalatpourD. Hezari and D. K. Salkuyeh, Two efficient inexact algorithms for a class of large sparse complex linear systems, Mediterr. J. Math., 13 (2016), 2301-2318.  doi: 10.1007/s00009-015-0621-4.

[14]

G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996.

[15]

D. HezariD. K. Salkuyeh and V. Edalatpour, A new iterative method for solving a class of complex symmetric system of linear equathions, Numer. Algor., 73 (2016), 927-955.  doi: 10.1007/s11075-016-0123-x.

[16]

D. HezariV. Edalatpour and D. K. Salkuyeh, Preconditioned GSOR iterative method for a class of complex symmetric system of linear equations, Numer. Linear Algebera Appl., 22 (2015), 761-776.  doi: 10.1002/nla.1987.

[17]

Z.-Z. Liang and G.-F. Zhang, On SSOR iteration method for a class of block two-by-wo linear systems, Numer. Algor., 71 (2016), 655-671.  doi: 10.1007/s11075-015-0015-5.

[18]

D. K. SalkuyehD. Hezari and V. Edalatpour, Generalized successive overrelaxation iterative method for a class of complex symmetric linear system of equations, Int. J. Comput. Math., 92 (2015), 802-815.  doi: 10.1080/00207160.2014.912753.

[19]

D. K. Salkuyeh and T. S. Siahkolaei, Two-parameter TSCSP method for solving complex symmetric system of linear equations, Calcolo, 55 (2018), 8. doi: 10.1007/s10092-018-0252-9.

[20]

G.-F. Zhang and Z. Zheng, A parameterized splitting iteration methods for complex symmetric linear systems, Jpn. J. Indust. Appl. Math., 31 (2014), 265-278.  doi: 10.1007/s13160-014-0140-x.

Table 1.  The optimal parameters for MHSS, GSOR, SSOR, ASSOR and PSSOR
$ m $
Method $ 16 $ $ 32 $ $ 64 $ $ 128 $ $ 256 $ $ 512 $
Example 1 PMHSS $ \alpha_{opt} $ 1.09 1.36 1.35 1.05 1.05 1.05
GSOR $ \alpha_{opt} $ 0.551 0.495 0.457 0.432 0.418 0.412
SSOR $ \omega_{opt} $ 0.33 0.29 0.26 0.24 0.24 0.23
ASSOR $ \omega_{opt} $ 0.80 0.77 0.75 0.74 0.72 0.72
PSSOR $ \alpha_{opt} $ 0.47 0.48 0.54 0.54 0.55 0.55
$ \omega_{opt} $ 0.83 0.83 0.82 0.82 0.82 0.82
Example 2 PMHSS $ \alpha _{opt} $ 1.43 1.53 1.38 1.26 1.24 1.24
GSOR $ \alpha_{opt} $ 0.189 0.190 0.190 0.190 0.190 0.190
SSOR $ \omega_{opt} $ 0.09 0.09 0.10 0.10 0.10 0.10
ASSOR $ \omega_{opt} $ 0.64 0.64 0.64 0.64 0.64 0.64
PSSOR $ \alpha_{opt} $ 0.08 0.09 0.09 0.09 0.09 0.09
$ \omega_{opt} $ 0.89 0.89 0.89 0.89 0.89 0.89
Example 3 PMHSS $ \alpha_{opt} $ 0.61 0.42 0.57 0.78 0.73 0.73
GSOR $ \alpha_{opt} $ 0.908 0.776 0.566 0.354 0.199 0.105
SSOR $ \omega_{opt} $ 0.69 0.52 0.34 0.19 0.10 0.05
ASSOR $ \omega_{opt} $ 0.62 0.62 0.62 0.61 0.61 0.61
PSSOR $ \alpha_{opt} $ 1.93 1.50 1.31 1.02 0.90 0.90
$ \omega_{opt} $ 0.82 0.74 0.68 0.62 0.61 0.61
$ m $
Method $ 16 $ $ 32 $ $ 64 $ $ 128 $ $ 256 $ $ 512 $
Example 1 PMHSS $ \alpha_{opt} $ 1.09 1.36 1.35 1.05 1.05 1.05
GSOR $ \alpha_{opt} $ 0.551 0.495 0.457 0.432 0.418 0.412
SSOR $ \omega_{opt} $ 0.33 0.29 0.26 0.24 0.24 0.23
ASSOR $ \omega_{opt} $ 0.80 0.77 0.75 0.74 0.72 0.72
PSSOR $ \alpha_{opt} $ 0.47 0.48 0.54 0.54 0.55 0.55
$ \omega_{opt} $ 0.83 0.83 0.82 0.82 0.82 0.82
Example 2 PMHSS $ \alpha _{opt} $ 1.43 1.53 1.38 1.26 1.24 1.24
GSOR $ \alpha_{opt} $ 0.189 0.190 0.190 0.190 0.190 0.190
SSOR $ \omega_{opt} $ 0.09 0.09 0.10 0.10 0.10 0.10
ASSOR $ \omega_{opt} $ 0.64 0.64 0.64 0.64 0.64 0.64
PSSOR $ \alpha_{opt} $ 0.08 0.09 0.09 0.09 0.09 0.09
$ \omega_{opt} $ 0.89 0.89 0.89 0.89 0.89 0.89
Example 3 PMHSS $ \alpha_{opt} $ 0.61 0.42 0.57 0.78 0.73 0.73
GSOR $ \alpha_{opt} $ 0.908 0.776 0.566 0.354 0.199 0.105
SSOR $ \omega_{opt} $ 0.69 0.52 0.34 0.19 0.10 0.05
ASSOR $ \omega_{opt} $ 0.62 0.62 0.62 0.61 0.61 0.61
PSSOR $ \alpha_{opt} $ 1.93 1.50 1.31 1.02 0.90 0.90
$ \omega_{opt} $ 0.82 0.74 0.68 0.62 0.61 0.61
Table 2.  Numerical results for Example 1
Method $ m=16 $ $ m=32 $ $ m=64 $ $ m=128 $ $ m=256 $ $ m=512 $
PMHSS IT 21 21 21 21 21 20
CPU 0.02 0.03 0.08 0.36 1.94 1.48
GSOR IT 20 22 24 26 27 27
CPU 0.02 0.02 0.06 0.39 2.05 11.27
SSOR IT 19 21 23 26 26 27
CPU 0.02 0.03 0.09 0.55 3.02 16.89
ASSOR IT 5 5 6 6 6 6
CPU 0.01 0.02 0.09 0.16 0.91 4.82
PSSOR IT 4 4 4 4 4 4
CPU 0.01 0.02 0.03 0.13 0.63 3.31
Method $ m=16 $ $ m=32 $ $ m=64 $ $ m=128 $ $ m=256 $ $ m=512 $
PMHSS IT 21 21 21 21 21 20
CPU 0.02 0.03 0.08 0.36 1.94 1.48
GSOR IT 20 22 24 26 27 27
CPU 0.02 0.02 0.06 0.39 2.05 11.27
SSOR IT 19 21 23 26 26 27
CPU 0.02 0.03 0.09 0.55 3.02 16.89
ASSOR IT 5 5 6 6 6 6
CPU 0.01 0.02 0.09 0.16 0.91 4.82
PSSOR IT 4 4 4 4 4 4
CPU 0.01 0.02 0.03 0.13 0.63 3.31
Table 3.  Numerical results for Example 2
Method $ m=16 $ $ m=32 $ $ m=64 $ $ m=128 $ $ m=256 $ $ m=512 $
PMHSS IT 34 37 38 38 38 38
CPU 0.02 0.04 0.09 0.60 3.21 26.73
GSOR IT 80 76 72 69 68 68
CPU 0.03 0.04 0.16 1.04 4.85 27.01
SSOR IT 74 74 66 66 66 66
CPU 0.03 0.06 0.19 1.33 7.61 41.39
ASSOR IT 7 7 7 7 7 7
CPU 0.01 0.01 0.03 0.18 0.96 5.09
PSSOR IT 3 3 3 3 3 3
CPU 0.02 0.02 0.03 0.11 0.51 2.64
Method $ m=16 $ $ m=32 $ $ m=64 $ $ m=128 $ $ m=256 $ $ m=512 $
PMHSS IT 34 37 38 38 38 38
CPU 0.02 0.04 0.09 0.60 3.21 26.73
GSOR IT 80 76 72 69 68 68
CPU 0.03 0.04 0.16 1.04 4.85 27.01
SSOR IT 74 74 66 66 66 66
CPU 0.03 0.06 0.19 1.33 7.61 41.39
ASSOR IT 7 7 7 7 7 7
CPU 0.01 0.01 0.03 0.18 0.96 5.09
PSSOR IT 3 3 3 3 3 3
CPU 0.02 0.02 0.03 0.11 0.51 2.64
Table 4.  Numerical results for Example 3
Method $ m=16 $ $ m=32 $ $ m=64 $ $ m=128 $ $ m=256 $ $ m=512 $
PMHSS IT 30 30 30 30 30 32
CPU 0.02 0.04 0.16 1.09 6.33 34.32
GSOR IT 7 11 20 44 71 131
CPU 0.02 0.02 0.08 0.97 8.19 90.83
SSOR IT 6 10 17 33 66 135
CPU 0.02 0.02 0.10 1.12 11.86 140.55
ASSOR IT 8 8 8 8 8 8
CPU 0.01 0.01 0.05 0.30 1.62 9.34
PSSOR IT 4 5 6 7 7 7
CPU 0.02 0.02 0.05 0.27 1.48 8.46
Method $ m=16 $ $ m=32 $ $ m=64 $ $ m=128 $ $ m=256 $ $ m=512 $
PMHSS IT 30 30 30 30 30 32
CPU 0.02 0.04 0.16 1.09 6.33 34.32
GSOR IT 7 11 20 44 71 131
CPU 0.02 0.02 0.08 0.97 8.19 90.83
SSOR IT 6 10 17 33 66 135
CPU 0.02 0.02 0.10 1.12 11.86 140.55
ASSOR IT 8 8 8 8 8 8
CPU 0.01 0.01 0.05 0.30 1.62 9.34
PSSOR IT 4 5 6 7 7 7
CPU 0.02 0.02 0.05 0.27 1.48 8.46
[1]

Erchuan Zhang, Lyle Noakes. Riemannian cubics and elastica in the manifold $ \operatorname{SPD}(n) $ of all $ n\times n $ symmetric positive-definite matrices. Journal of Geometric Mechanics, 2019, 11 (2) : 277-299. doi: 10.3934/jgm.2019015

[2]

Yi Xu, Jinjie Liu, Liqun Qi. A new class of positive semi-definite tensors. Journal of Industrial and Management Optimization, 2020, 16 (2) : 933-943. doi: 10.3934/jimo.2018186

[3]

Yang Cao, Wei- Wei Tan, Mei-Qun Jiang. A generalization of the positive-definite and skew-Hermitian splitting iteration. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 811-821. doi: 10.3934/naco.2012.2.811

[4]

Ai-Li Yang, Yu-Jiang Wu. Newton-MHSS methods for solving systems of nonlinear equations with complex symmetric Jacobian matrices. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 839-853. doi: 10.3934/naco.2012.2.839

[5]

Dengfeng Lü, Shuangjie Peng. On the positive vector solutions for nonlinear fractional Laplacian systems with linear coupling. Discrete and Continuous Dynamical Systems, 2017, 37 (6) : 3327-3352. doi: 10.3934/dcds.2017141

[6]

Jaume Llibre, Y. Paulina Martínez, Claudio Vidal. Linear type centers of polynomial Hamiltonian systems with nonlinearities of degree 4 symmetric with respect to the y-axis. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 887-912. doi: 10.3934/dcdsb.2018047

[7]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61

[8]

Sihem Guerarra. Positive and negative definite submatrices in an Hermitian least rank solution of the matrix equation AXA*=B. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 15-22. doi: 10.3934/naco.2019002

[9]

Kun-Peng Jin, Jin Liang, Ti-Jun Xiao. Uniform polynomial stability of second order integro-differential equations in Hilbert spaces with positive definite kernels. Discrete and Continuous Dynamical Systems - S, 2021, 14 (9) : 3141-3166. doi: 10.3934/dcdss.2021077

[10]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[11]

El Houcein El Abdalaoui, Sylvain Bonnot, Ali Messaoudi, Olivier Sester. On the Fibonacci complex dynamical systems. Discrete and Continuous Dynamical Systems, 2016, 36 (5) : 2449-2471. doi: 10.3934/dcds.2016.36.2449

[12]

Nguyen H. Sau, Vu N. Phat. LP approach to exponential stabilization of singular linear positive time-delay systems via memory state feedback. Journal of Industrial and Management Optimization, 2018, 14 (2) : 583-596. doi: 10.3934/jimo.2017061

[13]

Giuseppe Geymonat, Françoise Krasucki. Hodge decomposition for symmetric matrix fields and the elasticity complex in Lipschitz domains. Communications on Pure and Applied Analysis, 2009, 8 (1) : 295-309. doi: 10.3934/cpaa.2009.8.295

[14]

Juan Gabriel Brida, Viktoriya Semeshenko. Special Issue on: Complex systems in economics. Journal of Dynamics and Games, 2020, 7 (3) : i-ii. doi: 10.3934/jdg.2020011

[15]

Haibin Chen, Liqun Qi. Positive definiteness and semi-definiteness of even order symmetric Cauchy tensors. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1263-1274. doi: 10.3934/jimo.2015.11.1263

[16]

Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete and Continuous Dynamical Systems, 2021, 41 (7) : 3295-3317. doi: 10.3934/dcds.2020406

[17]

Antonio Ambrosetti, Massimiliano Berti. Homoclinics and complex dynamics in slowly oscillating systems. Discrete and Continuous Dynamical Systems, 1998, 4 (3) : 393-403. doi: 10.3934/dcds.1998.4.393

[18]

Renato Manfrin. On the global solvability of symmetric hyperbolic systems of Kirchhoff type. Discrete and Continuous Dynamical Systems, 1997, 3 (1) : 91-106. doi: 10.3934/dcds.1997.3.91

[19]

Alexandra Skripchenko. Symmetric interval identification systems of order three. Discrete and Continuous Dynamical Systems, 2012, 32 (2) : 643-656. doi: 10.3934/dcds.2012.32.643

[20]

Jefferson L. R. Bastos, Claudio A. Buzzi, Joan Torregrosa. Orbitally symmetric systems with applications to planar centers. Communications on Pure and Applied Analysis, 2021, 20 (10) : 3319-3346. doi: 10.3934/cpaa.2021107

 Impact Factor: 

Metrics

  • PDF downloads (317)
  • HTML views (609)
  • Cited by (0)

[Back to Top]