JuliaLang/IterativeSolvers.jl — pull request #28 by jiahao (2014-07-09 02:58:00+00:00)
Title: WIP: Abstract algorithmic interface for iterative orthogonalization

This PR will eventually provide several iterative orthogonalization algorithms for constructing an orthogonal basis for a vector space. The literature makes a big deal about controlling for loss of orthogonality in iterative methods, and so this is my attempt to throw the kitchen sink at the problem by providing the more widely touted variants of Gram-Schmidt orthogonalization. (If nothing else, users should be able to test these claims of orthogonality loss by having fine-grained control over the orthogonalization steps.)

The key design consideration here is how to provide these methods, which form the underlying basis (so to speak) of iterative linear solvers and eigensystem solvers, in a way that is composable and user-controllable. The interface exposed herein is inspired by the sorting algorithms in `Base` and the [SortingAlgorithms.jl](http://github.com/JuliaLang/SortingAlgorithms.jl) package, where a single generic function is declared and methods are defined for each concrete algorithm. Similarly, this PR exposes new overloaded methods for `qrfact!` and dispatches on abstract `OrthogonalizationAlg <: Algorithm` subtypes. Unlike the sorting algorithms, however, the `Algorithm` subtypes also wrap parameters specifying the number of iterations. The hope is that the abstract `Algorithm` interface will compose naturally with higher-level linear solvers and eigensolvers, allowing for the possibility of mixing and matching different orthogonalization routines over the course of an iterative solve.

To-do
- [x] Implement classical Gram-Schmidt
- [ ] Implement modified Gram-Schmidt
- [x] Implement columnwise modified Gram-Schmidt
- [x] Implement the Pythagorean variant of the QR normalization routine, which loses precision more slowly
- [ ] Refactor the existing `qrfact!` methods to use the `normalize!` methods
- [ ] Implement the Cholesky variant of Gander, 1980
- [ ] Implement Rutishauser's superothogonalization
- [ ] Implement backward- and forward- reorthogonalizing variants
- [ ] Implement adaptively reorthogonalizing variants using Rutishauser's and Giraud-Langou's criteria
- [ ] Implement Businger-Golub style partial QR decompositions (using a Frobenius norm threshold)
- [ ] Implement devectorized methods for dense matrices and vectors
- [ ] Allow the orthogonalization to be continued from a given partially orthogonalized iteration state
- [ ] Tests using Lauchli's example