Programación de matrices - Array programming
En informática , la programación de matrices 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 ) se han diseñado específicamente para generalizar operaciones en escalares para aplicarlas de forma transparente a vectores , matrices y matrices de dimensiones superiores. Estos incluyen APL , J , Fortran 90 , MATLAB , Analytica , TK Solver (como listas), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) y la extensión NumPy para Python . En estos lenguajes, una operación que opera en arreglos completos 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 amplias sobre la manipulación de datos. El nivel de concisión puede ser dramático en ciertos casos: no es raro encontrar gran variedad de lenguajes de programación de 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 a la vez a un conjunto completo de valores. Esto lo convierte en un modelo de programación de alto nivel , ya que permite al programador pensar y operar en 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, refiriéndose 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 se utilizan poco como herramientas de pensamiento en formas que serían consideradas significativas por, digamos, un matemático aplicado.
La tesis es que las ventajas de ejecución y universalidad que se encuentran en los lenguajes de programación pueden combinarse eficazmente, en un solo lenguaje coherente, con las ventajas que ofrece la notación matemática. Es importante distinguir la dificultad de describir y aprender una nota de la dificultad de dominar sus implicaciones. Por ejemplo, aprender las reglas para calcular un producto matricial es fácil, pero el dominio de sus implicaciones (como su asociatividad, su distributividad sobre la suma y su capacidad para representar funciones lineales y operaciones geométricas) es un asunto diferente y mucho más difícil. .
De hecho, la misma sugerencia de una notación puede hacer que parezca más difícil de 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, por lo tanto, podrían descartar sumariamente muchos de los algoritmos presentados aquí. Tal desestimación sería miope, ya que una declaración clara de un algoritmo generalmente puede usarse como base a partir de la cual se puede derivar fácilmente un algoritmo más eficiente.
La base detrás de la programación y el pensamiento de matrices es encontrar y explotar las propiedades de los datos donde los elementos individuales son similares o adyacentes. A diferencia de la orientación a objetos que desglosa implícitamente los datos en sus partes constituyentes (o cantidades escalares ), la orientación de matriz busca agrupar 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 de tensor 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 clasificación escalar porque opera con datos de dimensión cero (números individuales). La operación de producto cruzado es un ejemplo de una función de rango vectorial porque opera en vectores, no en escalares. La multiplicación de matrices es un ejemplo de una función de 2 rangos, porque opera en objetos de 2 dimensiones (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 elementos colapsa la matriz de entrada en 1 dimensión.
Usos
La programación de matrices se adapta muy bien a la paralelización implícita ; un tema de mucha investigación en la actualidad. Además, Intel y las CPU compatibles desarrolladas y producidas después de 1997 contenían varias extensiones de conjuntos de instrucciones, comenzando desde MMX y continuando a través de SSSE3 y 3DNow! , que incluyen capacidades rudimentarias de matriz SIMD . El procesamiento de matrices se diferencia del procesamiento en paralelo en que un procesador físico realiza operaciones en un grupo de elementos simultáneamente, mientras que el procesamiento en paralelo tiene como objetivo dividir un problema más grande en otros más pequeños ( MIMD ) para ser resuelto por varios procesadores. Los procesadores con dos o más núcleos son cada vez más comunes en la actualidad.
Idiomas
Los ejemplos canónicos de lenguajes de programación matriz son Fortran , APL , y J . Otros incluyen: A + , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL y TI-BASIC .
Lenguajes escalares
En lenguajes escalares como C y Pascal , las operaciones se aplican solo a valores individuales, por lo que a + b expresa la suma de dos números. En tales lenguajes, agregar una matriz a otra requiere indexación y bucle, cuya codificación es tediosa.
for (i = 0; i < n; i++)
for (j = 0; j < 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 de matriz de los objetos,
a(:,:) = a(:,:) + b(:,:)
Si bien los lenguajes escalares como C no tienen elementos de programación de matrices nativos como parte del lenguaje propiamente dicho, esto no significa que los programas escritos en estos lenguajes nunca aprovechen las técnicas subyacentes de vectorización (es decir, utilizan las instrucciones basadas en vectores de una CPU si las tiene). ellos o mediante el uso de varios núcleos de CPU). Algunos compiladores de C como GCC en algunos niveles de optimización detectan y vectorizan secciones de código que su heurística determina que se beneficiarían de él. La API OpenMP ofrece otro enfoque , que permite paralelizar secciones de código aplicables aprovechando múltiples núcleos de CPU.
Idiomas de matriz
En los lenguajes de matrices, las operaciones se generalizan para aplicarse tanto a escalares como a matrices. Por lo tanto, un + b expresa la suma de dos escalares si un y b son escalares, o la suma de dos matrices si son matrices.
Un lenguaje de matriz simplifica la programación, pero posiblemente a un costo conocido como penalización por abstracción . Debido a que las adiciones se realizan de forma aislada del resto de la codificación, es posible que no produzcan el código más eficiente de manera óptima . (Por ejemplo, las adiciones de otros elementos de la misma matriz pueden encontrarse posteriormente durante la misma ejecución, provocando búsquedas repetidas innecesarias). Incluso el compilador de optimización más sofisticado tendría dificultades para fusionar dos o más funciones aparentemente dispares que podrían aparecer en diferentes secciones de programa o subrutinas, aunque un programador podría hacer esto fácilmente, agregando sumas en la misma pasada sobre 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 azúcar sintáctico.
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 amplía el idioma original con asignaciones aumentadas :
A +← B
Analytica
Analytica ofrece la misma economía de expresión que Ada.
A := A + B;
BÁSICO
Dartmouth BASIC tenía declaraciones MAT para la manipulación de matrices y arreglos en su tercera edición (1966).
DIM A(4),B(4),C(4)
MAT A = 1
MAT B = 2 * A
MAT C = A + B
MAT PRINT A,B,C
Mata
Mata, el lenguaje de programación matricial 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, el subíndice y una de las muchas funciones matriciales inversas de Mata.
. mata:
: A = (1,2,3) \(4,5,6)
: A
1 2 3
+-------------+
1 | 1 2 3 |
2 | 4 5 6 |
+-------------+
: B = (2..4) \(1..3)
: B
1 2 3
+-------------+
1 | 2 3 4 |
2 | 1 2 3 |
+-------------+
: C = J(3,2,1) // A 3 by 2 matrix of ones
: C
1 2
+---------+
1 | 1 1 |
2 | 1 1 |
3 | 1 1 |
+---------+
: D = A + B
: D
1 2 3
+-------------+
1 | 3 5 7 |
2 | 5 7 9 |
+-------------+
: E = A*C
: E
1 2
+-----------+
1 | 6 6 |
2 | 15 15 |
+-----------+
: F = A:*B
: F
1 2 3
+----------------+
1 | 2 6 12 |
2 | 4 10 18 |
+----------------+
: G = E :+ 3
: G
1 2
+-----------+
1 | 9 9 |
2 | 18 18 |
+-----------+
: H = F[(2\1), (1, 2)] // Subscripting to get a submatrix of F and
: // switch row 1 and 2
: H
1 2
+-----------+
1 | 4 10 |
2 | 2 6 |
+-----------+
: I = invsym(F'*F) // Generalized inverse (F*F^(-1)F=F) of a
: // symmetric positive semi-definite matrix
: I
[symmetric]
1 2 3
+-------------------------------------------+
1 | 0 |
2 | 0 3.25 |
3 | 0 -1.75 .9444444444 |
+-------------------------------------------+
: end
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 amplía 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 del sistema 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. If aes un vector de fila de tamaño [1 n] y bes un vector de columna correspondiente de tamaño [n 1].
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 de 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 + B
FROM 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 suma de un escalar (que es, de hecho, un vector de un elemento) y un vector:
> A <- matrix(1:6, nrow=2) !!this has nrow=2 ... and A has 2 rows
> A
[,1] [,2] [,3]
[1,] 1 3 5
[2,] 2 4 6
> B <- t( matrix(6:1, nrow=2) ) # t() is a transpose operator !!this has nrow=2 ... and B has 3 rows --- a clear contradiction to the definition of A
> B
[,1] [,2]
[1,] 6 5
[2,] 4 3
[3,] 2 1
> C <- A %*% 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() creates a vector
[,1] [,2]
[1,] 30 21
[2,] 42 30
Razonamiento matemático y notación lingüística
El operador de división por la izquierda de la matriz expresa de forma concisa algunas propiedades semánticas de las matrices. Como en el equivalente escalar, si el ( determinante del) coeficiente (matriz) Ano es nulo, entonces es posible resolver la ecuación (vectorial) A * x = bmultiplicando por la izquierda ambos lados por el inverso de A: (en los lenguajes MATLAB y GNU Octave :) . Las siguientes afirmaciones matemáticas son válidas cuando es una matriz cuadrada de rango completo :
A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)-
(A^-1 * A)* x ==A^-1 * b( asociatividad matriz-multiplicación ) x = A^-1 * b
donde ==es el operador relacional de equivalencia . Las declaraciones anteriores también son expresiones MATLAB válidas 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, por lo que Atiene más filas que columnas, el pseudoinverso (en los lenguajes MATLAB y GNU Octave :) puede reemplazar al inverso , de la siguiente manera:
A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)-
(pinv(A) * A)* x ==pinv(A) * b(asociatividad matriz-multiplicación) x = pinv(A) * b
Sin embargo, estas soluciones no son ni las más concisas (por ejemplo, sigue existiendo la necesidad de 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 lo cual la solución x = a^-1 * brequeriría dos operaciones en lugar de la más eficiente x = b / a. El problema es que generalmente las multiplicaciones de matrices no son conmutativas, ya que la extensión de la solución escalar al caso de la matriz requeriría:
(a * x)/ a ==b / a-
(x * a)/ a ==b / a(¡la conmutatividad no es válida para las matrices!) -
x * (a / a)==b / a(la asociatividad también es válida para matrices) x = b / a
El lenguaje MATLAB introduce el operador de división a 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 asociatividad también es válida para las matrices, la conmutatividad ya no es necesaria) x = A \ b
Este no es solo un ejemplo de programación concisa de matrices 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 de matrices se beneficia de bibliotecas de álgebra lineal bastante eficientes como ATLAS o LAPACK .
Volviendo a la cita anterior de Iverson, la lógica detrás de ella debería ser ahora evidente:
Es importante distinguir la dificultad de describir y aprender una nota de la dificultad de dominar sus implicaciones. Por ejemplo, aprender las reglas para calcular un producto matricial es fácil, pero el dominio de sus implicaciones (como su asociatividad, su distributividad sobre la suma y su capacidad para representar funciones lineales y operaciones geométricas) es un asunto diferente y mucho más difícil. . De hecho, la misma sugerencia de una notación puede hacer que parezca más difícil de 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 las bibliotecas Armadillo y Blitz ++ .