A graph-theoretic model of symmetric givens operations and its implications Original Research Article

Symmetric Givens operations (A′ ← GAGT, G a Givens rotation matrix) are a basic tool in many matrix computations, especially for eigenvalue-eigenvector computations. A graph-theoretic model of these operations is given for symmetric matrices, analogous to the graph-theoretic model of Cholesky factorization. Using this model, it is shown that unless there is “accidental cancellation,” it is impossible to reduce a range of different matrix classes to tridiagonal form in o(n2) Givens operations; these classes include arrowhead matrices, pentadiagonal matrices, and cyclic tridiagonal matrices.