Postdoc: Stability Issues in the Parallel Solution of Certain Generalized Eigenvalue and Singular Value Problems

所提出的工作涉及某些特征值和奇异值问题的串行和并行算法的设计、分析和实现。这项工作的一个主要目标是设计出在浮点运算中实现时完全准确和稳定的算法。由于实际应用中出现的奇异值和特征值问题往往是非常大的阶数，因此本工作的第二个目标是开发这些算法的变体，这些算法在分布式存储MIMD多处理器上是有效的而不会损失精度。这类机器提供大型线性代数问题所需的计算能力和广泛的内存。这项工作将分四个阶段进行，复杂性不断增加。首先，PI将为数值算法和软件识别和构建稳定的构建块。例如，他们将研究用于各种初等平面变换的两个向量之间夹角的计算。下一阶段将完善现有的算法和软件，以反映我们对准确性和稳定性问题的最新理解。PI将对对称特征问题和奇异值分解特别感兴趣。第三阶段将开发新的算法，并为LAPACK等数值库提供软件。感兴趣的问题包括广义奇异值问题和乘积奇异值问题，以及余弦-正弦分解。最后一个阶段是将我们的算法高效地映射到分布式内存多处理器上，同时平衡并行性和数值稳定性之间的权衡。

The proposed work involves the design, analysis, and implementation of serial and parallel algorithms for certain eigenvalue and singular value problems. A primary goal of this work is to devise algorithms that are fully accurate and stable when implemented in floating point arithmetic. Because the singular value and eigenvalue problems arising in real-life applications are often of very large order, a second goal of this work is to develop variants of these algorithms that are efficient on distributed-memory MIMD multiprocessors without loss of accuracy. This class of machines provides both the computational power and the extensive memory required by large linear algebra problems. The work will proceed in four phases of increasing complexity. To begin, the PI will identify and construct stable building blocks for numerical algorithms and software. For example, they will study the computation of the angle between two vectors for use in various kinds of elementary plane transformations. The next phase will be to refine existing algorithms and software to reflect our newest understanding of accuracy and stability issues. The PI will be particularly interested in the symmetric eigenproblem and the singular value decomposition. The third phase will be to develop new algorithms and provide software for numerical libraries such as LAPACK. The problems of interest include the generalized and the product singular value problems, and the cosine-sine decomposition. The final phase will be to map our algorithms efficiently to distributed-memory multiprocessors while balancing the tradeoff between parallelism and numerical stability.