Pregunta:
¿Existe algún procedimiento o teoría establecida para generar código que aplique eficientemente una multiplicación matriz-vector, cuando la matriz es densa y está llena de ceros y unos? Idealmente, el código optimizado haría un uso sistemático de la información previamente calculada para reducir el trabajo duplicado.
En otras palabras, tengo una matriz y quiero hacer una precomputación basada en , que hará que calcular más eficiente posible cuando más tarde reciba el vector v .
es una matriz binaria densa rectangular que se conoce en "tiempo de compilación", mientras que es un vector real desconocido que solo se conoce en "tiempo de ejecución".
Ejemplo 1: (ventana deslizante)
Permítanme usar un pequeño ejemplo fácil para ilustrar mi punto. Considere la matriz,
Hacer una multiplicación estándar de matriz-vector se calculará exactamente de esta manera. Sin embargo, mucho de este trabajo es redundante. Podríamos hacer el mismo cálculo matricial a menor costo haciendo un seguimiento de un "total acumulado " y sumando / restando para obtener el siguiente número:
Ejemplo 2: (estructura jerárquica)
En el ejemplo anterior, podríamos hacer un seguimiento de un total acumulado. Sin embargo, generalmente uno necesitaría crear y almacenar un árbol de resultados intermedios. Por ejemplo, considere
- Calcule y , y agréguelos para obtener .
- Calcule y , y agréguelos para obtener .
- Agregue y para obtenerw 3 w 1
La estructura en los ejemplos anteriores es fácil de ver, pero para las matrices reales que me interesan, la estructura no es tan simple.
Ejemplo 3: (rango bajo)
Para aclarar alguna confusión, las matrices generalmente no son escasas. Específicamente, un método para resolver este problema debe ser capaz de encontrar métodos eficientes para aplicar matrices donde los bloques grandes estén llenos de unos. Por ejemplo, considere
Esta matriz se puede descomponer como una diferencia de dos matrices de rango 1,
por lo tanto, su acción en un vector se puede calcular de manera eficiente,
Motivación:
Estoy trabajando en un método numérico para el procesamiento de algunas imágenes, y hay varias matrices grandes y densas con diferentes estructuras que se arreglan para siempre. Más tarde, estas matrices deberán aplicarse a muchos vectores desconocidos que dependerán de la entrada del usuario. En este momento estoy usando lápiz y papel para crear un código eficiente por matriz, pero me pregunto si el proceso puede automatizarse.v i
Editar: (postdata)
Todas las respuestas aquí hasta ahora (hasta el 5/9/15) son interesantes, pero ninguna responde a la pregunta tan satisfactoriamente como esperaba. Probablemente resulta que esta es una pregunta de investigación difícil, y nadie sabe una buena respuesta.
Desde que se acabó el tiempo, estoy otorgando la recompensa a la respuesta de EvilJS, ya que aborda la pregunta correcta. Sin embargo, deseo que la respuesta contenga explicaciones más claras y detalladas.
La respuesta de tranisstor establece una conexión entre esta pregunta y el problema de la Boolean Matrix-Vector Multiplication (OMv) en línea, pero la conexión no es exactamente lo que esta pregunta hace. En particular, la siguiente suposición realmente no encaja (el énfasis es mío),
Ahora suponga que para todas las y todas las matrices n × conocemos un algoritmo , que para todos los vectores calcula en un tiempo verdaderamente subcuadrático, es decir, en el tiempo para algunos . v M v O ( n 2 - ε ) ε > 0
Que existan o no algoritmos subcuadráticos para todas las matrices es ortogonal a la cuestión de encontrar un algoritmo para una matriz específica que sea lo más rápido posible. La mayoría de las matrices 0-1 parecen ruido aleatorio y (si tuviera que adivinar) probablemente no tienen algoritmos subcuadráticos. Sin embargo, el hecho de que haya matrices realmente malas no me impide encontrar un algoritmo rápido en una buena matriz, por ejemplo, una matriz de "ventana deslizante".
Las respuestas de vzn, primera respuesta , segunda respuesta son interesantes (y en mi opinión no merecen tantos votos negativos), pero no se aplican a la pregunta por las razones discutidas en los comentarios allí.
fuente
Respuestas:
Si es posible, trate de explotar la naturaleza tridiagonal en bandas de la matriz.
De lo contrario, si la matriz contiene solo un número constante de valores distintos (que seguramente es binario), debe probar el algoritmo Mailman (por Edo Liberty, Steven W. Zucker en el informe técnico de la Universidad de Yale # 1402): optimizado en un diccionario finito
Common Subexpression Elimination se conoce desde hace algún tiempo como Multiplicación constante constante, pero bajar al nivel de puerta es una opción: los patrones utilizados aquí podrían usarse por separado como solución o fusionarse con otros métodos, el documento para este "Mejora de la eliminación de subexpresión común Algoritmo con un nuevo método de cálculo de retardo a nivel de puerta "por Ning Wu, Xiaoqiang Zhang, Yunfei Ye y Lidong Lan publicado en" Actas del Congreso Mundial sobre Ingeniería y Ciencias de la Computación 2013 Vol II WCECS 2013, 23-25 de octubre de 2013, San Francisco, EE. UU. " Gate level CSE
También hay un método tosco pero de trabajo, para generar una matriz simbólica con constantes, un vector con variables y conectarlo a una evaluación estática simple (SSA) desde compiladores, que automatiza el proceso de escribir matrices a mano.
nuevo prototipo de algoritmo
Lo que hizo con la suma de ejecución: Da 10 operaciones , y con mi idea inicial de usar Thomas es equivalente. Por ahora todavía estoy escribiendo y probando un nuevo algoritmo, también los tiempos de ejecución son desagradables , pero el primer resultado de la prueba me dio una respuesta sorprendente:
que proporciona 9 operaciones , definiéndolas como + o - es 1 y = es 0.
Esto da 7 operaciones , el resultado de mi algoritmo dio: Lo que da 6 operaciones Por ahora puedo decir que estoy usando la distancia de Hamming, & y | operaciones bit a bit, contando usos y haciendo algo como Cocke – Younger – Kasami (CYK) - "un algoritmo de análisis para gramáticas libres de contexto, llamado así por sus inventores, John Cocke, Daniel Younger y Tadao Kasami. Emplea análisis dinámico y de abajo hacia arriba programación." - de Wikipedia Esta es la misma técnica que uso para construir bloques de variables.
fuente
Esto está relacionado con una pregunta de investigación abierta, que se conoce como el "problema de la matriz de vectores booleanos en línea (OMv)". Este problema es el siguiente (ver [1]): Dado un binario matriz M y n vectores columna binarios v 1 , ... , v n , tenemos que calcular M v i antes de v i + 1 llega.n×n M n v1,…,vn Mvi vi+1
Observe que el problema de la pregunta es algo más general: permite matrices y vectores con valores reales. Observe que el problema con n × n matrices y vectores booleanos es "más fácil", ya que presenta un caso especial.m×n n×n
Claramente, el algoritmo ingenuo para el problema en línea de la matriz de vectores de matriz booleana (que solo usa la matriz de multiplicación de vectores estándar) lleva tiempo . Hay una conjetura (ver, por ejemplo, [1]) que esto no puede hacerse realmente más rápido que O ( n 3 ) . (Con más detalle, esta conjetura es la siguiente: no existe un algoritmo realmente subcúbico, que resuelva el problema de multiplicación de matrices booleanas en línea, es decir, no existe un algoritmo con tiempo de ejecución O ( n 3 - ε ) para ε > 0 ).O(n3) O(n3) O(n3−ε) ε>0
Se sabe que el algoritmo de Williams resuelve este problema en el tiempo . Ver [2] para más detalles.O(n3/log2n)
Sería un gran avance en el área de los límites inferiores condicionales, si se pudiera probar o refutar la conjetura anterior.
[1] Unificación y fortalecimiento de la dureza para problemas dinámicos a través de una conjetura de matriz de vectores en línea. por Henzinger, Krinninger, Nanongkai y Saranurak
[ http://eprints.cs.univie.ac.at/4351/1/OMv_conjecture.pdf ]
[2] Multiplicación matricial-vectorial en tiempo subcuadrático: (se requiere preprocesamiento). por Williams
[ http://dl.acm.org/citation.cfm?id=1283383.1283490 ]
Actualizar
Una de las preguntas en los comentarios fue la siguiente: Conocemos en tiempo de compilación. ¿No podemos ajustar nuestro algoritmo para adaptarlo a M , por lo que el problema OMV (conjetura) no se aplica? Veremos que este no es el caso, a menos que la conjetura de OMv falle.M M
La idea de la prueba es simple: suponga que podríamos dar algoritmos rápidos para todas las matrices de hasta cierto tamaño (por ejemplo, distinguir todos los casos posibles). Después de este cierto tamaño usamos divide y vencerás.
Aquí están los detalles:n0∈N n≤n0 n×n M An,M v Mv O(n2−ε) ε>0 . (Tenga en cuenta que esto permite un algoritmo individual para cada matriz hasta un tamaño ).n0×n0
Arregle algunos , que (sin pérdida de generalidad) es una potencia de 2 y mayor que 2. Ahora suponga que para todas las matrices n ≤ n 0 y todas las n × n M conocemos un algoritmo A n , M , que para todos los vectores v calcula M v en un tiempo verdaderamente subcuadrático, es decir, en el tiempo O ( n 2 - ε ) para algunos ε > 0
Ahora resolveremos OMv en un tiempo verdaderamente subcúbico:M n×n n=2k k n>n0 M M1,M2,M3,M4 2k−1×2k−1 , entonces usamos el algoritmo A 2 k - 1 , M i , de lo contrario, recurrimos. (Como n 0 es un número fijo, podemos elegir el algoritmo correcto en tiempo constante).2k−1≤n0 A2k−1,Mi n0
dada una matriz binaria de tamaño n × n , donde n = 2 k para algunos k y n > n 0 , usamos una estrategia de dividir y conquistar. Dividimos M en cuatro submatrices M 1 , M 2 , M 3 , M 4 de tamaños 2 k - 1 × 2 k - 1 . Si 2 k - 1
Tenga en cuenta que necesitaremos como máximo pasos de recursión. Además, para n vectores v 1 , ... , v n , haremos n cálculos. Por lo tanto, para procesar todas las multiplicaciones de vectores de matriz necesitaremos un tiempo de cálculo total de O ( n 3 - ε log n ) .O(logn) n v1,…,vn n O(n3−εlogn)
Es bien sabido que el logaritmo crece más lentamente que cualquier polinomio (en particular, más lento que cualquier raíz). Al fijar algunos con ˜ ε < ε , vemos que nuestro cálculo total se está ejecutando en un tiempo verdaderamente subcúbico (en particular, en el tiempo O ( n 3 - ˜ ε ) ). Por lo tanto, la conjetura de OMv estaría mal.ε~>0 ε~<ε O(n3−ε~)
(Si tiene el tamaño m × n y m y n no son potencias de 2, entonces los límites en los tiempos de funcionamiento siguen siendo válidas, ya que podíamos aumentar n y m a las próximas potencias de 2.)M m×n m n n m
Conclusión: Si pudiera hacer uso de distinciones de casos en las matrices de entrada para derivar algoritmos rápidos, entonces podría mejorar la conjetura de OMv.
fuente
esto es esencialmente CS a nivel de investigación, el problema se estudia al menos en dos formas, una de multiplicación de matrices dispersas (ejemplo de papel recién citado), y también se estudia el caso especial de "matrices dispersas binarias". el 2 nd caso se sabe que está relacionada con la optimización de programas de línea recta. los programas mínimos también pueden ser como DAG con dos tipos de "compuertas", suma y multiplicación, por lo que parte de la literatura sobre minimización de circuitos puede conectarse con esto, y posiblemente el software "listo para usar" podría adaptarse para este propósito. aquí es una referencia específica en el 2 nd caso y también la misma pregunta en cstheory con algún estudio empírico inicial básica.
Representando matrices binarias dispersas como programas de línea recta para multiplicación rápida de vectores de matriz / Neves, Araujo
Producto de cadena de matriz booleana dispersa rápida / teoría
fuente
No estoy seguro si este problema se ha estudiado exactamente, pero esta investigación está relacionada y parece una ventaja / inicio razonable. observa la descomposición de la hipergrafía para una multiplicación de matriz dispersa. Las matrices binarias son un caso especial de este enfoque. Este enfoque encontrará estrategias más óptimas que el método de multiplicación "directa". Es posible que se realicen más optimizaciones (dentro de este marco) en función de la propiedad de matriz binaria.
fuente