Numerical Solution of Least Squares Eigenvalue Problems

这个项目解决了一些关于最小二乘和特征值问题的精确解的公开问题。这两个问题领域是相互关联的，但每个领域都有不同的问题。对于最小二乘问题的研究，在算法的分析和实现方面仍然存在重要的问题。将考虑解等式约束最小二乘问题的直接方法和迭代方法。直接方法的工作涉及稀疏问题和消息传递体系结构的错误分析和实现问题。迭代方法的努力涉及到一类能够很好地处理约束最小二乘问题的预条件的发展。本征值问题的研究是以理论问题为基础的。最近，关于一类对称对角占优矩阵的特征值的相对误差的摄动界得到了发展。已有研究表明，有些算法达到了这些界限。对于一类重要的算法--分而治之算法，目前尚不清楚能否达到相对误差界。由于这类算法在几种分布式存储体系结构上都表现出了良好的性能，因此这一悬而未决的问题的解决将对特征值问题的求解产生重大影响。

This project addresses a number of open questions concerning the accurate solution of least squares and eigenvalue problems. These two problem areas are interrelated, but there are separate issues for each one of them. For the work on least squares problems, there remain important issues in both the analysis and implementation of the algorithms. Both direct and iterative methods for the solution of equality constrained least squares problems will be considered. The work on direct methods concerns error analysis and implementation issues for sparse problems and for message passing architectures. The effort on iterative methods concerns the development of a class of preconditioners that would work well on constrained least squares problems. The investigation of the eigenvalue problems is based upon theoretical questions. Recently perturbation bounds on the relative errors in the eigenvalues of a certain class of symmetric diagonally dominant matrices have been developed. It has been shown that some algorithms achieve these bounds. For one important class of algorithms, divide-and-conquer algorithms, it is not known whether the relative error bounds can be achieved. Since this class of algorithms has shown good performance on several distributed memory architectures, the resolution of this open question will have a significant impact on how eigenvalue problems are solved.