
Tridiagonalization Costs of the Bandwidth Contraction and
RutishauserSchwarz Algorithms
Ian A. Cavers
Department of British Columbia
University of British Columbia
November 4, 1993
Abstract
In this paper we perform detailed complexity analyses of the Bandwidth Contraction and RutishauserSchwarz 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.
1 Introduction
Both the Bandwidth Contraction (BC) algorithm, a generalization of Schwarz's diagonallyoriented algorithm [Sch63], and the columnoriented RutishauserSchwarz (RS) algorithm [Rut63, Sch68] use sequences of Givens similarity transformations to reduce a symmetric banded matrix to tridiagonal form. To simplify the complexity analysis of such algorithms we introduce a general framework for the analysis of algorithms using sequences of either standard or socalled fast Givens [Gen73] transformations. Using this framework we provide detailed analyses for standard and fast Givens variants of each algorithm, predicting the number of floating point operations required to reduce an N?N densely banded symmetric matrix, A, of bandwidthy b to tridiagonal form. Using several banded problems, we demonstrate the accuracy of each algorithm's analysis by checking their predicted operation counts with the symbolic sparse tridiagonalization tools Xmatrix and Trisymb.
Both Xmatrix and Trisymb estimate the flopz requirements of a tridiagonalization by manipulating sparsity structures to simulate a matrix's reduction. Xmatrix is an interactive tool which allows a user to specify a small sparse symmetric matrix and select a sequence of Givens transformations to effect its reduction. Alternatively, Trisymb symbolically reduces large sparse problems using one of several preselected algorithms, including R{S and BC. Xmatrix, Trisymb and the analyses of this paper assume numerical cancellation does not occur.
yBandwidth (or semibandwidth) is defined as b = maxi;j2f1:::Ng;i6=j ji ? jj such that Aij <> 0. zFollowing [GL89] a flop is defined to be any floating point arithmetic operation.