EFFICIENT ALGORITHMS FOR REAL SYMMETRIC TOEPLITZ LINEAR SYSTEM WITH LOW-RANK PERTURBATIONS AND ITS APPLICATIONS

Xing Zhang; Yanpeng Zheng; Zhaolin Jiang; Heejung Byun

doi:10.11948/20230073

2024 Volume 14 Issue 1

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2024 > 14(1): 106-118

Next Article Previous Article

Xing Zhang, Yanpeng Zheng, Zhaolin Jiang, Heejung Byun. EFFICIENT ALGORITHMS FOR REAL SYMMETRIC TOEPLITZ LINEAR SYSTEM WITH LOW-RANK PERTURBATIONS AND ITS APPLICATIONS[J]. Journal of Applied Analysis & Computation, 2024, 14(1): 106-118. doi: 10.11948/20230073

Citation:

Xing Zhang, Yanpeng Zheng, Zhaolin Jiang, Heejung Byun. EFFICIENT ALGORITHMS FOR REAL SYMMETRIC TOEPLITZ LINEAR SYSTEM WITH LOW-RANK PERTURBATIONS AND ITS APPLICATIONS[J]. Journal of Applied Analysis & Computation, 2024, 14(1): 106-118. doi: 10.11948/20230073

EFFICIENT ALGORITHMS FOR REAL SYMMETRIC TOEPLITZ LINEAR SYSTEM WITH LOW-RANK PERTURBATIONS AND ITS APPLICATIONS

1.
School of Information Science and Technology, Linyi University, Linyi 276000, China
2.
College of Information Technology, The University of Suwon, Hwaseong-si 445-743, Korea
3.
School of Automation and Electrical Engineering, Linyi University, Linyi 276000, China
4.
School of Mathematics and Statistics, Linyi University, Linyi 276000, China

Author Bio: Email: zhangxing_1013@163.com(X. Zhang); Email: hui.byun@gmail.com(H. Byun)
Corresponding authors: Email: zhengyanpeng0702@sina.com(Y. Zheng); Email: jzh1208@sina.com(Z. Jiang)
Fund Project: The authors were supported by National Natural Science Foundation of China (No. 12001257) and National Science Foundation of Shandong Province (No. ZR2020QA035)

Abstract

Abstract

This study investigates efficient algorithms for solving the real symmetric Toeplitz linear system with low-rank perturbations. Based on a new factorization of the real symmetric Toeplitz matrix inversion, we propose a novel and effective method to solve a sequence of linear equations with a same symmetric Toeplitz matrix. Together with the application of the Sherman-Morrison-Woodbury formula, the symmetric Toeplitz linear system with low-rank perturbations can be solved by two proposed algorithms. Moreover, the (structured) perturbation analysis and the applications in image encryption and decryption are given. The numerical results are presented to verify the theoretical analysis.
- Symmetric Toeplitz matrix /
- perturbations /
- order-reduction /
- encryption /
- decryption
MSC: 15A06, 15A09, 15B05, 65F05, 65T50

FullText(HTML)

References

[1]	Z. -Z. Bai, R. H. Chan and Z. -R. Ren, On order-reducible sinc discretizations and block-diagonal preconditioning methods for linear third-order ordinary differential equations, Numer. Linear Algebra Appl., 2014, 21, 108-135. doi: 10.1002/nla.1868 CrossRef Google Scholar
[2]	Z. -Z. Bai and K. -Y. Lu, Fast matrix splitting preconditioners for higher dimensional spatial fractional diffusion equations, J. Comput. Phys., 2020, 404, 1. Google Scholar
[3]	M. Batista and A. A. Karawia, The use of the Sherman-Morrison-Woodbury formula to solve cyclic block tri-diagonal and cyclic block penta-diagonal linear systems of equations, Appl. Math. Comput., 2009, 210, 558-563. Google Scholar
[4]	R. E. Blahut, Fast Algorithms for Signal Processing, Cambridge University Press, New York, 2010. Google Scholar
[5]	A. Chaves, J. G. Azadani and H. Alsalman, et al., Bandgap engineering of two-dimensional semiconductor materials, Npj 2D Mater. Appl., 2020, 4, 29. doi: 10.1038/s41699-020-00162-4 CrossRef Google Scholar
[6]	L. Du, T. Sogabe and S. -L. Zhang, A fast algorithm for solving tridiagonal quasi-Toeplitz linear systems, Appl. Math. Lett., 2018, 75, 74-81. doi: 10.1016/j.aml.2017.06.016 CrossRef Google Scholar
[7]	Y. -R. Fu, X. -Y. Jiang, Z. -L. Jiang and S. Jhang, Fast algorithms for finding the solution of CUPL-Toeplitz linear system from Markov chain, Appl. Math. Comput., 2021, 396, 125859. Google Scholar
[8]	I. Gohberg and V. Olshevsky, Circulants, displacements and decompositions of matrices, Integr. Equat. Oper. Th., 1992, 15, 730-743. doi: 10.1007/BF01200697 CrossRef Google Scholar
[9]	X. -M. Gu, T. -Z. Huang, X. -L. Zhao, H. -B. Li and L. Li, Fast iterative solvers for numerical simulations of scattering and radiation on thin wires, J. Electromagn. Waves Appl., 2015, 29(10), 1281-1296. doi: 10.1080/09205071.2015.1042559 CrossRef Google Scholar
[10]	X. -M. Gu, T. -Z. Huang, T. -Z. Zhao, H. -B. Li and L. Li, Strang-type preconditioners for solving fractional diffusion equations by boundary value methods, J. Comput. Appl. Math., 2015, 277, 73-86. doi: 10.1016/j.cam.2014.08.011 CrossRef Google Scholar
[11]	Y. -C. Huang and S. -L. Lei, A fast numerical method for block lower triangular Toeplitz with dense Toeplitz blocks system with applications to time-space fractional diffusion equations, Numer. Algor., 2017, 76(3), 605-616. doi: 10.1007/s11075-017-0272-6 CrossRef Google Scholar
[12]	J. -T. Jia and S. -M. Li, New algorithms for numerically solving a class of bordered tridiagonal systems of linear equations, Comput. Math. Appl., 2019, 78(1), 144-151. doi: 10.1016/j.camwa.2019.02.028 CrossRef Google Scholar
[13]	X. -Y. Jiang and K. Hong, Skew cyclic displacements and inversions of two innovative patterned matrices, Appl. Math. Comput., 2017, 308, 174-184. Google Scholar
[14]	Z. -L. Jiang, X. -T. Chen and J. -M. Wang, The explicit inverses of CUPL-Toeplitz and CUPL-Hankel matrices, East Asian J. Appl. Math., 2017, 7(1), 38-54. doi: 10.4208/eajam.070816.191016a CrossRef Google Scholar
[15]	Z. -L. Jiang and T. -T. Xu, Norm estimates of ω-circulant operator matrices and isomorphic operators for ω-circulant algebra, Sci. China Math., 2016, 59, 351-366. doi: 10.1007/s11425-015-5051-z CrossRef Google Scholar
[16]	Z. -L. Jiang and Z. -X. Zhou, Circulant Matrices, Chengdu Technology University, Chengdu, China, 1999. Google Scholar
[17]	S. -L. Lei and Y. -C. Huang, Fast algorithms for high-order numerical methods for space fractional diffusion equations, Int. J. Comput. Math., 2016, 94(5), 1062-1078. Google Scholar
[18]	M. Li, X. -M. Gu, C. -M. Huang, M. -F. Fei and G. -Y. Zhang, A fast linearized conservative finite element method for the strongly coupled nonlinear fractional Schrödinger equations, J. Comput. Phys., 2018, 358, 256-282. doi: 10.1016/j.jcp.2017.12.044 CrossRef Google Scholar
[19]	Y. -H. Li, X. Han and Y. Cao, et al., Quantum random number generation with uncharacterized laser and sunlight, Npj Quantum Inform., 2019, 5, 97. doi: 10.1038/s41534-019-0208-1 CrossRef Google Scholar
[20]	Z. -Y. Liu, S. -H. Chen, W. -J. Xu and Y. -L. Zhang, The eigen-structures of real (skew) circulant matrices with some applications, Comput. Appl. Math., 2019, 38, 178. doi: 10.1007/s40314-019-0971-9 CrossRef Google Scholar
[21]	Z. -Y. Liu, S. Li, Y. Yin and Y. -L. Zhang, Fast solvers for tridiagonal Toeplitz linear systems, Comput. Appl. Math., 2020, 39, 315. doi: 10.1007/s40314-020-01369-3 CrossRef Google Scholar
[22]	Z. -Y. Liu, X. -R. Qin, N. -C. Wu and Y. -L. Zhang, The shifted classical circulant and skew circulant splitting iterative methods for Toeplitz matrices, Canad. Math. Bull., 2017, 60(4), 807-815. doi: 10.4153/CMB-2016-077-5 CrossRef Google Scholar
[23]	Z. -Y. Liu, N. -C. Wu, X. -R. Qin and Y. -L. Zhang, Trigonometric transform splitting methods for real symmetric Toeplitz systems, Comput. Math. Appl., 2018, 75, 2782-2794. doi: 10.1016/j.camwa.2018.01.008 CrossRef Google Scholar
[24]	W. -H. Luo, X. -M. Gu, Y. Liu and M. Jing, A Lagrange-quadratic spline optimal collocation method for the time tempered fractional diffusion equation, Math. Comput. Simulat., 2021, 182, 1-24. doi: 10.1016/j.matcom.2020.10.016 CrossRef Google Scholar
[25]	A. S. Nicholas, Z. -H. Peter, C. Matteo and D. H. Kenneth, Distributed coding of choice, action and engagement across the mouse brain, Nature, 2019, 576, 266-273. doi: 10.1038/s41586-019-1787-x CrossRef Google Scholar
[26]	J. Pan, R. Ke, M. K. Ng and H. -W. Sun, Preconditioning techniques for diagonal-times-Toeplitz matrices in fractional diffusion equations, SIAM J. Sci. Comput., 2014, 36(6), A2698-A2719. doi: 10.1137/130931795 CrossRef Google Scholar
[27]	Y. Saad, Iterative Methods for Sparse Linear Systems, second ed., SIAM, Philadelphia, 2003. Google Scholar
[28]	A. T. Winder, C. Echagarruga, Q. -G. Zhang and P. J. Drew, Weak correlations between hemodynamic signals and ongoing neural activity during the resting state, Nat. Neurosci., 2017, 20, 1761-1769. doi: 10.1038/s41593-017-0007-y CrossRef Google Scholar
[29]	J. Wu, X. -M. Gu, Y. -L. Zhao, Y. -Y. Huang and B. Carpentieri, A note on the structured perturbation analysis for the inversion formula of Toeplitz matrices, Japan J. Indust. Appl. Math., 2023, 40(1), 645-663. doi: 10.1007/s13160-022-00543-w CrossRef Google Scholar
[30]	P. -P. Xie and Y. -M. Wei, The stability of formulae of the Gohberg-Semencul-Trench type for Moore-Penrose and group inverses of Toeplitz matrices, Linear Algebra Appl., 2016, 498, 117-135. doi: 10.1016/j.laa.2015.01.029 CrossRef Google Scholar
[31]	S. Yoon, H. Lee, J. H. Hong, Y. -S. Lim and W. Choi, Laser scanning reflection-matrix microscopy for aberration-free imaging through intact mouse skull, Nat. Commun., 2020, 11, 5721. doi: 10.1038/s41467-020-19550-x CrossRef Google Scholar
[32]	Q. -G. Zhang, M. Roche and K. W. Gheres, et al., Cerebral oxygenation during locomotion is modulated by respiration, Nat. Commun., 2019, 10, 1-15. doi: 10.1038/s41467-018-07882-8 CrossRef Google Scholar
[33]	X. Zhang, X. -Y. Jiang, Z. -L. Jiang and H. Byun, An improvement of methods for solving the CUPL-Toeplitz linear system, Appl. Math. Comput., 2022, 421, 126932. Google Scholar
[34]	X. Zhang, Y. -P. Zheng, Z. -L. Jiang and H. Byun, Numerical algorithms for corner-modified symmetric Toeplitz linear system with applications to image encryption and decryption, J. Appl. Math. Comput., 2022, 69, 1967-1987. Google Scholar
[35]	Y. -L. Zhao and X. -M. Gu, A. Ostermann, A preconditioning technique for an all-at-once system from Volterra subdiffusion equations with graded time steps, J. Sci. Comput., 2021, 88(1), 11. doi: 10.1007/s10915-021-01527-7 CrossRef Google Scholar
[36]	Y. -P. Zheng, S. Shon and J. Kim, Cyclic displacements and decompositions of inverse matrices for CUPL Toeplitz matrices, J. Math. Anal. Appl., 2017, 455, 727-741. doi: 10.1016/j.jmaa.2017.06.016 CrossRef Google Scholar