A framework for symmetric band reduction and tridiagonalization

TL;DRAbstract

This paper develops a framework for bandwidth reduction and tridiagonalization algorithms for symmetric banded matrices. The algorithm family includes the algorithms by Rutishauser and Schwarz, which underly the EISPACK and LAPACK implementations, and the algorithm recently proposed by Lang. Our framework leads to algorithms that require fewer floating-point operations, allow for space-time tradeoffs, enable the use of block orthogonal transformations, and increase the degree of parallelism inherent in the algorithm. 1 Introduction Reduction to tridiagonal form is a major step in eigenvalue computations for symmetric matrices. If the matrix is full, the conventional Householder tridiagonalization approach [11, 4, p. 276] or block variants thereof [9] is the method of choice. However, for banded matrices with semibandwidth b, where b ø n, this approach is not optimal since the matrix being reduced has completely filled in after log 2 (n=(b \\Gamma 1)) reduction steps. It is well known t

Chat with Paper

AI Agents for this Paper