Vectorizing Dynamic Time Warping (DTW) algorithm Dynamic Time Warping algorithm has a terrible convergence O(M x N), where M and N are the lengths of the sequences being aligned. This is due to the cost matrix computation, where a sequential approach is needed in order to compute the cumulative costs.
What are the alternatives? How can one decrease the computational cost? Is there any way to vectorize the cost matrix computation? Is there any good approximation method?

You can reduce the amortized time for DTW to O(M), using the UCR suite [a].
Doing that, you can process a million subsequences a second.
[a] Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu, Jesin Zakaria, Eamonn Keogh (2012). Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping SIGKDD 2012. Best paper award, and  Test-of-time Paper Award in 2022
