Faster Eigenvalue Computations

更快的特征值计算-Roy Mathias William and MaryABSTRACTI学院将开发新的、更快的算法来解决特征问题。我的方法是主动迫使通缩发生，而不是被动地等待通缩发生。这种被称为激进通货紧缩的想法是由布拉曼、拜尔斯和马蒂亚斯提出的。这个想法的一个非常简单的未经调整的实现导致了高达3倍的计算节省。我的项目由两个部分组成。第一部分是完善激进通货紧缩的实施细节，将其扩展到其他特征值问题，并编写实现这些想法的软件，以便其他人可以轻松使用它们--就像黑匣子一样。这将提供一种简单的方法来极大地提高特征值计算的速度。鉴于上述结果，我对该项目第一部分的效用和成功几乎没有怀疑。第二部分要雄心勃勃得多，也更具投机性。它是反复使用激进的通货紧缩思想，并精心选择参数，以便能够迫使如此多的通货紧缩，以至于在Hessenberg本征值问题的情况下，复杂性低于现在标准的n次方，并且对于许多问题族来说，可能低至n平方-log(N)。我希望对其他特征值问题的算法做出类似的改进。许多物理系统都是使用矩阵建模的。这些矩阵的特征值提供了对这些系统如何运行的洞察。这里有两个著名的本征值实用的例子。首先，可以通过分析相关矩阵的特征值来预测塔科马窄桥的倒塌。其次，每个化学元素发出特征频率的光，这些特征频率是相关矩阵的特征值。人们可以通过观察恒星发出的光的频率来推断恒星的组成。用于对系统建模的矩阵越大，模型就越准确。不幸的是，用于计算n乘n矩阵的特征值的标准方法的算术运算的数量与n次方成正比。我计划开发这样的算法：1.运算次数与n的平方成正比(大约)，由于n可以是数千或数百万，这一明显的微小改进应该被证明是非常有用的；2.可以利用现代超级计算机的能力，也许具有讽刺意味的是，从内存中调用数字比乘法或加法花费更长的时间。

FASTER EIGENVALUE COMPUTATIONSRoy MathiasCollege of William and MaryABSTRACTI will develop new, much faster, algorithms to solve eigenproblems. My approach is to actively force deflations, rather than passively waiting for them to occur. This idea, called aggressive deflation, was developed by Braman, Byers and Mathias. A very simple untuned implementation of the idea resulted in computational savings of up to a factor of 3. My project consists of two parts. The first part is to perfect the details of the implementation of aggressive deflation, to extend it to other eigenvalue problems, and to write software implementing these ideas, so that others can use them easily -- like a black box. This will provide a simple way to greatly increase the speed of eigenvalue computations. In light of the results mentioned above I have little doubt about the utility and success of this first part of the project. The second part is much more ambitious and more speculative. It is to repeatedly use the aggressive deflation idea, with carefully chosen parameters, so that one is able to force so many deflations that, in the case of the Hessenberg eigenvalue problem, the complexity is less than the now standard n-cubed, and is perhaps as low as n-squared-log(n) for many families of problems. I hope to make similar improvements in algorithms for other eigenvalue problems.Many physical systems are modeled using matrices. The eigenvalues of these matrices provide insight on how these systems behave. Here are two well known examples of the utility of eigenvalues. Firstly, the collapse of the Tacoma narrows bridge could have been predicted by analyzing the eigenvalues of the associated matrix. Secondly, each chemical element emits light of characteristic frequencies, which are the eigenvalues of an associated matrix. One can deduce the make up of stars just by observing the frequencies of light they emit. The larger the matrix used to model the system the more accurate the model. Unfortunately, the number of arithmetic operations that the standard approach to computing the eigenvalues of a n-by-n matrix is proportional to n-cubed. I plan to develop algorithms which 1. have operation count proportional to n-squared (approximately), and since n can be in the thousands or millions this apparently minor improvement should prove very useful, and 2. can exploit the capabilities of modern super computers, which perhaps ironically, take longer to recall numbers from memory than to multiply or add them.