快速计算以下乘积的方法

Question

给定

1）一个1xn向量a,

2）一个nx1向量b,

3）一个nxn矩阵X,

问题是获得一种迭代方法，它可以尽可能快地计算出乘积

a*{X*{X*{X*X}*X}*X}*b，其中括号{Y}是一个用户定义的运算符，返回一个所有对角线元素都为零且其非对角线元素等于矩阵Y的元素。

---

注意：

如果没有括号{}运算符，如果想计算乘积a*X*X*X*X*X*X*b，我认为我们可以自然地将矩阵乘法运算符*与之关联，如下所示：

(((a*X)*X)*X)*(X*(X*(X*b)))

因此总时间复杂度为O(n^2)。然而，当涉及到计算

a*{X*{X*{X*X}*X}*X}*b

我不知道如何改变*的关联顺序。如果有人能给我一些提示，以显示迭代计算a*{X*{X*{X*X}*X}*X}*b在与O(n^2)相同的时间内完成，而不是O(n^3)，我将不胜感激。

- John Smith

---

我不确定我理解这个问题，a*{X*{X*{X*X}*X}*X}*b = {{{{{{a*X}*X}*X}*X}*X}*X}*b。 - amit

@DavidEisenstat 是的，矩阵乘法是结合律。 - amit

@amit {} 改变了涉及的矩阵。我认为它不再是可结合的了。 - Teepeemm

@Teepeemm 好的，现在我明白了。{} 不仅仅是显示操作顺序。谢谢你澄清，现在问题更有意义了。我知道我之前没有理解这个问题。 - amit

不，我必须提到 {X*Y}*Z != X*{Y*Z}，尽管传统的矩阵乘法是可结合的。 - John Smith

Answer 1

我怀疑我们今天不可能通过以下简化来设计出一个O(矩阵乘法(n))时间复杂度的算法。但是，我们可以将空间使用降至线性。

令{Y} = Y - diag(Y)。我将考虑计算更简单的问题，即计算a*{X*{X*X}*X}*b'。利用diag的线性性，我们可以写成：

{X*{X*X}*X} = {X*(X*X - diag(X*X))*X}
            = X*(X*X - diag(X*X))*X - diag(X*(X*X - diag(X*X))*X)
            = X*X*X*X - X*diag(X*X)*X - diag(X*X*X*X - X*diag(X*X)*X)
            = X*X*X*X - X*diag(X*X)*X - diag(X*X*X*X) + diag(X*diag(X*X)*X).

现在逐个考虑每个术语。第一个术语，a*X*X*X*X*b' = ((a*X)*X)*(X*(X*b'))，可通过O(n^2)次运算计算。第二个术语，a*X*diag(X*X)*X*b' = (a*X)*diag(X*X)*(X*b')，也是如此。第四个术语a*diag(X*diag(X*X)*X)*b'同样如此。问题出在第三个术语上，a*diag(X*X*X*X)*b'。由于其他三个术语可以通过O(n^2)次运算计算，因此从某种意义上说，它相当于整个计算。

让j成为全1向量。那么j*diag(X*X*X*X)*j' = tr(X^4)。如果X是图的邻接矩阵，则tr(X^4)是（可能退化的）4个周期数。假设是无向简单图，退化的4个周期数由度序列的一个简单函数给出。周期计数中的最新技术似乎并不比矩阵乘法更好。

- David Eisenstat

---

谢谢，但我只是想知道对于计算“tr(X^4)”的简化是否正确。因为如果将“j”视为单位向量，则似乎可以使用“O(n^2)”计算该问题。 - John Smith

@JohnSmith 给我点启示。 - David Eisenstat