All electron, first principles, periodic calculations have been carried out to investigate the relaxation of the Al-terminated corundum surface. Different theoretical formalisms, Hartree-Fock (HF) and density functional theory using either the LDA or the hybrid B3LYP exchange-correlation functional, have been employed. In the past, many ab initio studies of surface structure have been performed using the experimental, rather than the theoretically optimized bulk structures. In the current study, we show that this leads to significant differences in the predicted geometry. In addition, we demonstrate that optimizing a limited subset of surface parameters also has a significant effect on the accuracy of the final geometry. The extent of the effect associated with each of these sources is shown to be strongly dependent on the choice of exchange-correlation potential.