Synthesizing optimal controllers for large scale uncertain systems is a challenging computational problem. This has motivated the recent interest in developing polynomial-time algorithms for computing reduced dimension models for uncertain systems. Here we present algorithms that compute lower dimensional realizations of an uncertain system, and compare their theoretical and computational characteristics. Three polynomial-time dimensionality reduction algorithms are applied to the Shell Standard Control Problem, a continuous stirred-tank reactor (CSTR) control problem, and a large scale benchmark problem, where it is shown that the algorithms can reduce the computational effort of optimal controller synthesis by orders of magnitude. These algorithms allow robust controller synthesis and robust control structure selection to be applied to uncertain systems of increased dimensionality.