Decompositions of Some Special Block Tridiagonal Matrices

In this paper, we present a unified approach to decomposing a special class of block tridiagonal matrices K (α ,β ) into block diagonal matrices using similarity transformations. The matrices K (α ,β )∈ Rpq× pq are of the form K (α ,β = block-tridiag[β B,A,α B] for three special pairs of (α ,β ): K (1,1), K (1,2) and K (2,2) , where the matrices A and B, A, B∈ Rp× q , are general square matrices. The decomposed block diagonal matrices (α ,β ) for the three cases are all of the form: (α ,β ) = D1 (α ,β ) ⊕ D2 (α ,β ) ⊕---⊕ Dq (α ,β ) , where Dk (α ,β ) = A+ 2cos ( θk (α ,β )) B, in which θk (α ,β ) , k = 1,2, --- q , depend on the values of α and β. Our decomposition method is closely related to the classical fast Poisson solver using Fourier analysis. Unlike the fast Poisson solver, our approach decomposes K (α ,β ) into q diagonal blocks, instead of p blocks. Furthermore, our proposed approach does not require matrices A and B to be symmetric and commute, and employs only the eigenvectors of the tridiagonal matrix T (α ,β ) = tridiag[β b, a,αb] in a block form, where a and b are scalars. The transformation matrices, their inverses, and the explicit form of the decomposed block diagonal matrices are derived in this paper. Numerical examples and experiments are also presented to demonstrate the validity and usefulness of the approach. Due to the decoupled nature of the decomposed matrices, this approach lends itself to parallel and distributed computations for solving both linear systems and eigenvalue problems using multiprocessors.

ON BLOCK MATRICES ASSOCIATED WITH DISCRETE TRIGONOMETRIC TRANSFORMS AND THEIR USE IN THE THEORY OF WAVE PROPAGATION

Block matrices associated with discrete Trigonometric transforms （DTT＇s） arise in the mathematical modelling of several applications of wave propagation theory including discretizations of scatterers and radiators with the Method of Moments, the Boundary Element Method, and the Method of Auxiliary Sources. The DTT＇s are represented by the Fourier, Hartley, Cosine, and Sine matrices, which are unitary and offer simultaneous diagonalizations of specific matrix algebras. The main tool for the investigation of the aforementioned wave applications is the efficient inversion of such types of block matrices. To this direction, in this paper we develop an efficient algorithm for the inversion of matrices with U-diagonalizable blocks （U a fixed unitary matrix） by utilizing the U- diagonalization of each block and subsequently a similarity transformation procedure. We determine the developed method＇s computational complexity and point out its high efficiency compared to standard inversion techniques. An implementation of the algorithm in Matlab is given. Several numerical results are presented demonstrating the CPU-time efficiency and accuracy for ill-conditioned matrices of the method. The investigated matrices stem from real-world wave propagation applications.