matrix_multiply_quadratic
1.0.0
이 소스 코드 (Python)는 내 전제 중 하나에서 시간과 공간 복잡성으로 이론적으로 입증 된 2 차 시간의 양성 정수 매트릭스 곱셈의 예비 구현입니다 [1]. strassen (O (n^log2 (7)) = O (n^2.807)) [2], Bini et al. (O (n^2.78)) 그러나 이들 모두는 이론적으로 건전하지만 텐서 파워와 같은 무거운 데이터 구조로 인해 실질적으로 구현할 수있는 것은 아닙니다. 이론적 배경은 숫자 이론적 방법에 근거하여 정확성에서 보여지고 입증되었습니다 [1]. 'matrix_multiply_test.py'파일은 기본적으로 내 메소드의 정확성을 실제로 입증하는 단위 테스트 파일입니다. 그러나이 방법은 양수 정수에 대해서만 설계 및 테스트되었으며, 이는 음의 정수, 부동 수 및 복소수의 경우에도 적절하게 수정 될 수 있습니다. 알고리즘의 실제 구현은 'matrix_multiply_quadratic.py'파일로 표시되었습니다. 이 모든 것과 함께, 나는 셀룰러 오토 마톤의 정말 좋은 예인 멀티 스레딩 기반 구현을 포함시켰다. CA 기반 구현의 테스트 된 버전은 'camatrix_mult_test.py'에 나와 있습니다. 시간 복잡성 분석은 'camatrix_mult.py'에 나와 있습니다.
[1] S. Mohapatra, "정수 매트릭스 곱셈을 최적화하는 컨볼 루션 숫자 이론 방법", [Arxiv : 1806.03701], 2018
[2] V. Strassen, "가우스 제거는 최적이 아닙니다", 숫자. 수학. 13, p. 354-356, 1969
[3] D. Bini, M. Capovani, F. Romani 및 G. Lotti. "O (n^2.7799) N × N 근사 행렬 곱셈에 대한 복잡성"Inf. 프로세스. Lett., pp. 234–235, 1979
[4] V. Strassen, "텐서의 점근 스펙트럼 및 행렬 곱셈의 지수", Proc. 27 번째 앤. IEEE SYMP. 컴퓨터 과학의 기초, pp. 49-54, 1984
[5] D. Coppersmith, S. Winograd, "산술 진행을 통한 매트릭스 곱셈". J. 상징적 컴퓨터. pp. 251–280, 1980
[6] V. Williams, "Coppersmith-Winograd보다 매트릭스를 더 빨리 곱합니다". ACM : pp.887–898, 2012
[7] F. Le Gall, "텐서의 힘과 빠른 매트릭스 곱셈", Proc. 39 번째 int. 증상. 기호 및 대수 계산, 2014
