크기 k x k의 행렬에 대한 Strassen 알고리즘의 부동 소수 연산 수는 몇 개입니까?

Question

곱하기 k x k 행렬에 대해 this analysis of Strassen's algorithm을 이해하려고합니다. 그러나 나는 아직도 얼마나 많은 작업이 invovled 너무 확신하지 않습니다. 누군가가 이것을 명확히하는 데 도움이 될 수 있습니까?

Answer 1

페이지가 대략 O (N^2.807 ...)라고 말할 때 나는 이것이 부동 소수점 연산의 수를 대략적으로 추정하는 것이라고 생각합니다. 모든 루핑/반복은 정수 연산과 함께 수행됩니다.

Answer 2

수행되는 작업 수는 다음과 같이 결정됩니다. 먼저, 행렬을 k/2에서 크기의 4 개의 하위 노력으로 나눈 다음, 그 행렬의 7 회 반복 승산을 수행합니다. 그런 다음 원하는 결과를 얻기 위해 해당 제품을 계속 추가합니다. 7> 2 LG

T (1) = 1

T (K) = 7T (K/2) + CK ²

주 : 이것은 다음과 같이 우리에게 한정된 점화식을 준다 , 왜냐하면 lg 7> lg 4 = 2. (여기서, lg는 이진 대수입니다. 따라서 Master theorem 중 하나의 경우에 알고리즘 알고리즘의 점근 적 복잡성은 O (k ^{lg 7}) ≈ O (k ^2.807)입니다.

희망이 도움이됩니다.