EFFICIENT ALGORITHMS FOR REAL SYMMETRIC TOEPLITZ LINEAR SYSTEM WITH LOW-RANK PERTURBATIONS AND ITS APPLICATIONS
Xing Zhang, Yanpeng Zheng, Zhaolin Jiang, Heejung Byun
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.
Topics & Concepts
Toeplitz matrixLevinson recursionAlgorithmMathematicsRank (graph theory)Linear systemSymmetric-key algorithmSymmetric matrixComputer scienceEncryptionCombinatoricsPure mathematicsMathematical analysisPublic-key cryptographyQuantum mechanicsPhysicsEigenvalues and eigenvectorsOperating systemMatrix Theory and AlgorithmsElectromagnetic Scattering and AnalysisOptical Network Technologies