행렬 곱셈 한 치수보다 훨씬 큰 다른

Question

그래서 쉬트 라쎈의 행렬 곱셈 알고리즘 복잡도가 O (N^2.8) 을 갖지만이 NXN이고, A는 MXN는 무엇 경우 B는 NXN 경우에만 작동 읽기 그리고 B는 nxo 이며, m은 n 및 오보다 훨씬 더 큰하지만 N과 O를 여전히 나는 그런 행렬의 곱셈을 너무 필요로하는 프로젝트를하고

제로와 패딩은 곱셈이 오래 걸리고 있습니다 매우 큰 I 몇 가지 조언을 얻으려고했다 기존의 알고리즘을 사용해야합니까, 아니면 Strassen의 알고리즘을 수정하여 더 빨리 수행해야합니까?

Answer 1

https://en.m.wikipedia.org/wiki/Strassen_algorithm

• 크기의 곱 [2N 개의 X의 N]이 * N의 엑스 10N]를 행하도록 배열 20 별도 [N의 X의 N] * [N의 X의 N] 조작으로 수행 할 수있다 결과를 형성;

• 크기 [N x 10N] * [10N x N]의 연산은 10 개의 개별 [N x N] * [N x N] 연산으로 수행 할 수 있으며 합쳐서 결과를 형성합니다.

이러한 기술은 단순히 2 제곱의 제곱에 맞추기보다 구현이 더 복잡해집니다. 그러나 기존의 곱셈이 아닌 Strassen의 구현을 수행하는 모든 사람이 구현의 단순성보다 계산 효율성을 우선으로 고려한다는 것은 합리적인 가정입니다.