JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (10): 1-9.doi: 10.6040/j.issn.1671-9352.0.2023.225

    Next Articles

Block triangular splitting and its preconditioning iterative algorithms for a class of complex symmetric linear systems

Yang WANG()   

  1. College of Mathematics and Computer, Jilin Normal University, Siping 136100, Jilin, China
  • Received:2023-05-19 Online:2024-10-20 Published:2024-10-10

RichHTML

13

PDF (PC)

420

Abstract:

Based on block triangular splitting for block 2×2 matrix, the block triangular splitting(BTS) iteration method and the preconditioned block triangular splitting (PBTS) iteration method for a class of complex symmetric linear system are proposed. Theoretical analysis shows that the BTS and PBTS methods converge under certain conditions. The optimal iteration parameters of these two methods are obtained. Numerical experiments demonstrate the effectiveness and superiority of the BTS method and the PBTS iterative methods.

Key words: complex symmetric linear system, convergence analysis, block triangular splitting, preconditioning

CLC Number: 

  • O242.2

Fig.1

Comparison of spectral radii of iterative matrices for Example 1"

Fig.2

Comparison of spectral radii of iterative matrices for Example 2"

Fig.3

Comparison of spectral radii of iterative matrices for Example 3"

Table 1

Theoretical optimal parameter values of six iterative methods for Example 1"

算法 n×n 8×8 16×16 32×32 64×64
GSOR αopt 0.6168 0.5516 0.4967 0.4590
SBTS αopt 6.5880/0.5411 8.4153/0.5316 10.6630/0.5250 12.7600/0.5204
NSBTS αopt 3.5645 4.4735 5.5938 6.6402
PGSOR αopt 0.9944 0.9908 0.9877 0.9855
ω* 0.7017 0.6578 0.6239 0.6025
PSBTS αopt 1.1753/0.8702 1.2344/0.8404 1.1866/0.8641 1.2050/0.8544
ω* 0.7018 0.6577 0.6239 0.6025
PNSBTS αopt 1.0116 1.0187 1.0253 1.0298
ω* 0.7018 0.6577 0.6239 0.6025

Table 2

Theoretical optimal parameter values of six iterative methods for Example 2"

算法 n×n 8×8 16×16 32×32 64×64
GSOR αopt 0.9636 0.9083 0.7764 0.5661
SBTS αopt 1.3747/0.7858 1.7470/0.7005 2.8820/0.6050 6.8786/0.5319
NSBTS αopt 1.0803 1.2238 1.7435 3.7080
PGSOR αopt 0.9937 0.9820 0.9556 0.9183
ω* 4.5036 3.0020 1.9780 1.4366
PSBTS αopt 1.1278/0.8982 1.2339/0.8406 1.4284/0.7693 1.6760/0.7126
ω* 4.5036 3.0020 1.9783 1.4366
PNSBTS αopt 1.0256 1.0373 1.0988 1.1943
ω* 4.5036 3.0020 1.9783 1.4366

Table 3

Theoretical optimal parameter values of six iterative methods for Example 3"

算法 n×n 8×8 16×16 32×32 64×64
GSOR αopt 0.4507 0.4553 0.4567 0.4571
SBTS αopt 12.3030/0.5212 11.9860/0.5217 11.8980/0.5219 11.8749/0.5219
NSBTS αopt 6.412 6.2540 6.2101 6.1984
PGSOR αopt 0.9035 0.8978 0.8962 0.8957
ω* 1.2536 1.3081 1.3236 1.3278
PSBTS αopt 1.7784/0.6956 1.8194/0.6894 1.8309/0.6878 1.8339/0.6874
ω* 1.2536 1.3081 1.3236 1.3278
PNSBTS αopt 1.4727 1.5072 1.2594 1.2607
ω* 1.2536 1.3081 1.3236 1.3278

Table 4

Comparison of iteration steps (IT) and iteration time (CPU) for Example 1"

算法 n×n 8×8 16×16 32×32 64×64
GSOR IT/CPU 14/0.005 15/0.023 16/0.047 16/0.215
SBTS IT/CPU 13/0.004 17/0.020 20/0.112 20/0.508
NSBTS IT/CPU 13/0.007 17/0.020 20/0.054 20/0.267
PGSOR IT/CPU 3/0.001 3/0.005 3/0.008 3/0.040
PSBTS IT/CPU 3/0.003 3/0.008 3/0.020 3/0.056
PNSBTS IT/CPU 3/0.001 3/0.002 3/0.009 3/0.042

Table 5

Comparison of iteration steps (IT) and iteration time (CPU) for Example 2"

算法 n×n 8×8 16×16 32×32 64×64
GSOR IT/CPU 7/0.003 9/0.008 14/0.068 26/0.546
SBTS IT/CPU 7/0.004 11/0.016 22/0.238 60/2.652
NSBTS IT/CPU 7/0.003 11/0.009 22/0.100 60/1.310
PGSOR IT/CPU 5/0.003 6/0.006 8/0.044 9/0.168
PSBTS IT/CPU 6/0.004 6/0.014 8/0.075 10/0.427
PNSBTS IT/CPU 6/0.002 6/0.004 8/0.037 10/0.236

Table 6

Comparison of iteration steps (IT) and iteration time (CPU) for Example 3"

算法 n×n 8×8 16×16 32×32 64×64
GSOR IT/CPU 34/0.007 33/0.020 31/0.086 30/0.362
SBTS IT/CPU 95/0.035 92/0.127 93/0.476 96/2.281
NSBTS IT/CPU 96/0.026 93/0.056 93/0.254 95/1.141
PGSOR IT/CPU 9/0.002 9/0.012 9/0.035 9/0.114
PSBTS IT/CPU 10/0.006 10/0.027 11/0.065 11/0.267
PNSBTS IT/CPU 10/0.003 10/0.010 11/0.030 12/0.145
1 SOMMERFELD A . Partial differential equations[M]. New York: Academic Press, 1949: 1- 10.
2 ARRIDGE S R . Optical tomography in medical imaging[J]. Inverse Problems, 1999, 15 (2): 41- 93.
doi: 10.1088/0266-5611/15/2/022
3 HIPTMAIR R . Finite elements in computational electromagnetism[J]. Acta Numerica, 2002, 11, 237- 339.
doi: 10.1017/S0962492902000041
4 ARANSON I S , KRAMER L . The world of the complex Ginzburg-Landau equation[J]. Reviews of Modern Physics, 2002, 74 (1): 99- 143.
doi: 10.1103/RevModPhys.74.99
5 KURAMOTO Y . Chemical oscillations, waves, and turbulence[M]. New York: Dover Publications, Inc, 2003: 89- 140.
6 SAAD Y , SCHULTZ M H . GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems[J]. SIAM Journal on Scientific and Statistical Computing, 1986, 7 (3): 856- 869.
doi: 10.1137/0907058
7 FREUND R W , NACHTIGAL N M . QMR: a quasi-minimal residual method for non-Hermitian linear systems[J]. Numerische Mathematik, 1991, 60 (1): 315- 339.
doi: 10.1007/BF01385726
8 AXELSSON O , KHCHEROV A . Real valued iterative methods for solving complex symmetric linear systems[J]. Numerical Linear Algebra with Applications, 2000, 7 (4): 197- 218.
doi: 10.1002/1099-1506(200005)7:4<197::AID-NLA194>3.0.CO;2-S
9 AXELSSON O , NEYTCHEVA M , AHMAD B . A comparison of iterative methods to solve complex valued linear algebraic systems[J]. Numerical Algorithms, 2014, 66 (4): 811- 841.
doi: 10.1007/s11075-013-9764-1
10 AXELSSON O , BAI Z Z , QIU S X . A class of nested iteration schemes for linear systems with a coefficient matrix with a dominant positive definite symmetric part[J]. Numerical Algorithms, 2004, 35, 351- 372.
doi: 10.1023/B:NUMA.0000021766.70028.66
11 BAI Z Z , GOLUB G H , NG M K . Hermitian and skew-hermitian splitting methods for non-hermitian positive definite linear systems[J]. SIAM Journal on Matrix Analysis and Applications, 2003, 24 (3): 603- 626.
doi: 10.1137/S0895479801395458
12 BAI Z Z , BENZI M , CHEN F . Modified HSS iteration methods for a class of complex symmetric linear systems[J]. Computing, 2010, 87 (3/4): 93- 111.
13 BAI Z Z , BENZI M , CHEN F . On preconditioned MHSS iteration methods for complex symmetric linear systems[J]. Numerical Algorithms, 2011, 56, 297- 317.
doi: 10.1007/s11075-010-9441-6
14 BAI Z Z , BENZI M , CHEN F , et al. Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems[J]. IMA Journal of Numerical Analysis, 2013, 33 (1): 343- 369.
doi: 10.1093/imanum/drs001
15 SALKUYEH D K , HEZARI D , EDALATPOUR V . Generalized successive over-relaxation iterative method for a class of complex symmetric linear system of equations[J]. International Journal of Computer Mathematics, 2015, 92 (4): 802- 815.
doi: 10.1080/00207160.2014.912753
16 HEZARI D , EDALATPOUR V , SALKUYEH D K . Preconditioned GSOR iterative method for a class of complex symmetric linear system of linear equations[J]. Numerical Linear Algebra with Applications, 2015, 22 (4): 761- 776.
doi: 10.1002/nla.1987
17 LI Xian , WEI Hongzhang , WU Yujiang . On symmetric block triangular splitting iteration method for a class of complex symmetric system of linear equations[J]. Applied Mathematics Letters, 2018, 79, 131- 137.
doi: 10.1016/j.aml.2017.12.008
18 ZHANG Jianhua , WANG Zewen , ZHAO Jing . Preconditioned symmetric block triangular splitting iteration method for a class of complex symmetric system of linear equations[J]. Applied Mathematics Letters, 2018, 86, 95- 102.
doi: 10.1016/j.aml.2018.06.024
19 ZHENG Qingqing , MA Changfeng . A class of triangular splitting methods for saddle point problems[J]. Journal of Computational and Applied Mathematics, 2016, 298, 13- 23.
doi: 10.1016/j.cam.2015.11.026
20 LI Jingtao , MA Changfeng . The parameterized upper and lower triangular splitting methods for saddle point problems[J]. Numerical Algorithms, 2017, 76, 413- 425.
doi: 10.1007/s11075-017-0263-7
21 BAI Z Z . On preconditioned iteration methods for complex linear systems[J]. Journal of Engineering Mathematics, 2015, 93, 41- 60.
doi: 10.1007/s10665-013-9670-5
22 LIANG Zhaozheng , ZHANG Guofeng . On SSOR iteration method for a class of block two-by-two linear systems[J]. Numerical Algorithms, 2016, 71, 655- 671.
doi: 10.1007/s11075-015-0015-5
23 WU Yujiang , LI Xu , YUAN Jinyun . A non-alternating preconditioned HSS iteration method for non-Hermitian positive definite linear systems[J]. Computational and Applied Mathematics, 2017, 36 (1): 367- 381.
doi: 10.1007/s40314-015-0231-6
24 BENZI M , BERTACCINI D . Block preconditioning of real-valued iterative algorithms for complex linear systems[J]. IMA Journal of Numerical Analysis, 2008, 28 (3): 598- 618.
25 LI Xu , YANG Aili , WU Yujiang . Lopsided PMHSS iteration method for a class of complex symmetric linear systems[J]. Numerical Algorithms, 2014, 66 (3): 555- 568.
doi: 10.1007/s11075-013-9748-1
26 ZHENG Qingqing , LU Linzhang . A shift-splitting preconditioned for a class of block two-by-two linear systems[J]. Applied Math Letters, 2016, 66 (3): 54- 60.
27 王洋, 赵彦军, 冯毅夫. 基于超松弛迭代的MHSS加速方法[J]. 山东大学学报(理学版), 2016, 51 (8): 61- 65.
doi: 10.6040/j.issn.1671-9352.0.2015.402
WANG Yang , ZHAO Yanjun , FENG Yifu . On successive-overrelaxation acceleration of MHSS iteration[J]. Journal of Shandong University (Natural Science), 2016, 51 (8): 61- 65.
doi: 10.6040/j.issn.1671-9352.0.2015.402
[1] WANG Yang, ZHAO Yan-jun, FENG Yi-fu. On successive-overrelaxation acceleration of MHSS iterations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 61-65.
[2] CHEN Yi-ming, KE Xiao-hong, HAN Xiao-ning, SUN Yan-nan, LIU Li-qing. Wavelets method for solving system of fractional differential equations and the convergence analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 67-74.
[3] ZHANG Jian-song1, NIU Hai-feng2. A new streamline-diffusion mixed finite element method for compressible  miscible displacement problem in porous medium [J]. J4, 2011, 46(12): 6-12.
[4] . A high accuracy finite volume element method based on cubic spline interpolation for twopoint boundary value problems [J]. J4, 2009, 44(2): 45-51.
[5] GUO Hui,LIN Chao . A least-squares mixed finite element procedure with the method of
characteristics for convection-dominated Sobolev equations [J]. J4, 2008, 43(9): 45-50 .
[6] GUO Hui .

A least-squares mixed finite element procedure with the method of
characteristics for convection-dominated diffusion equations

[J]. J4, 2008, 43(8): 6-10 .
[7] ZHANG Jian-song,YANG Dan-ping* . Numerical analysis for the thermistor problem with mixed boundary conditions [J]. J4, 2007, 42(8): 1-08 .
[8] ZHANG Jian-song and YANG Dan-ping . A fully-discrete splitting positive definite mixed element scheme finite for compressible miscible displacement in porous media [J]. J4, 2006, 41(1): 1-10 .
[9] ZHANG Jian-song and YANG Dan-ping . A fullydiscrete splitting positive definite mixed element scheme finite for compressible miscible displacement in porous media [J]. J4, 2006, 41(1): 1-10 .
[10] CHENG Ai-jie and LU Ning . Galerkin method for controlledrelease and spread of solute in porous media [J]. J4, 2006, 41(1): 16-20 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZOU Guo-ping1, MA Ru-ning1, DING Jun-di2, ZHONG Bao-jiang3. Image retrieval based on saliency weighted color and texture[J]. J4, 2010, 45(7): 81 -85 .
[2] CHEN Li . The robust fault diagnosis filter design for uncertain singular systems[J]. J4, 2007, 42(7): 62 -65 .
[3] DING Chao1, 2, YUAN Chang-an1, 3, QIN Xiao1, 3. A prediction algorithm for multi-data streams  based on GEP[J]. J4, 2010, 45(7): 50 -54 .
[4] ZHANG De-yu,ZHAI Wen-guang . [J]. J4, 2006, 41(5): 4 -07 .
[5] ZENG Weng-fu1, HUANG Tian-qiang1,2, LI Kai1, YU YANG-qiang1, GUO Gong-de1,2. A local linear emedding agorithm based on harmonicmean geodesic kernel[J]. J4, 2010, 45(7): 55 -59 .
[6] YI Chao-qun, LI Jian-ping, ZHU Cheng-wen. A kind of feature selection based on classification accuracy of SVM[J]. J4, 2010, 45(7): 119 -121 .
[7] SUN Liang-ji,JI Guo-xing . Jordan(α,β)-derivations and generalized Jordan(α,β)-derivations on upper triangular matrix algebras[J]. J4, 2007, 42(10): 100 -105 .
[8] YANG Jianhui1, ZHANG Jianping, CHENG Xinlu, YANG Xiangdong. Magnetic dipole transitions among 1s22s2p 3P0, of Be-like ions[J]. J4, 2009, 44(11): 29 -34 .
[9] PANG Yong,MU Zong-zhao,WANG Yue-hai,BAO Yu-hai,SUN Lei . Transpiration characteristics and its influencing factors of sixteen polar clones[J]. J4, 2006, 41(6): 168 -172 .
[10] WU Da-qian,DU Ning,WANG Wei,ZHAI Wen,WANG Yu-feng,WANG Ren-qing and ZHANG Zhi-guo* . Quantitative analysis of structure and biodiversity of shrub layer and herbage layer under forest community at Kunyu Mountain[J]. J4, 2007, 42(1): 83 -88 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd