Requisito de memória para multiplicação rápida de matrizes

Suponha que desejamos multiplicar matrizes. O algoritmo de multiplicação de matriz lenta é executado no tempo O ( n 3 ) e usa memória O ( n 2 ) . A multiplicação mais rápida da matriz ocorre no tempo n ω + o ( 1 ) , onde ω é a álgebra linear constante, mas o que se sabe sobre sua complexidade de memória?$n \times n$$O(n^3)$$O(n^2)$$n^{\omega + o(1)}$$\omega$

Parece que é possível a priori que a rápida multiplicação de matrizes consuma memória. Existe alguma garantia de que isso possa ser feito na memória O ( n 2 ) ? É o caso de os algoritmos de multiplicação de matriz atualmente conhecidos usarem memória O ( n 2 ) ?$n^{\omega}$$O(n^2)$$O(n^2)$

(Na verdade, estou interessado na multiplicação de matrizes retangulares, mas presumo que a resposta seja a mesma nesse caso que no caso quadrado e o caso quadrado seja melhor estudado.)

O uso de espaço é no máximo para todos os algoritmos do tipo Strassen (ou seja, aqueles baseados no limite superior do ranking de multiplicação de matrizes algebricamente). Consulte Complexidade espacial do algoritmo Coppersmith – Winograd$O(n^2)$

No entanto, percebi na minha resposta anterior que não expliquei por que o uso do espaço é ... então aqui vai algo ondulado à mão. Considere o que um algoritmo do tipo Strassen faz. Começa a partir de um algoritmo fixo para K × K matriz de multiplicação que usa K c multiplicações para alguma constante c < 3 . Em particular, esse algoritmo (seja ele qual for) pode ser escrito no WLOG para que:$O(n^2)$$K \times K$$K^c$$c < 3$

1. Ele calcula diferentes matrizes L 1 , … , L K c que multiplicam as entradas da primeira matriz A por vários escalares e K c matrizes R 1 , … , R K c da segunda matriz B de uma forma semelhante,$K^c$$L_1,\ldots,L_{K^c}$$A$$K^c$$R_1,\ldots,R_{K^c}$$B$

2. Multiplica essas combinações lineares , em seguida,$L_i \cdot R_i$

3. Multiplica entradas de por vários escalares, em seguida, adiciona todas essas matrizes acima entrywise obter Um ⋅ B .$L_i \cdot R_i$$A \cdot B$

(Esse é um algoritmo chamado "bilinear", mas acontece que todo algoritmo de multiplicação de matrizes "algébrico" pode ser escrito dessa maneira.) Para cada , esse algoritmo precisa apenas armazenar o produto atual L i ⋅ R i e o valor atual de A ⋅ B (inicialmente definido como todos os zeros) na memória em um determinado ponto, portanto, o uso do espaço é O ( K 2 ) .$i=1,\ldots,K^c$$L_i \cdot R_i$$A \cdot B$$O(K^2)$

Dado este algoritmo finito, isto é, em seguida, estendida para arbitrária matrizes, por quebrar as grandes matrizes em K × K blocos de dimensões K ℓ - 1 × K l - 1 , aplicando-se o finito K × K algoritmo para o bloco matrizes e chamando recursivamente o algoritmo sempre que precisar multiplicar dois blocos. Em cada nível de recursão, precisamos manter apenas os elementos do campo O ( K 2 ℓ ) na memória (armazenando O ( 1 $K^{\ell} \times K^{\ell}$$K \times K$$K^{\ell-1}\times K^{\ell-1}$$K \times K$$O(K^{2\ell})$$O(1)$diferente matrizes). Supondo que o uso de espaço para a multiplicação da matriz K ℓ - 1 × K ℓ - 1 seja S ( ℓ - 1 ) , o uso de espaço desse algoritmo recursivo é S ( ℓ ) ≤ S ( ℓ - 1 ) + O ( K 2 ℓ ) , que para S ( 1 ) = 2 K $K^{\ell} \times K^{\ell}$$K^{\ell-1}\times K^{\ell-1}$$S(\ell-1)$$S(\ell) \leq S(\ell-1) + O(K^{2\ell})$$S(1) = 2K^2$resolve para .$S(\ell) \leq O(K^{2\ell})$

$p$$O(n^2/p)$