Le plus rapide de l'algorithme pour le calcul du déterminant d'une matrice?

Pour un document de recherche, j'ai été affecté à la recherche le plus rapide de l'algorithme pour le calcul du déterminant d'une matrice.

Je sais déjà à propos de la décomposition LU et Bareiss algorithme qui à la fois s'exécuter en O(n^3), mais après avoir fait quelques recherches, il semble que certains des algorithmes exécuter quelque part entre les n^2 et n^3.

Ce source (voir page 113-114) et ce source (voir page 198) dire qu'existe un algorithme qui s'exécute en O(n^2.376) parce qu'il est basé sur la Chaudronnerie-Winograd algorithme de multiplication de matrices. Cependant, je n'ai pas été en mesure de trouver tous les détails sur un tel algorithme.

Mes questions sont:

  1. Quelle est la manière la plus rapide de créer (non théorique) de l'algorithme pour le calcul du déterminant d'une matrice?
  2. Où puis-je trouver des informations sur le plus rapide de l'algorithme?

Merci beaucoup.

Quelle est la taille des matrices? Combien de déterminants voulez-vous calculer?
Je suppose que les matrices sont de très grande taille (N > 22 est probablement assez grand?). Et de combien? Juste le déterminant de la matrice donnée. Entrée: 1 Grande Matrice de Sortie: Le seul déterminant de la matrice d'entrée.
Est stabilité numérique également un sujet de préoccupation?
Il peut être intéressant d'enquêter sur la question et réponses sur Ladderman de multiplication, stackoverflow.com/q/10827209/249341
Désolé, je ne sais pas quoi Stabilité Numérique.

OriginalL'auteur johnluke.laue | 2014-11-18

  1. 5

    Je crois que la manière la plus rapide dans la pratique (et couramment utilisé) de l'algorithme est l'Algorithme de Strassen. Vous pouvez en trouver l'explication sur Wikipédia ainsi que des exemples de code C.

    Algorithmes basés sur Chaudronnerie-Winograd la multiplication des algorithmes sont trop complexes pour être pratiques, mais ils ont le meilleur complexité asymptotique aussi loin.

    Il est intéressant de noter que le courant est lié O(n^{2.3728639}) mais comme Sopel dit, il est peu probable que le plus petit exposant vaut la peine de poursuivre sur une pratique de calcul, car ils ont un énorme facteur constant de l'avant.
    Je crois Strassen est utilisé pour l'inversion de matrice. voir en.wikipedia.org/wiki/... Et comme pour les algorithmes à base de Coppersmith-Winograd, vous avez raison - j'ai demandé à mon professeur et il a dit qu'ils sont les plus rapides, mais sont trop complexes pour être pratique. Merci!!!!
    Je crois qu'ils sont des problèmes très similaires (je suis finales de Coppersmith-Winograd algorithme de multiplication de matrice peut être transformé pour calculer les déterminants), mais je n'ai pas de grandes connaissances à ce sujet donc j'ai peut-être tort.

    OriginalL'auteur Sopel

  2. 2

    Je sais que ce n'est pas une réponse directe, pour ma question, mais pour les besoins de la réalisation de mon mémoire de recherche, c'est suffisant.
    J'ai juste fini de demander à mon professeur et je vais résumer ce qu'il a dit:

    Résumé:

    • La manière la plus rapide de la matrice de la multiplication des algorithmes (par exemple, Chaudronnerie-Winograd et, plus récemment, des améliorations) peut être utilisé avec O(n^~2.376) opérations arithmétiques, mais de lourdes et des outils mathématiques sont souvent impraticables.
    • La Décomposition LU et Bareiss n'utiliser O(n^3) de l'exploitation, mais sont plus pratiques

    En bref, même si la Décomposition LU et Bareiss ne sont pas aussi rapide que la plupart des algorithmes efficaces, elles sont plus pratiques et je dois concentrer mon étude sur ces deux.

    Merci pour tous ceux qui ont commenté et aidé!

    C'est un nit, mais "la Décomposition LU et Bareiss ne sont pas aussi rapide" n'est pas vraiment correct. Ce que tu veux dire, c'est "la Décomposition LU et Bareiss ne sont pas aussi rapide asymptotiquement". Le asymptotiquement supérieure algorithmes ont une telle haute constantes dans la réalité de leur temps d'exécution des fonctions, que le "plus lent" les algorithmes sont plus rapides dans la pratique. Par exemple, 1e6*n est plus grand que 0.0001*n^2 pour tout n < 1e5.

    OriginalL'auteur johnluke.laue

  3. 0

    Voir la suite de Matlab script de test, qui calcule les déterminants de l'arbitraire des matrices carrées (les comparaisons avec Matlab la fonction intégrée est également inclus):

    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(' ');

    OriginalL'auteur vnormi75