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.
