i******e
发帖数: 58 | 1 \sum_{i, j, k=1}^n {X(i,j)*X(j,k)*X(i,k), where X is a symmetric n by n
matrix.
计算复杂度能 < O(n^3) 么?
谢谢!!! | e**o
发帖数: 6038 | 2 复杂度定义是什么？
好奇，问问
【在 i******e 的大作中提到】
: \sum_{i, j, k=1}^n {X(i,j)*X(j,k)*X(i,k), where X is a symmetric n by n
: matrix.
: 计算复杂度能 < O(n^3) 么?
: 谢谢!!!
| i******e
发帖数: 58 | 3 O(n^3) means that the calculation can be bounded by M*n^3, for a
sufficiently large constant M.
【在 e**o 的大作中提到】
: 复杂度定义是什么？
: 好奇，问问
| e**o
发帖数: 6038 | 4 那不是只要 X_ij 一致有界不就是自然的结果了吗
【在 i******e 的大作中提到】
: O(n^3) means that the calculation can be bounded by M*n^3, for a
: sufficiently large constant M.
| i******e
发帖数: 58 | 5 忘记了一个条件, 矩阵X 的 每一个元素都是有限的.
这个求和 简单计算 的计算量 是 n^3, 想问一下有没有更快的算法, 或者不存在更快
的算法?
谢谢!!!
【在 e**o 的大作中提到】
: 那不是只要 X_ij 一致有界不就是自然的结果了吗
| c*******h
发帖数: 1096 | 6 相当于做一次矩阵乘法和一次hadamard积
hadamard积是O(n^2)的
矩阵乘法用Strassen可以从O(n^3)降到O(n^2.807)，用Coppersmith–Winograd
可以降到O(n^2.376)，这是理论上现在知道最快的了
如果要一个practical而且numerically stable的方法，还得回到原始的O(n^3)
的方法
【在 i******e 的大作中提到】
: \sum_{i, j, k=1}^n {X(i,j)*X(j,k)*X(i,k), where X is a symmetric n by n
: matrix.
: 计算复杂度能 < O(n^3) 么?
: 谢谢!!!
| i******e
发帖数: 58 | 7 你说的都对。
但是，这个求和不像矩阵乘法， 矩阵乘法需要知道结果矩阵的每一个元素。
如果求和\sum_{i, j, k=1}^n {X(i,j)*X(j,k)}，相当于做一次矩阵乘法， 然后再把
结果矩阵的每一个元素相加， 但是计算量是O(n^2), 因为可以先对 i 或 k 求和。
\sum_{i, j, k=1}^n {X(i,j)*X(j,k)*X(i,k) 不一样，i, j, k 相互耦合， 先对任何
一个先求和也绕不开另外两个。
谢谢。
【在 c*******h 的大作中提到】
: 相当于做一次矩阵乘法和一次hadamard积
: hadamard积是O(n^2)的
: 矩阵乘法用Strassen可以从O(n^3)降到O(n^2.807)，用Coppersmith–Winograd
: 可以降到O(n^2.376)，这是理论上现在知道最快的了
: 如果要一个practical而且numerically stable的方法，还得回到原始的O(n^3)
: 的方法
| c*******h
发帖数: 1096 | 8 i suggest you do the following:
1. compute Y(i,k) = \sum_j X(i,j)*X(j,k) for all i,k in whatever nasty way
2. sum = 0
3. for i = 1:n
4. for k = 1:n
5. sum += Y(i,k)*X(i,k)
6. endfor
7. endfor
the bottleneck is line 1
【在 i******e 的大作中提到】
: 你说的都对。
: 但是，这个求和不像矩阵乘法， 矩阵乘法需要知道结果矩阵的每一个元素。
: 如果求和\sum_{i, j, k=1}^n {X(i,j)*X(j,k)}，相当于做一次矩阵乘法， 然后再把
: 结果矩阵的每一个元素相加， 但是计算量是O(n^2), 因为可以先对 i 或 k 求和。
: \sum_{i, j, k=1}^n {X(i,j)*X(j,k)*X(i,k) 不一样，i, j, k 相互耦合， 先对任何
: 一个先求和也绕不开另外两个。
: 谢谢。
| i******e
发帖数: 58 | 9 Thank you for your suggestion.
But as you pointed out, the computation cost for line 1 is already n^3.
Any improvement?
【在 c*******h 的大作中提到】
: i suggest you do the following:
: 1. compute Y(i,k) = \sum_j X(i,j)*X(j,k) for all i,k in whatever nasty way
: 2. sum = 0
: 3. for i = 1:n
: 4. for k = 1:n
: 5. sum += Y(i,k)*X(i,k)
: 6. endfor
: 7. endfor
: the bottleneck is line 1
| c*******h
发帖数: 1096 | 10 Strassen, or Coppersmith-Winograd
【在 i******e 的大作中提到】
: Thank you for your suggestion.
: But as you pointed out, the computation cost for line 1 is already n^3.
: Any improvement?
| i******e
发帖数: 58 | 11 Thank you. I will read their papers.
【在 c*******h 的大作中提到】
: Strassen, or Coppersmith-Winograd
|
|
