Fast minimum variance wavefront reconstruction for extremely large telescopes

We present what we believe to be a new algorithm, FRactal Iterative Method (FRiM), aiming at the reconstruction of the optical wavefront from measurements provided by a wavefront sensor. As our application is adaptive optics on extremely large telescopes, our algorithm was designed with speed and best quality in mind. The latter is achieved thanks to a regularization that enforces prior statistics. To solve the regularized problem, we use the conjugate gradient method, which takes advantage of the sparsity of the wavefront sensor model matrix and avoids the storage and inversion of a huge matrix. The prior covariance matrix is, however, non-sparse, and we derive a fractal approximation to the Karhunen-Loève basis thanks to which the regularization by Kolmogorov statistics can be computed in O(N) operations, with N being the number of phase samples to estimate. Finally, we propose an effective preconditioning that also scales as O(N) and yields the solution in five to ten conjugate gradient iterations for any N. The resulting algorithm is therefore O(N). As an example, for a 128 x 128 Shack-Hartmann wavefront sensor, the FRiM appears to be more than 100 times faster than the classical vector-matrix multiplication method.