Abbiamo una matrice con elementi nel campo degli interi modulo 2 (F_2). Stiamo cercando algoritmi che moltiplicano n x n matrix su F_2 nel giusto O(n^2.81/(log n)^0.4)
Com'è possibile?
Lo so, l'algoritmo di Strassen dà O(n^2.81), ma come possiamo ottenere questo fattore (log n)^0.4?
risposte:
4 per risposta № 1Puoi fare quanto segue:
Prendi ciascuna matrice possibile con le dimensioni 
. Ci sono 
tali matrici (
).
Precarica il risultato della moltiplicazione per queste matrici. Questo ti dà una tabella con le dimensioni 
. Quindi, nella fase di ricorsione dell'algoritmo Strassen, se le matrici richieste per la moltiplicazione sono abbastanza piccole, è possibile utilizzare i valori precalcolati in questa tabella (se inferiore a 
potresti riempire righe e colonne appropriate con zeri). Permettere 
. Quindi hai seguito la ricorsione:
Si noti che la profondità di ricorrenza è 
, quindi hai:
Usando la formula delle serie geometriche:
