THE GEOMETRY OF ALGORITHMS WITH ORTHOGONALITY CONSTRAINTS

In this paper we develop new Newton and conjugate gradient algorithms on the Grassmann and Stiefel manifolds. These manifolds represent the constraints that arise in such areas as the symmetric eigenvalue probl em, nonlinear eigenvalue problems, electronic structures computations, and signal processing. In addition to the new algorithms, we show how the geometrical framework gives penetrating new insights allowing us to create, understand, and compare algorithms. The theory proposed her e provides a taxonomy for numerical linear algebra algorithms that pro vide a top level mathematical view of previously unrelated algorithms. It is our hope that developers of new algorithms and perturbation the ories will benefit from the theory, methods, and examples in this pape r.