| Citation: |
Litao Zhang, Yongwei Zhou, Xianyu Zuo, Chaoqian Li, Yaotang Li. A NOTE ON BLOCK PRECONDITIONER FOR GENERALIZED SADDLE POINT MATRICES WITH HIGHLY SINGULAR (1, 1) BLOCK[J]. Journal of Applied Analysis & Computation, 2019, 9(3): 916-927. doi: 10.11948/2156-907X.20180168
|
A NOTE ON BLOCK PRECONDITIONER FOR GENERALIZED SADDLE POINT MATRICES WITH HIGHLY SINGULAR (1, 1) BLOCK
-
Abstract
In this paper, we present a block triangular preconditioner for generalized saddle point matrices whose coefficient matrices have singular (1, 1) blocks. Theoretical analysis shows that all the eigenvalues of the preconditioned matrix are strongly clustered when choosing an optimal parameter. Numerical experiments are given to demonstrate the efficiency of the presented preconditioner. -
-
References
[1] E. Aulisa, S. Calandrini and G. Capodaglio, FOV-equivalent block triangular preconditioners for generalized saddle-point problems, Appl. Math. Lett., 2018, 75, 43-49. doi: 10.1016/j.aml.2017.06.018 [2] M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 2005, 14, 1-137. doi: 10.1017/S0962492904000212 [3] M. Benzi and J. Liu, Block preconditioning for saddle point systems with indefinite (1, 1) block, Int. J. Comput. Math., 2007, 5, 1-16. [4] M. Benzi and G. H. Golub, A preconditioner for generalized saddle point problems, IAM J. Matrix Anal. Appl., 2004, 26, 20-41. doi: 10.1137/S0895479802417106 [5] M. Benzi and A. J. Wathen, Some Preconditioning Techniques for Saddle Point Problems, Math. Ind., 2008, 13, 195-211. doi: 10.1007/978-3-540-78841-6 [6] F. Beik, M. Benzi and S. Chaparpordi, On block diagonal and block triangular iterative schemes and preconditioners for stabilized saddle point problems, J. Comput. Appl. Math., 2017, 326, 15-30. doi: 10.1016/j.cam.2017.05.009 [7] Z. H. Cao, A note on spectrum analysis of augmentation block preconditioned generalized saddle point matrices, J. Comput. Appl. Math., 2013, 238(15), 109-115. [8] Z. H. Cao, Augmentation block preconditioners for saddle point-type matrices with singular (1, 1) blocks, Numer. Linear Algebra Appl., 2008, 15, 515-533. doi: 10.1002/nla.v15:6 [9] S. Chaparpordi, F. Beik and D. Salkuyeh, Block triangular preconditioners for stabilized saddle point problems with nonsymmetric (1, 1)-block, Comput. Math. Appl., 2018, 76(6), 1544-1553. doi: 10.1016/j.camwa.2018.07.006 [10] L. B. Cui, C. Chen, W. Li and M. K. Ng, An eigenvalue problem for even order tensors with its applications, Linear Multilinear Algebra, 2016, 64, 602-621. doi: 10.1080/03081087.2015.1071311 [11] L. B. Cui, W. Li and M. K. Ng, Primitive Tensors and Directed Hypergraphs, Linear Algebra Appl., 2015, 471, 96-108. doi: 10.1016/j.laa.2014.12.033 [12] L. B. Cui, C. X. Li and S. L. Wu, The relaxation convergence of multisplitting AOR method for linear complementarity problem, Linear Multilinear Algebra. DOI: 10.1080/03081087.2018.1511680. [13] L. B. Cui and Y. S. Song, On the uniqueness of the positive Z-eigenvector for nonnegative tensors, J. Comput. Appl. Math., 2019, 352, 72-78. doi: 10.1016/j.cam.2018.11.032 [14] C. Greif and D. Schötzau, Preconditioners for the discretized time-harmonic Maxwell equations in mixed form, Numer. Linear Algebra Appl., 2007, 14, 281-297. doi: 10.1002/(ISSN)1099-1506 [15] C. Greif and D. Schötzau, Preconditioners for saddle point linear systems with highly singular (1, 1) blocks, Electron. Trans. Numer. Anal., 2006, 22, 114-121. [16] E. Haber, U. M. Ascher and D. Oldenberg, On the optimization techniques for solving nonlinear inverse problems, Inverse Problems, 2000, 16, 1263-1280. doi: 10.1088/0266-5611/16/5/309 [17] A. Hadjidimos, On equivalence of optimal relaxed block iterative methods for the singular nonsymmetric saddle point problem, Linear Algebra Appl., 2017, 522, 175-202. doi: 10.1016/j.laa.2017.01.035 [18] T. Z. Huang, G. H. Cheng and L. Li, New Block Triangular Preconditioners for Saddle Point Linear Systems with Highly Singular (1, 1) Blocks, Math. Probl. Eng, 2009, Hindawi Publishing Corporation. [19] D. D. Jiang, W. J. Wang, L. Shi and H. B. Song, A compressive sensing-based approach to end-to-end network traffic reconstruction, IEEE T. Autom. Sci. Eng., 2018, online available. DOI: 10.1109/TNSE.2018.2877597 [20] D. D. Jiang, L. W. Huo and H. B. Song, Rethinking behaviors and activities of base stations in mobile cellular networks based on big data analysis, IEEE T. Autom. Sci. Eng., 2018, 1(1), 1-12. [21] D. D. Jiang, L. W. Huo and Y. Li, Fine-granularity inference and estimations to network traffic for SDN, Plos One, 2018, 13(5), 1-23. [22] D. D. Jiang, L. W. Huo, Z. H. Lv, et al., A joint multi-criteria utility-based network selection approach for vehicle-to-infrastructure networking, IEEE T. Autom. Sci. Eng., 2018, 99, 1-15. [23] D. D. Jiang, P. Zhang, Z. H. Lv, et al., Energy-efficient multi-constraint routing algorithm with load balancing for smart city applications, IEEE Internet Things, 2016, 3(6), 1437-1447. doi: 10.1109/JIOT.2016.2613111 [24] P. Lancaster and M. Tismenetsky, The Theory of Matrices, seconded. with applications, Academic Press, London, 1985. [25] D. Li, C. Greif and D. Schötzau, Parallel numerical solution of the time-harmonicMaxwell equations inmixed form, Numer. Linear Algebra Appl., 2012, 19, 525-539. doi: 10.1002/nla.v19.3 [26] T. Rees and C. Greif, A preconditioner for linear systems arising from interior optimization methods, SIAM J. Sci. Comput., 2007, 29, 1992-2007. doi: 10.1137/060661673 [27] D. Salkuyeh and M. Rahimian, A modification of the generalized shift-splitting method for singular saddle point problems, Comput. Math. Appl., 2017, 74(12), 2940-2949. doi: 10.1016/j.camwa.2017.07.029 [28] C. Siefert and E. D. Sturler, Preconditioners for Generalized Saddle-Point Problems, SIAM J. Numer. Anal., 2006, 44(3), 1275-1296. doi: 10.1137/040610908 [29] H. A. Van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, Cambridge, UK, 2003. [30] L. T. Zhang, A new preconditioner for generalized saddle matrices with highly singular (1, 1) blocks, Int. J. Comput. Math., 2014, 91(9), 2091-2101. doi: 10.1080/00207160.2013.867953 -
-
Figures(7) / Tables(4)
Export File
Citation
Litao Zhang, Yongwei Zhou, Xianyu Zuo, Chaoqian Li, Yaotang Li. A NOTE ON BLOCK PRECONDITIONER FOR GENERALIZED SADDLE POINT MATRICES WITH HIGHLY SINGULAR (1, 1) BLOCK[J]. Journal of Applied Analysis & Computation, 2019, 9(3): 916-927. doi: 10.11948/2156-907X.20180168
Format
Content
DownLoad:
-
Figure 1. A uniform mesh with
$h=\frac{\sqrt{2}}{4}$ -
Figure 2. The eigenvalue distribution for the block triangular preconditioned matrix
$\mathcal {P}_{t}^{-1}\mathcal {A}$ when$t=-0.5$ (the first),$t=1.5$ (the second),$t=2.5$ (the third) and$t=-1$ (the fourth, the optimal parameters), respectively. Here,$h=\frac{\sqrt{2}}{8}$ . -
Figure 3. The eigenvalue distribution for the block triangular preconditioned matrix
$\mathcal {P}_{t}^{-1}\mathcal {A}$ when$t=-0.5$ (the first),$t=1.5$ (the second),$t=2.5$ (the third) and$t=-1$ (the fourth, the optimal parameters), respectively. Here,$h=\frac{\sqrt{2}}{12}$ . -
Figure 4. The eigenvalue distribution for the block triangular preconditioned matrix
$\mathcal {P}_{t}^{-1}\mathcal {A}$ when$t=-0.5$ (the first),$t=1.5$ (the second),$t=2.5$ (the third) and$t=-1$ (the fourth, the optimal parameters), respectively. Here,$h=\frac{\sqrt{2}}{18}.$ -
Figure 5. The eigenvalue distribution for the block triangular preconditioned matrix
$\mathcal {T}_{k, j}^{-1}\mathcal {A}$ when$k=2, j=-1$ (the first, the optimal parameters),$\mathcal {H}_{\xi, \eta}^{-1}\mathcal {A}$ when$\xi=1, \eta=-1$ (the second, the optimal parameters ($\xi\eta=-1$ )) and$\xi=-2, \eta=1/2$ (the third, the optimal parameters ($\xi\eta=-1$ )),$\mathcal {P}_{t}^{-1}\mathcal {A}$ when$t=-1$ (the fourth, the optimal parameters), respectively. Here,$h=\frac{\sqrt{2}}{8}.$ -
Figure 6. The eigenvalue distribution for the block triangular preconditioned matrix
$\mathcal {T}_{k, j}^{-1}\mathcal {A}$ when$k=2, j=-1$ (the first, the optimal parameters),$\mathcal {H}_{\xi, \eta}^{-1}\mathcal {A}$ when$\xi=1, \eta=-1$ (the second, the optimal parameters ($\xi\eta=-1$ )) and$\xi=-2, \eta=1/2$ (the third, the optimal parameters ($\xi\eta=-1$ )),$\mathcal {P}_{t}^{-1}\mathcal {A}$ when$t=-1$ (the fourth, the optimal parameters), respectively. Here,$h=\frac{\sqrt{2}}{12}.$ -
Figure 7. The eigenvalue distribution for the block triangular preconditioned matrix
$\mathcal {T}_{k, j}^{-1}\mathcal {A}$ when$k=2, j=-1$ (the first, the optimal parameters),$\mathcal {H}_{\xi, \eta}^{-1}\mathcal {A}$ when$\xi=1, \eta=-1$ (the second, the optimal parameters ($\xi\eta=-1$ )) and$\xi=-2, \eta=1/2$ (the third, the optimal parameters ($\xi\eta=-1$ )),$\mathcal {P}_{t}^{-1}\mathcal {A}$ when$t=-1$ (the fourth, the optimal parameters), respectively. Here,$h=\frac{\sqrt{2}}{18}.$