• 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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461

[2]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[3]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[4]

Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436

[5]

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

[6]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377

[7]

Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, , () : -. doi: 10.3934/era.2020117

[8]

Teresa D'Aprile. Bubbling solutions for the Liouville equation around a quantized singularity in symmetric domains. Communications on Pure & Applied Analysis, 2021, 20 (1) : 159-191. doi: 10.3934/cpaa.2020262

[9]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[10]

Susmita Sadhu. Complex oscillatory patterns near singular Hopf bifurcation in a two-timescale ecosystem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020342

[11]

Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302

[12]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[13]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266

[14]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[15]

Lingju Kong, Roger Nichols. On principal eigenvalues of biharmonic systems. Communications on Pure & Applied Analysis, 2021, 20 (1) : 1-15. doi: 10.3934/cpaa.2020254

[16]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[17]

Ilyasse Lamrani, Imad El Harraki, Ali Boutoulout, Fatima-Zahrae El Alaoui. Feedback stabilization of bilinear coupled hyperbolic systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020434

[18]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[19]

Simon Hochgerner. Symmetry actuated closed-loop Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 641-669. doi: 10.3934/jgm.2020030

[20]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029

 Impact Factor: 

Metrics

  • PDF downloads (171)
  • HTML views (495)
  • Cited by (0)

[Back to Top]