performance - 计算以下产品的快速方法

Question

给定

1) 1xn 向量a,

2) 一个nx1向量b,

3) 一个nxn矩阵X,

问题是获得一个可以计算乘积的迭代方法

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

as fast as possible，其中括号{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)。

Answer 1

我怀疑我们今天能否通过以下归约得出一个 o(matrix-multiplication(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 为全一向量。然后 j*diag(X*X*X*X)*j' = tr(X^4)。如果 X 是图的邻接矩阵，则 tr(X^4) 是(可能退化的)4 循环的数量。假设一个无向简单图，退化 4 循环的数量由度数序列的一个简单函数给出。 state of the art in cycle counting似乎并不比矩阵乘法好。