Algorithms for solving a class of real quasi-symmetric Toeplitz linear systems and its applications

Xing Zhang; Xiaoyu Jiang; Zhaolin Jiang; Heejung Byun; Xing Zhang; Xiaoyu Jiang; Zhaolin Jiang; Heejung Byun

doi:10.3934/era.2023101

Electronic Research Archive

2023, Volume 31, Issue 4: 1966-1981. doi: 10.3934/era.2023101

Previous Article Next Article

Research article

Algorithms for solving a class of real quasi-symmetric Toeplitz linear systems 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, Republic of Korea
3.
School of Mathematics and Statistics, Linyi University, Linyi 276000, China

Received: 19 November 2022 Revised: 29 January 2023 Accepted: 29 January 2023 Published: 13 February 2023

In this paper, fast numerical methods for solving the real quasi-symmetric Toeplitz linear system are studied in two stages. First, based on an order-reduction algorithm and the factorization of Toeplitz matrix inversion, a sequence of linear systems with a constant symmetric Toeplitz matrix are solved. Second, two new fast algorithms are employed to solve the real quasi-symmetric Toeplitz linear system. Furthermore, we show a fast algorithm for quasi-symmetric Toeplitz matrix-vector multiplication. In addition, the stability analysis of the splitting symmetric Toeplitz inversion is discussed. In mathematical or engineering problems, the proposed algorithms are extraordinarily effective for solving a sequence of linear systems with a constant symmetric Toeplitz matrix. Fast matrix-vector multiplication and a quasi-symmetric Toeplitz linear solver are proven to be suitable for image encryption and decryption.
- image,
- encryption,
- decryption,
- decomposition,
- matrix inversion,
- quasi-symmetric Toeplitz matrix
Citation: Xing Zhang, Xiaoyu Jiang, Zhaolin Jiang, Heejung Byun. Algorithms for solving a class of real quasi-symmetric Toeplitz linear systems and its applications[J]. Electronic Research Archive, 2023, 31(4): 1966-1981. doi: 10.3934/era.2023101

Related Papers:

Abstract

In this paper, fast numerical methods for solving the real quasi-symmetric Toeplitz linear system are studied in two stages. First, based on an order-reduction algorithm and the factorization of Toeplitz matrix inversion, a sequence of linear systems with a constant symmetric Toeplitz matrix are solved. Second, two new fast algorithms are employed to solve the real quasi-symmetric Toeplitz linear system. Furthermore, we show a fast algorithm for quasi-symmetric Toeplitz matrix-vector multiplication. In addition, the stability analysis of the splitting symmetric Toeplitz inversion is discussed. In mathematical or engineering problems, the proposed algorithms are extraordinarily effective for solving a sequence of linear systems with a constant symmetric Toeplitz matrix. Fast matrix-vector multiplication and a quasi-symmetric Toeplitz linear solver are proven to be suitable for image encryption and decryption.

References

[1]	M. M. Rams, M. Zwolak, B. Damski, A quantum phase transition in a quantum external field: superposing two magnetic phases, Sci. Rep., 2 (2012), 655. https://doi.org/10.1038/srep00655 doi: 10.1038/srep00655
[2]	P. A. Papakonstantinou, D. P. Woodruff, G. Yang, True randomness from big data, Sci. Rep., 6 (2016), 33740. https://doi.org/10.1038/srep33740 doi: 10.1038/srep33740
[3]	B. Y. Tang, B. Liu, Y. P. Zhai, C. Q. Wu, W. R. Yu, High-speed and large-scale privacy amplifcation scheme for quantum key distribution, Sci. Rep., 9 (2019), 15733. https://doi.org/10.1038/s41598-019-50290-1 doi: 10.1038/s41598-019-50290-1
[4]	X. B. Wang, J. T. Wang, J. Q. Qin, C. Jiang, Z. W. Yu, Guessing probability in quantum key distribution, npj Quantum Inf., 6 (2020), 45. https://doi.org/10.1038/s41534-020-0267-3 doi: 10.1038/s41534-020-0267-3
[5]	Y. A. Chen, Q. Zhang, T. Y. Chen, W. Q. Cai, S. K. Liao, J. Zhang, et al., An integrated space-to-ground quantum communication network over 4600 kilometres, Nature, 589 (2021), 214–219. https://doi.org/10.1038/s41586-020-03093-8 doi: 10.1038/s41586-020-03093-8
[6]	S. Nordebo, M. F. Naeem, P. Tans, Estimating the short-time rate of change in the trend of the keeling curve, Sci. Rep., 10 (2020), 21222. https://doi.org/10.1038/s41598-020-77921-2 doi: 10.1038/s41598-020-77921-2
[7]	A. Machado, Z. Cai, T. Vincent, G. Pellegrino, J. M. Lina, E. Kobayashi, et al., Deconvolution of hemodynamic responses along the cortical surface using personalized functional near infrared spectroscopy, Sci. Rep., 11 (2021), 5964. https://doi.org/10.1038/s41598-021-85386-0 doi: 10.1038/s41598-021-85386-0
[8]	X. M. Gu, T. Z. Huang, X. L. Zhao, H. B. Li, L. Li, Fast iterative solvers for numerical simulations of scattering and radiation on thin wires, J. Electromagn. Waves Appl., 29 (2015), 1281–1296. https://doi.org/10.1080/09205071.2015.1042559 doi: 10.1080/09205071.2015.1042559
[9]	Z. Z. Bai, Y. M. Huang, M. K. Ng, On preconditioned iterative methods for certain time-dependent partial differential equations, SIAM J. Numer. Anal., 47 (2009), 1019–1037. https://doi.org/10.1137/080718176 doi: 10.1137/080718176
[10]	Z. Z. Bai, R. H. Chan, Z. R. Ren, On sinc discretization and banded preconditioning for linear third-order ordinary differential equations, Numer. Linear Algebra Appl., 18 (2011), 471–497. https://doi.org/10.1002/nla.738 doi: 10.1002/nla.738
[11]	X. M. Gu, Y. L. Zhao, X. L. Zhao, B. Carpentieri, Y. Y. Huang, A note on parallel preconditioning for the all-at-once solution of Riesz fractional diffusion equations, Numer. Math. Theory Methods Appl., 14 (2021), 893–919. https://doi.org/10.48550/arXiv.2003.07020 doi: 10.48550/arXiv.2003.07020
[12]	Y. L. Zhao, 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., 88 (2021), 11. https://doi.org/10.1007/s10915-021-01527-7 doi: 10.1007/s10915-021-01527-7
[13]	Z. Z. Bai, K. Y. Lu, Optimal rotated block-diagonal preconditioning for discretized optimal control problems constrained with fractional time-dependent diffusive equations, Appl. Numer. Math., 163 (2021), 126–146. https://doi.org/10.1016/j.apnum.2021.01.011 doi: 10.1016/j.apnum.2021.01.011
[14]	Z. Z. Bai, K. Y. Lu, Fast matrix splitting preconditioners for higher dimensional spatial fractional diffusion equations, J. Comput. Phys., 404 (2020), 1. https://doi.org/10.1016/j.jcp.2019.109117 doi: 10.1016/j.jcp.2019.109117
[15]	W. H. Luo, X. M. Gu, Y. Liu, M. Jing, A Lagrange-quadratic spline optimal collocation method for the time tempered fractional diffusion equation, Math. Comput. Simul., 182 (2021), 1–24. https://doi.org/10.1016/j.matcom.2020.10.016 doi: 10.1016/j.matcom.2020.10.016
[16]	M. Li, X. M. Gu, C. M. Huang, M. F. Fei, G. Y. Zhang, A fast linearized conservative finite element method for the strongly coupled nonlinear fractional Schrödinger equations, J. Comput. Phys., 358 (2018), 256–282. https://doi.org/10.1016/j.jcp.2017.12.044 doi: 10.1016/j.jcp.2017.12.044
[17]	Z. Y. Liu, X. R. Qin, N. C. Wu, Y. L. Zhang, The shifted classical circulant and skew circulant splitting iterative methods for Toeplitz matrices, Can. Math. Bull., 60 (2017), 807–815. https://doi.org/10.4153/CMB-2016-077-5 doi: 10.4153/CMB-2016-077-5
[18]	Z. Y. Liu, N. C. Wu, X. R. Qin, Y. L. Zhang, Trigonometric transform splitting methods for real symmetric Toeplitz systems, Comput. Math. Appl., 75 (2018), 2782–2794. https://doi.org/10.1016/j.camwa.2018.01.008 doi: 10.1016/j.camwa.2018.01.008
[19]	Z. Y. Liu, S. H. Chen, W. J. Xu, Y. L. Zhang, The eigen-structures of real (skew) circulant matrices with some applications, Comput. Appl. Math., 38 (2019), 178. https://doi.org/10.1007/s40314-019-0971-9 doi: 10.1007/s40314-019-0971-9
[20]	S. L. Lei, Y. C. Huang, Fast algorithms for high-order numerical methods for space fractional diffusion equations, Int. J. Comput. Math., 94 (2016), 1062–1078. http://dx.doi.org/10.1080/00207160.2016.1149579 doi: 10.1080/00207160.2016.1149579
[21]	Y. C. Huang, 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, Numerical Algorithms, 76 (2017), 605–616. https://doi.org/10.1007/s11075-017-0272-6 doi: 10.1007/s11075-017-0272-6
[22]	Z. L. Jiang, T. T. Xu, Norm estimates of $\omega$-circulant operator matrices and isomorphic operators for $\omega$-circulant algebra, Sci. China Math., 59 (2016), 351–366. https://doi.org/10.1007/s11425-015-5051-z doi: 10.1007/s11425-015-5051-z
[23]	Y. R. Fu, X. Y. Jiang, Z. L. Jiang, S. Jhang, Fast algorithms for finding the solution of CUPL-Toeplitz linear system from Markov chain, Appl. Math. Comput., 396 (2021), 125859. https://doi.org/10.1016/j.amc.2020.125859 doi: 10.1016/j.amc.2020.125859
[24]	X. Y. Jiang, K. Hong, Skew cyclic displacements and inversions of two innovative patterned matrices, Appl. Math. Comput., 308 (2017), 174–184. https://doi.org/10.1016/j.amc.2017.03.024 doi: 10.1016/j.amc.2017.03.024
[25]	Y. P. Zheng, S. Shon, J. Kim, Cyclic displacements and decompositions of inverse matrices for CUPL Toeplitz matrices, J. Math. Anal. Appl., 455 (2017), 727–741. https://doi.org/10.1016/j.jmaa.2017.06.016 doi: 10.1016/j.jmaa.2017.06.016
[26]	Z. L. Jiang, X. T. Chen, J. M. Wang, The explicit inverses of CUPL-Toeplitz and CUPL-Hankel matrices, East Asian J. Appl. Math., 7 (2017), 38–54. https://doi.org/10.4208/eajam.070816.191016a doi: 10.4208/eajam.070816.191016a
[27]	X. Zhang, X. Y. Jiang, Z. L. Jiang, H. Byun, An improvement of methods for solving the CUPL-Toeplitz linear system, Appl. Math. Comput., 421 (2022), 126932. https://doi.org/10.1016/j.amc.2022.126932 doi: 10.1016/j.amc.2022.126932
[28]	L. Du, T. Sogabe, S. L. Zhang, A fast algorithm for solving tridiagonal quasi-Toeplitz linear systems, Appl. Math. Lett., 75 (2018), 74–81. https://doi.org/10.1016/j.aml.2017.06.016 doi: 10.1016/j.aml.2017.06.016
[29]	P. P. Xie, 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., 498 (2016), 117–135. https://doi.org/10.1016/j.laa.2015.01.029 doi: 10.1016/j.laa.2015.01.029
[30]	J. Wu, X. M. Gu, Y. L. Zhao, Y. Y. Huang, B. Carpentieri, A note on the structured perturbation analysis for the inversion formula of Toeplitz matrices, Jpn. J. Ind. Appl. Math., 40 (2023), 645–663. https://doi.org/10.1007/s13160-022-00543-w doi: 10.1007/s13160-022-00543-w
[31]	I. Gohberg, V. Olshevsky, Circulants, displacements and decompositions of matrices, Integr. Equations Oper. Theory, 15 (1992), 730–743. https://doi.org/10.1007/BF01200697 doi: 10.1007/BF01200697
[32]	R. Chan, X. Q. Jin, An Introduction to Iterative Toeplitz Solvers, SIAM, Philadelphia, 2007. https: //doi.org/10.1137/1.9780898718850
[33]	R. E. Blahut, Fast Algorithms for Signal Processing, Cambridge University Press, New York, 2010. https://doi.org/10.1017/CBO9780511760921
[34]	H. Y. Jian, T. Z. Huang, X. M. Gu, X. L. Zhao, Y. L. Zhao, Fast implicit integration factor method for nonlinear space Riesz fractional reaction–diffusion equations, J. Comput. Appl. Math., 378 (2020), 112935. https://doi.org/10.1016/j.cam.2020.112935 doi: 10.1016/j.cam.2020.112935
[35]	M. Batista, 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., 210 (2009), 558–563. https://doi.org/10.1016/j.amc.2009.01.003 doi: 10.1016/j.amc.2009.01.003
[36]	M. K. Ng, Circulant and skew-circulant splitting methods for Toeplitz systems, J. Comput. Appl. Math., 159 (2003), 101–108. https://doi.org/10.1016/S0377-0427(03)00562-4 doi: 10.1016/S0377-0427(03)00562-4

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)