Eigenvalue Computation
with CUDA

Abstract

The computation of all or a subset of all eigenvalues is an important problem in linear algebra, statistics, physics, and many other fields. This report describes the implementation of a bisection algorithm for the computation of all eigenvalues of a tridiagonal symmetric matrix of arbitrary size with CUDA.

Background

In this section we will establish our notation and provide the mathematical background for the remainder of the report. On a first read some of the presented material might prove difficult for the mathematically less inclined reader. Most theorems can, however, be employed as black box results and their value becomes apparent when they are used in the next sections. Readers interested in a more thorough discussion of eigen analysis algorithms are referred, for example, to the book by Parlett [4] or the thesis by Dhillon [13].

Notation

In this report we will use Householder’s notation. Scalars are denoted by roman or greek lowercase letters such as   and  and  are used to represent vectors. If not mentioned otherwise, all vectors are assumed to be column vectors. Matrices are denoted by uppercase bold roman letters such as  indexed with two indices  and  denotes the row index and  the column index. A matrix  can thus be written as