Computing the eigenvalues and eigenvectors of symmetric arrowhead matrices (Q753416)

The authors consider the eigenvalue problem for a symmetric real matrix A having all elements equal to zero except those in the main diagonal and one (last) column and one (last) row of A. In some physical applications the order n of such a matrix A may be in thousands. Instead of reducing such a matrix into tridiagonal form (that needs \(O(n^ 3)\) time and \(O(n^ 2)\) storage), the authors show that the eigenvalues may be obtained with \(O(n^ 2)\) time complexity and O(n) storage by solving a nonlinear (rational) equation closely related to the secular equation of the matrix A. This equation may be solved using a combination of the secant method and interval bisection (such a procedure is usually available in library subroutine packages). The formulae for eigenvectors of such a matrix are also derived and their exactness for obtained estimations of eigenvalues is analyzed. A general Wilkinson-style rounding-error analysis is also done. The calculations for one eigenvalue/eigenvector are completely independent of those for another, so the algorithm may be completely parallelized.