AN INVERSE EXTREME EIGENPAIR PROBLEM AND ITS PARALLEL ITERATIVE SOLUTION FOR SYMMETRICAL TRIDIAGONAL MATRICES

This article concerns computing the largest (or smallest) eigenvalue and corresponding eigenvector of a large irreducible symmetric tridiagonal matrix. We divide the original extreme eigenpair problem into p subproblems when the matrix is partitioned in p-block form. An inverse extreme eigenpair problem associated with the divide method is considered: Find a (p - 1)-dimensional vector a such that the largest eigenvalue lambda of a given symmetric tridiagonal matrix T is the common largest eigenvalues of p small matrices T-i(a) which are updated matrices of the diagonal blocks T-i of T with rank-one/two corrections. We prove that the inverse problem is solvable and has a unique positive solution and that the corresponding eigenvector of T-i(a) with the positive solution a forms a section of the eigenvector of T corresponding to its largest eigenvalue. An algorithm is proposed for solving the inverse problem iteratively, on which a system of nonlinear equations should be solved for each of its iterative steps. It is proved that the iterative scheme converges for any positive initial vector and that its convergence is asymptotically quadratic. The new method can be used to compute the extreme eigenpairs of T and is well suited for parallel implementation. Some numerical tests were performed, which show the efficiency of the new parallelizable algorithm.