Eigenvalue problems arise in many diverse areas of science and engineering, including, but by no means limited to nuclear magnetic resonance, signal processing, speech processing, and control theory. This project will build on previous algorithmic innovations to further accelerate the numerical solution of one class of these important problems. This research is typical of the field of Numerical Linear Algebra in that it is a blending of mathematics and computer science. Specifically, new deflation strategies, which should allow large eigenvalue problems to be broken into smaller sub-problems, will be implemented and tested. If successful, a production quality code will be submitted to netlib.org for inclusion in the Linear Algebra Package (LAPACK), an open-source repository of reliable scientific computational software.
An eigenvalue problem can be described as: Given a matrix of real or complex numbers, compute some or all of its eigenvalues and their corresponding eigenvectors. Eigenvalue problems arise in many diverse areas of science and engineering, including, but by no means limited to nuclear magnetic resonance, signal processing, speech processing, and control theory. Eigenvalue analysis allows structural engineers to compute the natural frequencies of a building or bridge, provides financial analysts with a means of predicting stock prices, gives statisticians tools for identifying clusters in large data sets and underlies Google's PageRank algorithm. In some instances, only the first few largest eigenvalues are of interest, while others require computation of all of the eigenvalues. The goal of this project was to build upon previous algorithmic innovations to further accelerate the computation of large, dense eigenproblems where all eigenvalues are desired. Dense means that the underlying matrix has relatively few zero entries, probably with no particular structure to their positions. At the time of this project a large matrix for a dense eigenproblem is one with dimensions 10,000 by 10,000 or larger. Since its introduction in 1961 by J.G.F. Francis and independently the same year by V.N. Kublanovskaya, the QR Algorithm has remained the method of choice for solving dense eigenvalue problems. In 2000, Computing in Science and Engineering named the QR Algorithm one of the top ten algorithms of the twentieth century. A key factor in the overall performance of the QR Algorithm is identification of converged eigenvalues and the subsequent reduction in size of the problem. This process is called deflation. In 2002 Braman, Byers and Mathias introduced the technique of Aggressive Early Deflation (AED) to significantly improve the performance of the QR Algorithm. AED focuses on a submatrix of the problem which is referred to as a deflation window. The QR Algorithm itself is used to compute the eigenvalues of this deflation window, and, under certain conditions, some of these eigenvalues can be identified as converged eigenvalues of the larger matrix. Although the solution of the deflation window eigenvalues requires a substantial computational cost, when enough deflations are identified "early", the total time to solve the entire eigenproblem can be as much as five times faster than without using AED. The focus of this research project was to determine whether increasing the number of deflation windows and also varying their sizes and positions would result in additional acceleration of the QR Algorithm. The results have been somewhat mixed. For large, dense matrices where the entries are randomly taken from a normal distribution, a multiwindow approach proved to be beneficial, cutting runtimes by as much as 50% (see Figure 1). However, when applied to various matrices from real world applications, the multiwindow technique has not been found to improve performance. Further study to provide an explanation for this disparate behavior is ongoing.
