PERF Optimize dot product order #17684
Description
When multiplying 3 or more matrices, the order of parathesis doesn't impact the results but it can have a very significant impact on the number of operations and on performance see https://en.wikipedia.org/wiki/Matrix_chain_multiplication
For matrix multiplication of dense arrays there is numpy.linalg.multi_dot and we we should use it I think. To find existing occurrences where it could be used, see for instance the result of
git grep 'dot(.*dot'
sklearn/datasets/_samples_generator.py: return np.dot(np.dot(u, s), v.T)
sklearn/datasets/_samples_generator.py: X = np.dot(np.dot(U, 1.0 + np.diag(generator.rand(n_dim))), Vt)
sklearn/decomposition/_fastica.py: w -= np.dot(np.dot(w, W[:j].T), W[:j])
sklearn/decomposition/_fastica.py: return np.dot(np.dot(u * (1. / np.sqrt(s)), u.T), W)
sklearn/decomposition/_fastica.py: S = np.dot(np.dot(W, K), X).T
sklearn/decomposition/_nmf.py: norm_WH = trace_dot(np.dot(np.dot(W.T, W), H), H)
sklearn/decomposition/_nmf.py: denominator = np.dot(np.dot(W.T, W), H)
sklearn/discriminant_analysis.py: self.coef_ = np.dot(self.means_, evecs).dot(evecs.T)
sklearn/gaussian_process/_gpc.py: s_1 = .5 * a.T.dot(C).dot(a) - .5 * R.T.ravel().dot(C.ravel())
sklearn/gaussian_process/_gpc.py: s_3 = b - K.dot(R.dot(b)) # Line 14
sklearn/linear_model/_bayes.py: coef_ = np.dot(X.T, np.dot(
sklearn/linear_model/_logistic.py: ret[:n_features] = X.T.dot(dX.dot(s[:n_features]))
sklearn/linear_model/_ridge.py: AXy = A.dot(X_op.T.dot(y))
Ideally each replacement should be benchmarked.
For matrix multiplication safe_sparse_dot using a combination of sparse and dense matrice, some of this could apply as well, though defining a general heuristic is probably a bit more difficult there.