El uso del espacio es como máximo para todos los algoritmos similares a Strassen (es decir, aquellos basados en el límite superior del rango de multiplicación de la matriz algebraicamente). Ver Complejidad espacial del algoritmo Coppersmith – WinogradO ( n2)
Sin embargo, me di cuenta en mi respuesta anterior que no explicaba por qué el uso del espacio es ... así que aquí va algo ondulado. Considere lo que hace un algoritmo similar a Strassen. Comienza a partir de un algoritmo fijo para la multiplicación de matrices K × K que utiliza multiplicaciones de K c para alguna constante c < 3 . En particular, este algoritmo (sea lo que sea) se puede escribir WLOG para que:O ( n2)K× KKCc < 3
Calcula diferentes matrices L 1 , ... , L K c que multiplican las entradas de la primera matriz A por varios escalares y K c matrices R 1 , ... , R K c de la segunda matriz B de una forma similar,KCL1, ... , LKCUNKCR1,…,RKcB
Multiplica esas combinaciones lineales , entoncesLi⋅Ri
Se multiplica las entradas de por diversos escalares, entonces agrega todas estas matrices hasta entrywise para obtener A ⋅ B .Li⋅RiA⋅B
(Este es un algoritmo llamado "bilineal", pero resulta que cada algoritmo de multiplicación matricial "algebraico" se puede escribir de esta manera.) Para cada , este algoritmo solo tiene que almacenar el producto actual L i ⋅ R i y el valor actual de A ⋅ B (inicialmente establecido en todos los ceros) en la memoria en cualquier punto dado, por lo que el uso del espacio es O ( K 2 ) .i=1,…,KcLi⋅RiA⋅BO(K2)
Dado este algoritmo finito, se extiende a las matrices arbitrarias , al dividir las matrices grandes en bloques K × K de dimensiones K ℓ - 1 × K ℓ - 1 , aplicando el algoritmo K × K finito al bloque matrices, y recursivamente llamando al algoritmo cada vez que necesita multiplicar dos bloques. En cada nivel de recursión, necesitamos mantener solo elementos de campo O ( K 2 ℓ ) en la memoria (almacenar O ( 1 )Kℓ×KℓK×KKℓ−1×Kℓ−1K×KO(K2ℓ)O(1)diferentes matrices ). Suponiendo que el uso de espacio para K ℓ - 1 × K ℓ - 1 multiplicación de matriz es S ( ℓ - 1 ) , el uso de espacio de este algoritmo recursivo es S ( ℓ ) ≤ S ( ℓ - 1 ) + O ( K 2 ℓ ) , que para S ( 1 ) = 2 K 2Kℓ×KℓKℓ−1×Kℓ−1S(ℓ−1)S(ℓ)≤S(ℓ−1)+O(K2ℓ)S(1)=2K2resuelve a .S(ℓ)≤O(K2ℓ)
fuente