Strassen의 알고리즘을 이길 수있는 알고리즘

-4

교수 Caesar는 Strassen의 알고리즘보다 점차 빠르게 인 행렬 곱셈 알고리즘을 개발하고자합니다. 그의 알고리즘은 각 행렬을 크기 n/4 x n/4의 조각으로 나누는 divide and-conquer 방법을 사용할 것이며 나누기와 결합 단계를 함께하면 Theta (n^2) 시간이 걸립니다.Strassen의 알고리즘을 이길 수있는 알고리즘

출처

2016-10-02 useruser1412

이 문제를 해결하기위한 * 모든 노력을 보여줄 수 있습니까? –

@ScottHunter이 솔루션을 온라인으로 찾았지만 이해하지 못했습니다. http://clrs.skanev.com/04/05/02.html – useruser1412

어떤 해결책이 있습니까? 나는 어떤 해결책도 보지 못했다. –

여기에 질문이 무엇인지 구체적으로 설명하지는 않지만이 사소한 알고리즘이 Strassen보다 빠르게 실행된다는 것을 반증하는 것입니다.

은 ( K이며, 귀하의 질문에 4) 블록으로 차원의 각 (N/K) X (N/K) 당신의 행렬을 나누는 말. 각 행렬 K ² 블록이되며, K ³ 블록 승산있을 것이다 (첫 번째 행렬에서의 각 블록은 2 매트릭스에서 K 블록을 곱한 것). 따라서, 복잡도 재발

T (n)은 K = 3 T (N/K) + Θ (N 2⁾이다. case 1 of the Master theorem 바이

,이

T (N) = (N ³) Θ (N ^{로그 K (K ³)}) = Θ을 의미한다.

이것은 일반적인 행렬 곱셈과 같습니다. Strassen을 이길 수는 없습니다.

출처

2016-10-03 06:52:41

"행렬을 k 블록으로 나눕니다 ... 각 행렬에는 k^2 블록이 있습니다"? –

@ScottHunter 많은 감사합니다! 그것은 끔찍한 오타였습니다. –

아니, 그것은 화려한 오타되었습니다 :) –

Strassen의 알고리즘을 이길 수있는 알고리즘

답변

관련 문제