Programación de matrices

En informática, la programación matricial se refiere a soluciones que permiten la aplicación de operaciones a un conjunto completo de valores a la vez. Estas soluciones se utilizan comúnmente en entornos científicos y de ingeniería.

Los lenguajes de programación modernos que admiten la programación de matrices (también conocidos como lenguajes vectoriales o multidimensionales) han sido diseñados específicamente para generalizar operaciones sobre escalares para aplicarlas de forma transparente a vectores, matrices y matrices de dimensiones superiores. Entre ellos se incluyen APL, J, Fortran, MATLAB, Analytica, Octave, R, Cilk Plus, Julia y Perl Data Language (PDL). En estos lenguajes, una operación que opera sobre matrices enteras puede denominarse operación vectorizada, independientemente de si se ejecuta en un procesador vectorial, que implementa instrucciones vectoriales. Las primitivas de programación de matrices expresan de forma concisa ideas generales sobre la manipulación de datos. El nivel de concisión puede ser espectacular en ciertos casos: no es raro encontrar lenguajes de programación de matrices con una sola línea que requieren varias páginas de código orientado a objetos.

Conceptos de matriz

La idea fundamental detrás de la programación de matrices es que las operaciones se aplican de inmediato a un conjunto completo de valores. Esto la convierte en un modelo de programación de alto nivel, ya que permite al programador pensar y operar sobre agregados completos de datos, sin tener que recurrir a bucles explícitos de operaciones escalares individuales.

Kenneth E. Iverson describió la lógica detrás de la programación de matrices (en realidad, se refería a APL) de la siguiente manera:

la mayoría de los lenguajes de programación son decididamente inferiores a la notación matemática y son poco utilizados como herramientas de pensamiento de maneras que se considerarían significativas por, por ejemplo, un matemático aplicado.

La tesis es que las ventajas de la ejecutabilidad y universalidad encontradas en los lenguajes de programación se pueden combinar eficazmente, en un solo lenguaje coherente, con las ventajas ofrecidas por la notación matemática. es importante distinguir la dificultad de describir y aprender una pieza de notación de la dificultad de dominar sus implicaciones. Por ejemplo, aprender las reglas para la computación de un producto de matriz es fácil, pero un dominio de sus implicaciones (como su asociatividad, su distributividad sobre adición, y su capacidad de representar funciones lineales y operaciones geométricas) es una materia diferente y mucho más difícil.

De hecho, la muy sugestiva de una notación puede hacer que parezca más difícil aprender debido a las muchas propiedades que sugiere para las exploraciones.

[...]

Los usuarios de computadoras y lenguajes de programación a menudo se preocupan principalmente por la eficiencia de la ejecución de algoritmos, y podría, por lo tanto, descartar sumariamente muchos de los algoritmos presentados aquí. Tal despido sería corto de vista ya que una clara declaración de un algoritmo se puede utilizar generalmente como base de la cual uno puede derivar fácilmente un algoritmo más eficiente.

La base de la programación y el pensamiento basados en matrices es encontrar y explotar las propiedades de los datos en los que los elementos individuales son similares o adyacentes. A diferencia de la orientación a objetos, que descompone implícitamente los datos en sus partes constituyentes (o cantidades escalares), la orientación a matrices busca agrupar los datos y aplicar un manejo uniforme.

El rango de función es un concepto importante para los lenguajes de programación de matrices en general, por analogía con el rango tensorial en matemáticas: las funciones que operan sobre datos pueden clasificarse por el número de dimensiones sobre las que actúan. La multiplicación ordinaria, por ejemplo, es una función de rango escalar porque opera sobre datos de dimensión cero (números individuales). La operación de producto vectorial es un ejemplo de una función de rango vectorial porque opera sobre vectores, no sobre escalares. La multiplicación de matrices es un ejemplo de una función de dos rangos, porque opera sobre objetos bidimensionales (matrices). Los operadores de colapso reducen la dimensionalidad de una matriz de datos de entrada en una o más dimensiones. Por ejemplo, la suma de los elementos colapsa la matriz de entrada en una dimensión.

Usos

La programación de matrices es muy adecuada para la paralelización implícita, un tema de mucha investigación en la actualidad. Además, las CPU de Intel y compatibles desarrolladas y producidas después de 1997 contenían varias extensiones de conjuntos de instrucciones, comenzando por MMX y continuando con SSSE3 y 3DNow!, que incluyen capacidades rudimentarias de matriz SIMD. Esto ha continuado en la década de 2020 con conjuntos de instrucciones como AVX-512, lo que convierte a las CPU modernas en sofisticados procesadores vectoriales. El procesamiento de matrices se diferencia del procesamiento paralelo en que un procesador físico realiza operaciones en un grupo de elementos simultáneamente, mientras que el procesamiento paralelo tiene como objetivo dividir un problema más grande en otros más pequeños (MIMD) para que sean resueltos por partes por numerosos procesadores. Los procesadores con múltiples núcleos y las GPU con miles de núcleos de computación general son comunes a partir de 2023.

Idiomas

Los ejemplos canónicos de lenguajes de programación de matrices son Fortran, APL y J. Otros incluyen: A+, Analytica, Chapel, IDL, Julia, K, Klong, Q, MATLAB, GNU Octave, Scilab, FreeMat, PDL, R, Raku, S-Lang, SAC, Nial, ZPL, Futhark y TI-BASIC.

Lenguajes escalares

En lenguajes escalares como C y Pascal, las operaciones se aplican solo a valores únicos, por lo que a+b expresa la suma de dos números. En dichos lenguajes, sumar una matriz a otra requiere indexación y bucles, cuya codificación es tediosa.

para ()i = 0; i c) n; i++) para ()j = 0; j c) n; j++) a[i[ ]j] += b[i[ ]j];

En lenguajes basados en matrices, por ejemplo en Fortran, el bucle for anidado anterior se puede escribir en formato de matriz en una línea,

a = a + b

o alternativamente, para enfatizar la naturaleza matricial de los objetos,

a(:,:) = a(:,:) + b(:,:)

Mientras que los lenguajes escalar como C no tienen elementos de programación de array nativos como parte del lenguaje apropiado, esto no significa que los programas escritos en estos idiomas nunca se aprovechan de las técnicas subyacentes de la vectorización (es decir, utilizando las instrucciones basadas en vectores de CPU si las tiene o utilizando múltiples núcleos de CPU). Algunos compiladores C como GCC en algunos niveles de optimización detectan y vectorizan secciones de código que sus heurísticas determinan se beneficiarían de él. Otro enfoque es dado por la API OpenMP, que permite paralelizar las secciones aplicables del código aprovechando múltiples núcleos de CPU.

Array languages

En los lenguajes de matrices, las operaciones se generalizan para que se apliquen tanto a escalares como a matrices. Por lo tanto, a+b expresa la suma de dos escalares si a y b son escalares, o la suma de dos matrices si son matrices.

Un lenguaje de matrices simplifica la programación, pero posiblemente a un costo conocido como la penalidad de abstracción. Debido a que las adiciones se realizan de forma aislada del resto del código, es posible que no produzcan el código más eficiente de forma óptima. (Por ejemplo, es posible que se encuentren adiciones de otros elementos de la misma matriz durante la misma ejecución, lo que causaría búsquedas repetidas innecesarias). Incluso el compilador optimizador más sofisticado tendría dificultades extremas para fusionar dos o más funciones aparentemente dispares que podrían aparecer en diferentes secciones del programa o subrutinas, aunque un programador podría hacerlo fácilmente, agregando sumas en la misma pasada por la matriz para minimizar la sobrecarga).

Ada

El código C anterior se convertiría en el siguiente en el lenguaje Ada, que admite la sintaxis de programación de matrices.

A := A + B;

APL

APL utiliza símbolos Unicode de un solo carácter sin ningún tipo de complejidad sintáctica.

A ← A + B

Esta operación funciona en matrices de cualquier rango (incluido el rango 0) y en un escalar y una matriz. Dyalog APL extiende el lenguaje original con asignaciones aumentadas:

A +← B

Análisis

Analytica ofrece la misma economía de expresión que Ada.

A:= A + B;

BÁSICO

Dartmouth BASIC tenía instrucciones MAT para la manipulación de matrices y arreglos en su tercera edición (1966).

DIM A()4),B()4),C()4)MAT A = 1MAT B = 2 * AMAT C = A + BMAT PRINT A,B,C

Mata

El lenguaje de programación matricial Mata de Stata admite la programación de matrices. A continuación, ilustramos la suma, la multiplicación, la suma de una matriz y un escalar, la multiplicación elemento por elemento, la subexpresión y una de las muchas funciones de matriz inversa de Mata.

. mata mata:

A =1,2,3) (4,5,6)

A
 1 2 3 +------------+ 1 Silencio 1 2 3 Silencio
 2 Silencio 4 5 6 Silencio
 +------------+B =2..4) (1..3)

B
 1 2 3 +------------+ 1 Silencio 2 3 4 Silencio
 2 Silencio 1 2 3 Silencio
 +------------+: C = J()3,2,1) // A 3 por 2 matriz de uno: C
 1 2 +--------+ 1 Silencio 1 1 Silencio
 2 Silencio 1 1 Silencio
 3 Silencio 1 1 Silencio
 +--------+D = A + B

D
 1 2 3 +------------+ 1 Silencio 3 5 7 Silencio
 2 Silencio 5 7 9 Silencio
 +------------+E = A*C

: E
 1 2 +----------+ 1 Silencio 6 6 Silencio
 2 Silencio 15 15 Silencio
 +----------+: F = A:*B

: F
 1 2 3 + 1 Silencio 2 6 12 Silencio
 2 Silencio 4 10 18 Silencio
 +G = E:+ 3: G
 1 2 +----------+ 1 Silencio 9 9 Silencio
 2 Silencio 18 18 Silencio
 +----------+H = F21), (1, 2) // Subscripting to get a submatrix of F and: // conmutación de la fila 1 y 2: H
 1 2 +----------+ 1 Silencio 4 10 Silencio
 2 Silencio 2 6 Silencio
 +----------+# I = invsym(F '*F) // Inverso generalizado (F*F^(-1)F=F) de: // matriz semidefinida simétrica positiva# I
[simétrica]
 1 2 3 Y... 1 Silencio 0 Silencio
 2 Silencio 0 3.25 Silencio
 3 Silencio 0 -1.75.94444444 Silencio
 Y...: final

MATLAB

La implementación en MATLAB permite la misma economía que permite el uso del lenguaje Fortran.

A = A + B;

Una variante del lenguaje MATLAB es el lenguaje GNU Octave, que extiende el lenguaje original con asignaciones aumentadas:

A += B;

Tanto MATLAB como GNU Octave admiten de forma nativa operaciones de álgebra lineal, como la multiplicación de matrices, la inversión de matrices y la solución numérica de sistemas de ecuaciones lineales, incluso utilizando la pseudoinversa de Moore-Penrose.

El ejemplo de Nial del producto interno de dos matrices se puede implementar utilizando el operador de multiplicación de matrices nativo. Si a es un vector de fila de tamaño [1 n] y b es un vector de columna correspondiente de tamaño [n 1].

a * b;

Por el contrario, el producto de entrada se implementa como:

a.* b;

El producto interno entre dos matrices que tienen el mismo número de elementos se puede implementar con el operador auxiliar (:), que transforma una matriz dada en un vector columna, y el operador de transposición ':

A(:)' * B(:);

Rasql

El lenguaje de consulta rasdaman es un lenguaje de programación de matrices orientado a bases de datos. Por ejemplo, se podrían agregar dos matrices con la siguiente consulta:

SELECT A + BDESDE A, B

R

El lenguaje R admite el paradigma de matriz de forma predeterminada. El siguiente ejemplo ilustra un proceso de multiplicación de dos matrices seguido de la adición de un escalar (que, de hecho, es un vector de un elemento) y un vector:

■ A . matriz()1:6, #=2) ! esto tiene nrow=2... y A tiene 2 filas■ A [,1] [,2] [,3][1,] 1 3 5[2,] 2 4 6■ B . t() matriz()6:1, #=2) ) # t() es un operador de transpose!! esto tiene nrow=2... y B tiene 3 filas --- una clara contradicción a la definición de A■ B [,1] [,2][1,] 6 5[2,] 4 3[3,]■ C . A Porcentaje B■ C [,1] [,2][1,] 28 19[2,] 40 28■ D . C + 1■ D [,1] [,2][1,] 29 20[2,] 41 29■ D + c()1, 1) # c() crea un vector [,1] [,2][1,] 30 21[2,] 42 30

Raku

Raku admite el paradigma de matriz a través de sus metaoperadores. El siguiente ejemplo demuestra la adición de matrices @a y @b utilizando el operador Hyper junto con el operador plus.

[0] # @a [1,1], [2,2], [3,3]]
[[2]1 1[ ]2 2[ ]3 3]]

[1] # @b [4,4], [5,5], [6,6]]
[[2]4 4[ ]5 5[ ]6 6]]

[2] @a »+« @b;
[[2]5 5[ ]7 7[ ]9 9]]

Razones matemáticos y notación de lenguaje

El operador de división por la izquierda de matrices expresa de forma concisa algunas propiedades semánticas de las matrices. Como en el equivalente escalar, si el (determinante del) coeficiente (matriz) A no es nulo, entonces es posible resolver la ecuación (vectorial) A * x = b multiplicando por la izquierda ambos lados por la inversa de A: A−1 (tanto en lenguajes MATLAB como GNU Octave: A^-1). Las siguientes afirmaciones matemáticas se cumplen cuando A es una matriz cuadrada de rango completo:

A^-1 *(A * x)==A^-1 * (b)

(A^-1 * A)* x ==A^-1 * b (Asociación de la multiplicación matrix)

x = A^-1 * b

donde == es el operador relacional de equivalencia. Las sentencias anteriores también son expresiones válidas de MATLAB si la tercera se ejecuta antes que las demás (las comparaciones numéricas pueden ser falsas debido a errores de redondeo).

Si el sistema está sobredeterminado –de modo que A tiene más filas que columnas– la pseudoinversa A+ (en los lenguajes MATLAB y GNU Octave: pinv(A)) puede reemplazar a la inversa A−1, de la siguiente manera:

pinv(A) *(A * x)==pinv(A) * (b)

(pinv(A) * A)* x ==pinv(A) * b (Asociación de la multiplicación matrix)

x = pinv(A) * b

Sin embargo, estas soluciones no son las más concisas (por ejemplo, todavía sigue siendo necesario diferenciar mediante notación los sistemas sobredeterminados) ni las más eficientes desde el punto de vista computacional. Este último punto es fácil de entender al considerar nuevamente el equivalente escalar a * x = b, para el cual la solución x = a^-1 * b requeriría dos operaciones en lugar de la más eficiente x = b / a. El problema es que, en general, las multiplicaciones de matrices no son conmutativas, ya que la extensión de la solución escalar al caso matricial requeriría:

(a * x)/ a ==b / a

(x * a)/ a ==b / a (La computatividad no se mantiene para las matrices!)

x * (a / a)==b / a (la asociación también tiene para las matrices)

x = b / a

El lenguaje MATLAB introduce el operador de división por la izquierda para mantener la parte esencial de la analogía con el caso escalar, simplificando así el razonamiento matemático y preservando la concisión:

A (A * x)==A b

(A A)* x ==A b (la asociación también tiene para matrices, la conmutación ya no es necesaria)

x = A b

Este no es sólo un ejemplo de programación matricial concisa desde el punto de vista de la codificación, sino también desde la perspectiva de la eficiencia computacional, que en varios lenguajes de programación matricial se beneficia de bibliotecas de álgebra lineal bastante eficientes como ATLAS o LAPACK.

Volviendo a la cita anterior de Iverson, la razón detrás de ella debería ahora ser evidente:

es importante distinguir la dificultad de describir y aprender una pieza de notación de la dificultad de dominar sus implicaciones. Por ejemplo, aprender las reglas para la computación de un producto de matriz es fácil, pero un dominio de sus implicaciones (como su asociatividad, su distributividad sobre adición, y su capacidad de representar funciones lineales y operaciones geométricas) es una materia diferente y mucho más difícil. De hecho, la muy sugestiva de una notación puede hacer que parezca más difícil aprender debido a las muchas propiedades que sugiere para las exploraciones.

Bibliotecas de terceros

El uso de bibliotecas especializadas y eficientes para proporcionar abstracciones más concisas también es común en otros lenguajes de programación. En C++, varias bibliotecas de álgebra lineal explotan la capacidad del lenguaje para sobrecargar operadores. En algunos casos, una abstracción muy concisa en esos lenguajes está explícitamente influenciada por el paradigma de programación de matrices, como lo hacen la biblioteca de extensión NumPy para Python y las bibliotecas Armadillo y Blitz++.