Document Type : Research Paper
Authors
1 Align Technology Inc, San Jose, CA 95134, USA
2 School of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran
Abstract
In this paper we have developed an iterative method to solve eigenproblem for non-repetitive tridiagonal matrices. The importance of eigensolution for tridiagonal matrices is that in many algorithms the eigneproblem for an arbitrary matrix is first converted to the eigenproblem for a tridiagonal matrix and then the problem is tackled. Our proposed method was developed through taking advantages of some unique properties of repetitive and non-repetitive tridiagonal matrices. First, we established closed-form solutions for the system of linear equations $ \bf{Mx=f} $ for the condition $ \mathbf{M} $ is tridiagonal. When $ \mathbf{M} $ is a repetitive tridiagonal matrix, the unknown vector $ \mathbf{x} $, the vector $ \mathbf{f} $, and the coefficient matrix $ \mathbf{M} $ are expanded using orthogonal basis of matrix $ \mathbf{M} $ and closed-form relationships are obtained. For non-repetitive matrix $ \mathbf{M} $, the tridiagonal matrix algorithm is used to efficiently solve the matrix equation. We then using orthogonal basis of matrix $ \mathbf{M} $ and closed-form relationships are obtained. For non-repetitive matrix $ \mathbf{M} $, the tridiagonal matrix algorithm is used to efficiently solve the matrix equation. We then implemented these solutions in an iterative relationship for eigenproblem where eigenpairs of non-repetitive tridiagonal matrices were obtained through successive solution of the tridiagonal matrix equation efficiently solved above. Furthermore, closed-form relationships for eigenpairs of repetitive tridiagonal matrices were implemented in the algorithm as start point for eigensolution of non-repetitive tridiagonal matrices so that the required number of iterations was significantly reduced. Computational complexity of the proposed method is $ O(n^2) $ that is competitive with the best existing algorithms in literature. As indicated through several numerical examples, the advantages of the proposed algorithm include high rate of convergence, computational efficiency in each iteration, simple implementation, and availability of an objective start point for initialization.
Keywords
)