JuliaLang/IterativeSolvers.jl — pull request #31 by jiahao (2014-09-12 02:20:08+00:00)
Title: WIP: Implicitly restarted Arnoldi factorizers

This PR contains very naïve (but working!) implementations of the Arnoldi method for iteratively constructing partial Hessenberg factorizations (equivalently, Arnoldi factorizations, incomplete Hessenberg factorizations, or truncated Hessenberg factorizations), as encapsulated in the `ArnoldiFactorization` type which wraps the partial Hessenberg factorization (_H_, _V_) and the residual vector _r_ such that

![image](https://cloud.githubusercontent.com/assets/1732/4244520/2c4e5984-3a23-11e4-97ee-13204270cc17.png)

Explicitly restarted and implicitly restarted variants of Arnoldi are also implemented as `Restarted{Arnoldi}` and `ImplicitlyRestarted{Arnoldi}`. (The implicitly restarted Arnoldi method is the core numerical algorithm underlying ARPACK.) These iterators are constructed from `Restarted` and `ImplicitlyRestarted`; both are parametric `Factorizer` types which are themselves parametric on an underlying `Factorizer`. The idea is to factor out the the techniques for restarting the factorization process from the underlying factorization process itself. (It could easily be symmetric Lanczos or biorthogonal Lanczos instead, where the underlying matrix factorization object is the tridiagonal analogue of the Arnoldi factorization.)

There is a lot to do here:

- [ ] Figure out what to export
- [ ] The `Arnoldi` process should become parametric on the orthogonalization method (#28)
- [ ] The `Terminator` type should be consistent with #29
- [ ] The `Shifts` function should provide most (if not all) of the various spectral partitioning methods described in the ARPACK documentation. Currently, only the `LM` (largest magnitude) mode is implemented. The nice thing is that Julia allows users to specify a custom rule for partitioning the spectrum as a function (the `by` keyword argument of `Shifts`).
- [ ] The deflation step in `ImplicitlyRestarted{Arnoldi}` should be replaced with the bulge-chasing version of the implicitly shift QR update, which is much more efficient.
- [ ] Is there a "thin" version of the matrix factorization? What is the bare minimum state needed to be saved during the iteration process?