Definición de exponente de multiplicación matricial

15

Coloquialmente, la definición del exponente de multiplicación de matrices es el valor más pequeño para el cual existe un algoritmo de multiplicación de matrices conocido . Esto no es aceptable como una definición matemática formal, por lo que supongo que la definición técnica es algo así como el infimum sobre todo tal que existe un algoritmo de multiplicación de matrices en . $\omega$ $n^{\omega}$ $t$ $n^t$

En este caso, no podemos decir que hay un algoritmo para la multiplicación de matrices en o incluso , simplemente que para todo existe un algoritmo en . Sin embargo, a menudo, los documentos y resultados que utilizan la multiplicación de matrices informarán su costo simplemente como . $n^{\omega}$ $n^{\omega + o(1)}$ $\epsilon > 0$ $n^{\omega + \epsilon}$ $O(n^{\omega})$

¿Existe alguna definición alternativa de que permita este uso? ¿Hay resultados que garanticen que debe existir un algoritmo de tiempo o ? ¿O es el uso simplemente descuidado? $\omega$ $n^{\omega}$ $n^{\omega + o(1)}$ $O(n^{\omega})$

ds.algorithms linear-algebra David Harris
fuente

2

Si solo quiere usar la multiplicación de matrices como un recuadro negro, la forma más fácil es decir "Sea

ω

$\omega$ tal que podamos multiplicar

n \times n

$n \times n$ -matrices con operaciones aritméticas

O (n^{ω})

$O(n^\omega)$ ". Por supuesto,

ω

$\omega$ no es el exponente de la multiplicación de matrices entonces, pero puede ser arbitrariamente cercano. Si desea establecer el exponente de su ejecución final en representación decimal, actualmente debe redondear de todos modos, ya que todas las estimaciones no triviales para

ω

$\omega$ que conozco son números irracionales o secuencias infinitas.

Markus Bläser

2

ω

$\omega$ se define típicamente como el infimum sobre todos los reales

k

$k$ para

n

$n$ yendo a

\infty

$\infty$ tal manera que haya unalgoritmo de tiempo

O (n^{k})

$O(n^k)$ que multiplique dosmatrices

n \times n

$n\times n$ (donde el tiempo es el número de sumas, multiplicaciones y divisiones en el campo subyacente). Esto también significa que técnicamente siempre deberíamos escribir

n^{ω + o (1)}

$n^{\omega+o(1)}$ pero eso se vuelve desordenado, por lo que cuando veas

O (n^{ω})

$O(n^\omega)$ deberías pensar

donde

es el tiempo de ejecución de un algoritmo de multiplicación de matrices.

O (M (n))

$O(M(n))$

M (n)

$M(n)$

virgi

20

El exponente de multiplicación matricial siendo no garantiza que haya un algoritmo que se ejecute en el tiempo , sino que solo para cada , hay un algoritmo que se ejecuta en . De hecho, si puede encontrar un algoritmo que se ejecute en el tiempo , esto muestra que . $\omega$ $O(n^\omega)$ $\epsilon > 0$ $O(n^{\omega+\epsilon})$ $O(n^2 \mathrm{polylog}(n))$ $\omega = 2$

Puede encontrar la definición formal en el libro Teoría de la complejidad algebraica de Peter Bürgisser, Michael Clausen, Amin Shokrollahi.

MCH
fuente

7

Un comentario menor que es demasiado largo para ser un comentario:

A veces, cuando tiene un problema para el cual hay un algoritmo con tiempo de ejecución para cada , hay un algoritmo con tiempo de ejecución . $O(n^{k+\epsilon})$ $\epsilon>0$ $n^{k+o(1)}$

Por ejemplo, a veces obtienes algoritmos que van como para alguna función de crecimiento rápido (como ). Si establece en (digamos) , entonces será o (1). En el ejemplo con siendo , puede elegir $f(1/\epsilon)n^{k+\epsilon}$ $f$ $2^{2^{1/\epsilon}}$ $f(1/\epsilon)$ $\log n$ $\epsilon$ $f(1/\epsilon)$ $2^{2^{1/\epsilon}}$ $1/\epsilon$ ser , que da , que es o (1). Entonces, el tiempo de ejecución final de este algoritmo será , ya que también es . $\log \log \log n$ $\epsilon = 1/ (\log \log \log n)$ $n^{k+o(1)}$ $\log n$ $n^{o(1)}$

Robin Kothari
fuente

Me imagino que el algoritmo Coppersmith-Winograd entra en esta categoría.

David Harris

2

@DavidHarris: No sé sobre eso. Quizás alguien que entienda el algoritmo pueda arrojar algo de luz sobre eso. Solo quería decir que a menudo

no es tan malo como parece.

O (n^{k + ϵ})

$O(n^{k+\epsilon})$

Robin Kothari

5

Es bien sabido el resultado de Coppersmith y Winograd que el tiempo no puede ser realizado por un solo algoritmo. Pero he leído que se restringieron a algoritmos basados en identidades bilineales similares a Strassen, por lo que no estoy seguro ya que el documento está detrás de un muro de pago. $O(n^{\omega})$

Diego de Estrada
fuente

3

No estoy de acuerdo con su afirmación en la pregunta de que no está bien definido por "el valor más pequeño para el cual existe un algoritmo de multiplicación de matriz conocido ". Cuando las personas usan esta constante, es porque su algoritmo se basa en una multiplicación de matriz, y por una complejidad , significan que "la complejidad óptima de nuestro algoritmo viene dada por el algoritmo óptimo para la multiplicación de matriz". $\omega$ $n^ω$ $n^\omega$

No digo que no sea posible definir otra manera (por ejemplo, decir que es la mejor complejidad posible). $\omega$ $\omega$

Por cierto, el límite superior más conocido para la multiplicación de matrices acaba de mejorar a si no me equivoco. $2.3737$

Bruno
fuente

3

No veo cómo el conocimiento humano puede ser parte de una definición matemática

David Harris

2

La experiencia reciente muestra que es mucho más fácil cuantificar sobre todos los algoritmos que sobre todos los algoritmos conocidos actualmente por la humanidad ;-)

Markus Bläser

Definición de exponente de multiplicación matricial

Respuestas: