Mathematical Sciences: Numerical Linear Algebra - Accuracy and Parallelism

Mathias等人研究了求线性系统特征值和特征向量的并行算法的精度，提出了求解特征值问题，特别是非对称问题的高效并行算法。该项目的第一部分集中于分析并行算法的精度--特别是1.并行前缀类型算法2.(可能是广义的)对称特征值和奇异值问题的Jacobi算法3.Hessenberg QR算法的实现。精度问题很重要，尽管人们在这方面做的工作很少，因为一些并行算法的精度可能比相应的串行算法低得多--以至于它们产生的结果是毫无意义的。项目的第二部分寻求非对称特征值问题的高效并行算法和提高对称特征值问题的并行算法的效率。非对称情况尤其重要，因为对于这个问题，没有一种算法可以适当地利用并行计算机的能力。并行算法被广泛使用和研究，因为它们使人们能够用比使用串行算法少得多的时间来解决计算问题。随着并行计算变得越来越普遍，拥有既准确又高效的并行算法是很重要的。这个项目的目标是为数值线性代数中的问题提供这样的算法。特征问题自然而然地出现在科学技术的各个领域，因此有效的算法对解决这些问题有着广泛的影响。

Mathias The investigator studies the accuracy of parallel algorithms for finding the eigenvalues and eigenvectors of linear systems and develops efficient parallel algorithms for eigenvalue problems, especially the nonsymmetric case. The first part of the project focuses on analysing the accuracy of parallel algorithms -- in particular 1. parallel prefix type algorithms 2. Jacobi algorithms for the (possibly generalized) symmetric eigenvalue and singular value problems 3. implementations of the Hessenberg QR algorithm. The question of accuracy is important, though little work has been done on it, because some parallel algorithms can be much less accurate than the corresponding serial algorithm -- so much so that the results that they produce are meaningless. The second part of the project seeks efficient parallel algorithms for the nonsymmetric eigenvalue problem and to improve the efficiency of the parallel algorithms for the symmetric eigenvalue problem. The nonsymmetric case is especially important as there is no algorithm for this problem that can properly exploit the capabilities of a parallel computer. Parallel algorithms are widely used and studied because they allow one to solve a computational problem in much less time than if one were to use a serial algorithm. As parallel computing becomes increasing common it is important to have parallel algorithms that are both accurate and efficient. The goal of this project is to provide such algorithms for problems in numerical linear algebra. Eigenproblems arise naturally in every area of science and technology, so effective algorithms to solve them have broad impact.