Tridiagonalization Costs of the Bandwidth contraction and Rutishauser-Schwarz Algorithms

ID
TR-93-39
Authors
Ian Cavers
Publishing date
November 1993
Length
20 pages
Abstract

In this paper we perform detailed complexity analyses of the Bandwidth Contraction and Rutishauser-Schwarz tridiagonalization algorithms using a general framework for the analysis of algorithms employing sequences of either standard or fast Givens transformations. Each algorithm's analysis predicts the number of flops required to reduce a generic densely banded symmetric matrix to tridiagonal form. The high accuracy of the analyses is demonstrated using novel symbolic sparse tridiagonalization tools, Xmatrix and Trisymb.