A faster multidimensional scaling?
You may use a sampling based method, in which you get an approximation of the actual result by combining the partial results for samples extracted from your data. There are several methods based on sampling, but you could take a look to the following link as an example, so you can understand what I am talking about:

A Fast Approximation to Multidimensional Scaling