¿Cómo cambiaría la industria del software si se descubre un algoritmo que lleva a cabo la multiplicación matricial con una complejidad de O (n ^ 2)?

Answer 1

Honestamente, no cambiaría tanto, porque un algoritmo elegante [matemático] O (n ^ 2) [/ matemático] probablemente sería más lento en la vida real que el ingenuo [matemático] O (n ^ 3) [/ matemático] algoritmo. (Al menos a juzgar por los intentos de otras personas para resolver este problema).

[math] O (n ^ 2) [/ math] solo significa que para matrices [math] n [/ math] suficientemente grandes, dos matrices [math] n [/ math] -by- [math] n [/ math] pueden ser multiplicado en [math] \ leq cn ^ 2 [/ math] tiempo, por alguna constante [math] c [/ math] que no depende de las matrices específicas. [matemática] O (n ^ 3) [/ matemática] significa lo mismo, pero por [matemática] cn ^ 3 [/ matemática] tiempo. El problema es que [math] c [/ math] en el algoritmo [math] O (n ^ 2) [/ math] probablemente sería mucho más alto que el [math] c [/ math] en el [math] O ( n ^ 3) [/ math] algoritmo, por lo que el algoritmo ingenuo ganaría en entradas de tamaño normal.

Para ilustrar, suponga que c = 1 para el algoritmo [matemático] O (n ^ 3) [/ matemático] y c = 1 millón para el algoritmo [matemático] O (n ^ 2) [/ matemático]. Luego, para matrices de 100 por 100, el algoritmo [math] O (n ^ 3) [/ math] está garantizado para ejecutarse en [math] \ leq 10 ^ 6 [/ math] tiempo, mientras que el [math] O ( n ^ 2) El algoritmo [/ math] está garantizado para ejecutarse en [math] \ leq 10 ^ {10} [/ math]. Entonces, el algoritmo [matemático] O (n ^ 2) [/ matemático] es más lento, hasta que comienzas a multiplicar matrices de 1 millón por 1 millón, y luego comienza el algoritmo [matemático] O (n ^ 3) [/ matemático] victorioso.

Answer 2

Hay un algoritmo para esto. Se llama algoritmo de Freivalds – Wikipedia

El principal problema con la multiplicación de matrices grandes no es la complejidad del tiempo, es el tamaño de la matriz. La codificación física de las matrices significa que necesita distribuir el proceso y hacerlo especialmente. Porque una computadora estándar no puede contener matrices grandes. Derecha.

Para ilustrar esto.

[matemática] \ matemática {0} (n ^ {3}) [/ matemática] para 1 millón x 1 millón que es [matemática] 10 ^ {18} [/ matemática]

flops bien mi computadora hace 80 giga flops. O 8.0 [matemáticas] * 10 ^ {9} [/ matemáticas]

Entonces eso llevaría mucho tiempo. La computadora no acepta este tamaño de matriz o comienza a formarse y su memoria llegará al 80% y se detendrá. Porque eso es 8 terabytes. Está tratando de seguir construyéndolo y va a fallar. Siendo realistas, esta matriz debe dividirse y aprobarse. Hay mejores formas de usar GPU para operaciones con muchos subprocesos.