讓A是一個給定的方陣，其大小爲nxn。令A[i]表示通過用零列向量代替列的A而形成的nxn矩陣。如何減少矩陣乘法的次數
現在我想計算以下(n^4+n^3+n^2)矩陣產品：
{A[x]*A[y]*A[z]*A[w] | for all x=1,...n , y=1,...,n , z=1,...n, and w=1,...,n}
{A[y]*A[z]*A[w] | for all y=1,...,n , z=1,...n, and w=1,...,n}
{A[z]*A[w] | for all z=1,...n, and w=1,...,n}
如果我計算出每個產品的天真，也需要O((n^4+n^3+n^2)*n^3)時間複雜度（假設矩陣乘法需要O(n^3)時間）。
但是，我注意到有許多重複的乘法可以被記憶。有沒有一種有效的方法（如DP）可以儘可能減少矩陣乘法的次數？
第一個明顯的優化是使用第三組的結果來計算第一個。
想到的第二個稍微有點棘手。
B[i]讓表示nxn 0矩陣與通過i的A（i.o.w. B[i] = A - A[i]）i第柱代替第柱。
然後用矩陣分佈定律[1]重寫矩陣乘積，就像這樣。 A[x]*A[y] = (A - B[x])(A - B[y]) = (A - B[x])A - (A - B[x])B[y] = AA - B[x]A - AB[y] - B[x]B[y]。
由於B[i]是隻有一個非零列的稀疏矩陣，因此上面的產品非常容易計算，加上一個「滿」矩陣乘法 - AA - 只需要計算一次。
3乘法情況如下所示。 A[x]*A[y]*A[z] = AAA - B[x]AA - AB[y]A + B[x]B[y]A - AAB[z] + B[x]AB[z] + AB[y]B[z] + B[x]B[y]B[z]。
經過上一步，我們已經有大部分因素（每個B[i]A和AB[i]），如果內存不擔心;或者我們可以很容易地計算出它（因爲再次，B[i]是稀疏的）。
4乘法情況然後可以完成類似物。
乘法A [Z]和A [W]，跳過 '0' 列中w的每一次迭代，然後簡單地填充該列用零在應答（或者如果你調用內存，然後默認它已經是0）。這是你的問題＃3
現在，取這個矩陣，它有一個列（wth列），並乘以A [y]，再次利用這一事實，即同一列是零和你可以跳過乘法。你現在有＃2。
重複這一次乘以A [x]這個結果，利用相同的0列。總的來說，你總共有3 *（n-1）* n *（2n）= 6 * n^3 - 6 * n^2個乘法（如果我的數學是正確的話）。