Complexity of Inversion of Block Triangular Toeplitz Matrices and Solution of Block Triangular Toeplitz Linear Systems

Abstract:

      In this paper, it is showed that the computational complexity of inversion of block triangular Toeplitz matrix U= (U₀, U₁,…, U_n-1 ) is O (m²nlogn + m³), as well as solution of block triangla r Toeplitz linear systems, where U 's are m×m mat rices. By using this results, we reduce arithmetic operations of division of polynomials from O(nlog²n) to O(nlogn).