Adaptive optics systems for future large optical telescopes may require thousands of sensors and actuators. Optimal reconstruction of phase errors using relative measurements requires feedback from every sensor to each actuator, resulting in computational scaling for n actuators of n2. The optimum local reconstructor is investigated, wherein each actuator command depends only on sensor information in a neighboring region. The resulting performance degradation "global" modes is quantified analytically, and two approaches are considered for recovering global performance. Combining local and global estimators in a two-layer hierarchic architecture yields computations scaling with n(4/3); extending this approach to multiple layers yields linear scaling. An alternative approach that maintains a local structure is to allow actuator commands to depend on both local sensors and prior local estimates. This iterative approach is equivalent to a temporal low-pass filter on global information and gives a scaling of n(3/2). The algorithms are simulated by using data from the Palomar Observatory adaptive optics system. The analysis is general enough to also be applicable to active optics or other systems with many sensors and actuators.