매트릭스의 행렬식을 계산하는 가장 빠른 알고리즘?

Question

연구 논문의 경우 행렬의 행렬식을 계산하는 가장 빠른 알고리즘을 연구하도록 지정되었습니다.

는 이미^(N^3)하지만 뒷조사를하고 후,이 곳 N 사이의 실행^2 n은 어떤 알고리즘이있는 것 같다 O에있는 모두 실행에 대한 LU 분해 및 Bareiss 알고리즘을 알고 삼.

이 source (113-114 페이지 참조) 및 source (198 페이지 참조)은 Coppersmith-Winograd의 행렬 곱셈 알고리즘을 기반으로하기 때문에 O (n^2.376)에서 실행되는 알고리즘이 있다고합니다. 그러나, 나는 그런 알고리즘에 대한 세부 사항을 찾을 수 없었습니다.

내 질문은 :

1. 행렬의 행렬식을 계산하는 가장 빠른 생성 (비 이론적 인) 알고리즘은 무엇입니까?
2. 가장 빠른 알고리즘에 대한 정보는 어디에서 찾을 수 있습니까?

감사합니다.

Answer 1

실용적인 (그리고 일반적으로 사용되는) 알고리즘은 Strassen 알고리즘이라고 생각합니다. 샘플 C 코드와 함께 Wikipedia에 대한 설명을 찾을 수 있습니다.

Coppersmith-Winograd's multiplication algorithms을 기반으로 한 알고리즘은 너무 복잡하여 실용적이지 못하지만 실제로는 최대한의 점근 적 복잡성이 있습니다.

Answer 2

제 질문에 대한 직접적인 답변이 아니라는 것을 알고 있습니다 만, 제 연구 논문을 완성하기에 충분합니다. 난 그냥 내 교수를 물어 결국 나는 그가 말한 것을 요약한다 :

이

요약 :

• 가장 빠른 행렬 곱셈 알고리즘 (예를 들어, 구리 세공인 - Winograd와 최근의 개선이) O와 함께 사용할 수 있습니다 (n^~ 2.376) 산술 연산이지만, 무거운 수학 도구를 사용하고 종종 비실용적입니다.
• LU 분해 및 Bareiss가 LU 분해 및 Bareiss 최대한 빨리 가장 효율적인 알고리즘과 같은하지 않더라도, (N^3) 작업 O를 사용하여 수행하지만, 요컨대

보다 실용적이며, 그들은 더 실용적 나는이 두 논문에 초점을 맞추어야한다.

의견을 말하고 도움을 준 모든 분들께 감사드립니다.

Answer 3

임의의 정사각형 행렬의 결정 계산 다음 matlab에 테스트 스크립트 참조 (matlab에 내장 된 기능에 대한 비교도 포함되어 있습니다) :

nMin = 2; % Start with 2-by-2 matrices 
nMax = 50; % Quit with 50-by-50 matrices 
nTests = 10000; 
detsOfL = NaN*zeros(nTests, nMax - nMin + 1); 
detsOfA = NaN*zeros(nTests, nMax - nMin + 1); 
disp(' '); 
for n = nMin:nMax 
    tStart = tic; 
    for j = 1:nTests 
     A = randn(n, n); 
     detA1 = det(A); % Matlab's built-in function 
     if n == 1 
      detsOfL(j, 1) = 1; 
      detsOfA(j, 1) = A; 
      continue; % Trivial case => Quick return 
     end 
     [L, U, P] = lu(A); 
     PtL = P'*L; 
     realEigenvaluesOfPtL = real(eig(PtL)); 
     if min(prod(realEigenvaluesOfPtL)) < 0 % det(L) is always +1 or -1 
      detL = -1; 
     else 
      detL = 1; 
     end 
     detU = prod(diag(U)); 
     detA2 = detL * detU; % Determinant of A using LU decomposition 
     if detA1 ~= detA2 
      error(['Determinant computation failed at n = ' num2str(n) ', j = ' num2str(j)]); 
     end 
     detsOfL(j, n - nMin + 1) = detL; 
     detsOfA(j, n - nMin + 1) = detA2; 
    end 
    tElapsed = toc(tStart); 
    disp(sprintf('Determinant computation was successful for n = %d!! Elapsed time was %.3f seconds', n, tElapsed)); 
end 
disp(' ');