Tridiagonalization Costs of the Bandwidth Contraction and

Rutishauser-Schwarz 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 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.

1 Introduction

Both the Bandwidth Contraction (BC) algorithm, a generalization of Schwarz's diagonallyoriented algorithm [Sch63], and the column-oriented Rutishauser-Schwarz (R-S) 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 so-called 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 semi-bandwidth) 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.