The term "adaptive optics" refers to the technology of sensing, estimating, and correcting the wavefront aberrations in an optical system in real time, so that (for example) a telescope on the ground can image astronomical objects as clearly as a telescope in space. The basic elements of an adaptive optical (AO) system include a wavefront sensor (WFS) to measure the wavefront aberrations, a deformable mirror (DM) to correct the aberrations, and a wavefront reconstruction algorithm to compute the DM commands from the WFS measurements.
Wavefront reconstruction may be formulated as a well-posed linear inverse problem, but it is on the verge of becoming computationally intractable for proposed systems with 10^4 or more measurements from multiple wavefront sensors, 10^4 or more actuator commands to be computed for multiple deformable mirrors, and update rates of approximately 1000 Hz.
Fortunately, it is now possible to compute reconstruction algorithms with complexity O(N^1.5)) instead of the O(N^3) required for classical techniques. New methods with complexity O(N) are under development. We describe one promising method based upon conjugate gradients, multigrid preconditioning, and a block from of symmetric Gauss Seidel smoothing. This algorithm is sufficient for non-real-time simulations of the AO systems now being proposed for 30 meter class telescopes, but further advances will be necessary to implement these computations in real time.