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.