Fast Matrix Inversion Algorithm And Its Application To Palindromic Eigenvalue Problems

Fast algorithms for large-scale sparse matrix inversion are of fundamental importance and of recent research interests.In this paper,a new fast algorithm for computing the inversion of block tridiagonal Toeplitz matrices is proposed.It first computes four block vectors on the edge of the inverse in a divide-and-conquer way,and then represents the inverse in terms of these four block vectors using block displacement operators,where FFT-based techniques can be applied.The paper is inspired by the work of solving a palindromic quadratic eigenvalue problem(PQEP)of special structure which occurs in the vibration analysis of fast trains.The new fast algorithm is based on the current structure-preserving algorithm for solving a related matrix equation,and reducing the eigenvalue problem to the matrix equation is called the solvent approach.In the current algorithm there appears a block tridiagonal Toeplitz linear system and the proposed fast inversion algorithm fits well in solving that problem,making the present algorithms much faster,especially when the size of problem is large.Numerical examples are presented to show the effectiveness and efficiency of the improved fast algorithm.