Let us have square symmetric matrix of squared euclidean distances $\bf D$ between $n$ points and vector lengthed $n$ indicating cluster or group membership ($k$ clusters) of the points; a cluster may consist of $\ge1$ point.
What is the most efficient or really efficient (in terms of speed) way to compute distances between the cluster centroids here?
So far I always did Principal Coordinate analysis in this situation. PCoA, or Torgerson's MDS amounts to first converting $\bf D$ into the matrix of scalar products $\bf S$ ("double centering") and then performing PCA of it. This way we create coordinates for the $n$ points in the euclidean space they span. After that, it is easy to compute distances between the centroids the usual way - as you would do it with
grouped points x variables data. PCoA has to do eigen-decomposition or SVD of the
n x n symmetric positive semidefinite $\bf S$, but $n$ can be quite big. In addition, the task is not a dimensionality reduction one and we don't actually need those orthogonal principal axes. So I have a feeling that these decompositions might be an overkill.
So, do you have knowledge or ideas about a potentially faster way?