Silhouette Score takes close to exponential time when using dtw/soft-dtw

Hi, I am trying to train my model on 25,000 rows of time series data with each row having data for over 60 time-intervals. It is taking 2+ hours to fit and predict using kMeans & soft-dtw as distance metric. However, since I need to find optimal number of clusters, I need to run the algorithm for clusters 3-10 and calculate silhouette score each time.

Calculation of silhouette score is taking 3+ hours. Is there a way to speed this up? Also, how can I speed up this entire process?
How can I parallelize both soft-dtw and silhouette score?

Any suggestions would be much appreciated.

Thanks!

Start by profiling the silhouette-score calculation and the soft-DTW path used with kMeans on the reported 25,000-by-60 data. Compare runtime across cluster counts 3–10 and investigate whether parallelization changes the bottleneck. Done would require a specific, validated performance improvement, but the issue does not identify files or tests.