A quick way to calculate the next product
Considering
1) a 1xn
vector a
,
2) a nx1
vector b
,
3) a nxn
matrix X
,
the problem is getting an iterative method that can compute the product
a*{X*{X*{X*X}*X}*X}*b
as fast as possible, where parenthesis {Y}
is a user-defined operator that returns a matrix whose diagonal elements are all zero and whose off-diagonal elements are equal to the elements of the matrix Y
.
Note:
Without the parenthesis operator {}
, if we need to compute the product a*X*X*X*X*X*X*b
, I think we can naturally concatenate the matrix multiplication operator *
like this:
(((a*X)*X)*X)*(X*(X*(X*b)))
so it's a total time complexity O(n^2)
. However, when it comes to calculating
a*{X*{X*{X*X}*X}*X}*b
I don't know how to change the kind of association *
. I would appreciate it if someone could give me some advice to show the possibility of iterative computation a*{X*{X*{X*X}*X}*X}*b
at the same time O(n^2)
, rather than O(n^3)
.
source to share
I doubt we will come up with the o(matrix-multiplication(n))
-time algorithm today, the next drop. However, it is possible for the use of space to be linear.
Let {Y} = Y - diag(Y)
. I will consider a simpler computation problem a*{X*{X*X}*X}*b'
. Using linearity diag
, we write
{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).
Now let's look at each term in turn. The first term is a*X*X*X*X*b' = ((a*X)*X)*(X*(X*b'))
calculated using operations O(n^2)
. The second term is a*X*diag(X*X)*X*b' = (a*X)*diag(X*X)*(X*b')
also. So the fourth term a*diag(X*diag(X*X)*X)*b'
.
The third term is problematic, a*diag(X*X*X*X)*b'
. Since the other three are computable with operations O(n^2)
, this is equivalent in some sense to the whole computation.
Let j
- all-one vector. Then j*diag(X*X*X*X)*j' = tr(X^4)
. If X
is the adjacency matrix of the graph, then tr(X^4)
is the number of (possibly degenerate) 4-cycles. Assuming an undirected simple graph, the number of degenerate 4-cycles is given by a simple function of the sequence of degrees. the prior art in counting cycles does not appear to be better than matrix multiplication.
source to share