Multiplicación de Matrices: La importancia de un algoritmo.

Cuando explicamos la importancia y la usabilidad que tienen las matemáticas en la vida real muchas veces nos cuesta explicarlo o verbalizarlo, pero verdaderamente las matemáticas son realmente útiles en ámbitos más allá de los números y las ciencias.

Uno de los ejemplos ya no solo interesantes si no también muy importante debido a su relevancia en el mundo del algoritmo, son las matrices.

Las matrices es un concepto matemático muy relevante en ámbitos como los video juegos o actualmente en el mundo de la inteligencia artificial. Por ejemplo, todo lo que conlleva la gestión de imágenes depende en mayor o menor medida de las matrices.

Una matriz es un arreglo rectangular de números, que se representa en forma de tabla de filas y columnas. Cada elemento de la matriz se puede acceder mediante un par de índices, que indican la fila y la columna a la que corresponde.

En la inteligencia artificial, las matrices se utilizan en una amplia variedad de aplicaciones, tales como las redes neuronales donde las matrices se utilizan para representar los pesos de las conexiones entre las neuronas y para realizar cálculos durante el proceso de aprendizaje.

En el campo del procesamiento del lenguaje natural las matrices se pueden utilizar para representar vectores de palabras o frases y para realizar cálculos durante el procesamiento del lenguaje.

Como hemos mencionado anteriormente las matrices son una herramienta importante en el campo de la visión por computadora, ya que se utilizan para representar y manipular imágenes y vídeos digitales. Una imagen digital se puede representar como una matriz de puntos de datos, donde cada punto de datos se conoce como un «pixel». Los pixels se pueden ordenar en filas y columnas para formar la matriz. Cada pixel contiene información sobre el color y la luminosidad de un pequeño fragmento de la imagen, normalmente con valores entre 0 y 255

Las matrices también se utilizan en diversos algoritmos y técnicas de procesamiento de imágenes, como el filtrado, la transformación de imagen y la detección de características. Por ejemplo, se pueden utilizar matrices para aplicar filtros a una imagen para modificar su apariencia, como eliminar el ruido o enfatizar los bordes. También se pueden utilizar matrices para realizar transformaciones geométricas en imágenes, como rotaciones o deformaciones. Además, se pueden para detectar y extraer características específicas de una imagen, como bordes o patrones. Algo que utilizamos prácticamente a diario cuando “jugamos” con nuestras fotos en dispositivos móviles aplicando los llamados filtros en las RRSS.

En resumen, las matrices son una herramienta esencial en el campo de la visión por computadora y se utilizan en una amplia gama de aplicaciones y técnicas de procesamiento de imágenes.

Una vez que hemos contextualizado la importancia de las matrices, podemos entender la relevancia que puede tener el operar con este concepto matemático, exactamente en este articulo nos centraremos en la multiplicación de matrices que tal y como resaltaba el paper “Discovering faster matrix multiplication algorithms with reinforcement learning” publicado el 5 de octubre de 2022, es un aspecto de total actualidad y donde empresas como DeepMind (Google) trabajan en optimizar este algoritmo para mejorar su capacidad de cómputo y ejecución con matrices de dimensiones muy grandes. Hay que tener en cuenta que simplemente con gestionar imágenes de una resolución de 1024×1024 ya nos está haciendo trabajar con matrices de 1024 filas y 1024 columnas.

Es aquí donde nace la importancia de poder tener algoritmos eficaces y de baja complejidad para realizar este tipo de operaciones de una manera rápida y correcta. Actualmente el algoritmo tradicional que permite multiplicar matrices tiene una complejidad de N³ , siendo N la dimensión de nuestra matriz. El que esa dimensión esté elevada al cubo nos quiere indicar que su programación está basada en 3 bucles anidados, los cuales se van cerrando desde dentro hacia afuera.

Para entender el algoritmo de multiplicación de matrices hagamos una pequeña representación con dos matrices sencillas de dimensión 2×2

En programación podemos representarlo como

Como se puede observar el mínimo número de operaciones son 8 multiplicaciones y 4 sumas desplazándonos de manera vertical en un bucle, horizontal en el otro y finalmente realizar las operaciones y colocar el valor en el sitio correspondiente con el último bucle.

Esto implica un crecimiento polinomial n^3 según vaya aumentando las dimensiones de las matrices.

El algoritmo de multiplicación de matrices es algo que se lleva trabajando mucho tiempo y ya en 1969 se descubrió el algoritmo de Strassen , ideado por Volker Strassen y al que a menudo se hace referencia como «multiplicación rápida de matrices.

El algoritmo de Strassen es un algoritmo eficiente de multiplicación de matrices que permite multiplicar dos matrices en un tiempo n^2.807, en lugar del tiempo n^3 que lleva multiplicar dos matrices utilizando el algoritmo estándar de multiplicación de matrices, explicado anteriormente

Esta implementación utiliza llamadas a funciones recursivas para dividir las matrices en submatrices más pequeñas hasta que alcanzan un tamaño de 1×1, momento en el que se pueden multiplicar directamente. Luego, los valores intermedios se calculan mediante una serie de sumas y restas de matrices, y el resultado final se ensambla combinando los valores intermedios.

Para entender que es el concepto de recursividad en programación podéis leer el siguiente artículo. https://www.europeanvalley.es/noticias/entender-la-recursividad/

Sin entrar en muchos detalles complejos de las matemáticas simplemente podemos decir que la estructura del algoritmo de Strassen para dos matrices de 2×2, tal y como hemos puesto de ejemplo anteriormente, sería.

Lo cual se puede observar que nos ahorramos una multiplicación (Strassen = 7 multiplicaciones, frente al tradicional = 8 multiplicaciones), y es aquí la explicación de la bajada de complejidad anteriormente mencionada.

Comparamos ambos algoritmos

Con todos estos datos y sus explicaciones nos hace pensar que el algoritmo de Strassen será a priori mejor que el algoritmo tradicional, simplemente por observar su complejidad. Pero como estamos en un ámbito académico que mejor manera de enseñarlo y mostrar algo muy interesante en la eficacia de los algoritmos.

Se realiza una programación en Python de ambos algoritmos para comparar su tiempo de ejecución con la multiplicación de matrices de igual dimensión para ambos.

En nuestra primera prueba podemos observar que en matrices de hasta 128×128 el algoritmo tradicional es más eficaz que el algoritmo de Strassen.

Los tiempos de ejecución de Strassen son mayores, incluso aumentando cuando pasamos de 64 dimensiones a 128. ¿Por qué ocurre esto? ¿El algoritmo de Strassen no tenía una complejidad más baja?

Efectivamente es así, pero la cantidad de los datos también juega un papel importante en la capacidad de ejecución de los algoritmos, siendo relevante su eficacia cuando estos datos alcanzan un tamaño determinado. Por lo tanto, si realizamos el mismo experimento, pero en este caso aumentamos el número de dimensiones, se puede observar lo siguiente.

A partir de 512 dimensiones el algoritmo de Strassen empieza a ser mejor que el tradicional, aumentando su eficacia a medida que se aumenten las dimensiones.

Como conclusión podemos decir que la mejora de la complejidad en algoritmos tan importantes como este que acabamos de explicar no solo depende de la programación, si no también de conocer donde se encuentra su punto de inflexión en función a los datos utilizados.

Una interesante reflexión la cual podemos trabajar de manera educativa con una demostración no muy compleja.

Para la realización de la actividad os comparto la programación en Python del algoritmo de Strassen.