Diseño de fila mayor versus columna mayor de matrices

16

En la programación de cálculos de matriz densa, ¿hay alguna razón para elegir un diseño de fila mayor del diseño de columna mayor?

Sé que dependiendo del diseño de la matriz elegida, necesitamos escribir el código apropiado para usar las memorias caché de manera efectiva para fines de velocidad.

El diseño de fila principal parece más natural y más simple (al menos para mí). Pero las bibliotecas principales como LAPACK que están escritas en Fortran usan el diseño principal de la columna, por lo que debe haber alguna razón para haber hecho esta elección.

smilingbuddha
fuente
Si consideramos calcular b = A * x con el vector de columna x, para la fila mayor A podemos usar productos internos de vectores, A (i,:) ^ T x para obtener b (i); para la columna mayor, es posible que solo necesitemos vectores multiplicadores escalares, sum_i A (:, i) x (i). ¡Me parece que la columna mayor es mucho mejor! ¿Qué piensas?
Hui Zhang
Entrena para que te guste la columna principal. Es fácil cuando visualiza vectores como columnas, o su transposición como filas. Hace que la visualización de la multiplicación de matrices sea muy simple y facilita seguir muchas matemáticas publicadas.
Mike Dunlavey

Respuestas:

18

El diseño principal de la columna es el esquema utilizado por Fortran y es por eso que se usa en LAPACK y otras bibliotecas.

En general, es mucho más eficiente en términos de uso de ancho de banda de memoria y rendimiento de caché para acceder a los elementos de una matriz en el orden en que están dispuestos en la memoria. Dependiendo de cómo se almacenen sus matrices, querrá elegir algoritmos que aprovechen esto.

Almacenamiento interno Almacenamiento interno del formato principal de columna

Brian Borchers
fuente
11

En el vacío sin considerar ningún software existente, no hay razón para preferir la columna principal sobre la fila principal desde el punto de vista del código. Sin embargo, la mayoría de la literatura matemática está escrita de manera que agrupa los vectores en una matriz almacenándolos como columnas en lugar de filas. Por ejemplo, cuando escribe la ecuación de valor propio completo , la XUNX=XΛXmatriz contiene todos los vectores propios escritos en columnas. Realmente nunca se ve escrito de otra manera (aunque escuché que a la gente de estadísticas les gustan los vectores de fila). Por lo tanto, era natural que el primer software asumiera el formato principal de columna, de modo que si tiene una matriz que es un conjunto de vectores, el almacenamiento de cualquier vector es contiguo. Por lo tanto, me imagino que la tradición se ha llevado hasta nuestros días, y si quieres interactuar con el viejo Fortran, debes usar la columna mayor. Entonces, casi todo el álgebra lineal numérica altamente eficiente se realiza en la columna mayor.

La razón por la cual C es una fila mayor es en parte consecuencia de su sintaxis de matriz; declara una matriz de 3 filas por 2 columnas como double a[3][2], y los índices posteriores varían más rápido que los índices anteriores, lo que para las matrices 2D hace que la fila sea mayor. Combine esto con el orden natural de lectura occidental de izquierda a derecha, hace que la fila mayor parezca más natural.

Victor Liu
fuente
2
Creo que estos son argumentos pobres. El hecho de que el último índice en '' 'doble a [3] [2]' '' varíe más rápido no es una coincidencia: fue una decisión de diseño consciente de la misma manera que fue una decisión de diseño consciente en Fortran hágalo al revés cuando tenga una matriz '' 'real (3,2)' ''.
Wolfgang Bangerth
1
Además, ya no es cierto que casi todo el álgebra lineal numérica altamente eficiente sea una columna mayor. Esto aún puede ser cierto para BLAS y LAPACK, pero no es cierto para todas las bibliotecas de álgebra lineal principales que han aparecido en los últimos 15 años: por ejemplo, tanto PETSc como Trilinos utilizan formatos de almacenamiento de matriz dispersos principales.
Wolfgang Bangerth
Soy consciente de que la convención C fue una decisión consciente, probablemente basada en el orden de lectura natural. Quise decir que probablemente no fue diseñado teniendo en cuenta el álgebra lineal numérica, por lo que es una coincidencia que sea una fila mayor. En segundo lugar, no tenía la intención de mantener el argumento para matrices dispersas, solo densas. Por disperso, es un poco mixto, con formatos de fila y columna comprimidos.
Victor Liu
55
No para diferir el punto, pero C era originalmente un lenguaje de sistemas, basado en los lenguajes anteriores B y BCPL, que se ejecutaba en sistemas como el PDP-11 que originalmente no tenía números de punto flotante. Decir que lo diseñaron teniendo en cuenta los números es bastante difícil.
Victor Liu
77
He estado allí, etc. La razón por la cual las matrices en C mueven el último índice más rápido es porque C no tiene matrices. Tiene vectores de vectores que pueden implementarse de forma transparente como bloques sólidos de memoria o como conjuntos de punteros a conjuntos. Hacer que el orden de los índices sea compatible con Fortran (supongo) ni siquiera estaba en el radar de Dennis Ritchie.
Mike Dunlavey
2

El orden de columnas principales parece ser más natural. Por ejemplo, suponga que si desea guardar la película en un archivo imagen por imagen, entonces está usando el orden de las columnas, y eso es muy intuitivo y nadie lo guardaría en orden de fila principal.

Si es programador en C / C ++, debe usar algunas bibliotecas de nivel superior para matrices (Eigen, Armadillo, ...) con el orden predeterminado de columnas principales. Solo el loco usaría punteros C sin procesar con orden de fila mayor, aunque C / C ++ ofrece algo que recuerda la indexación matricial.

Por simplicidad, todo con orden de fila mayor debe considerarse como al menos extraño formado. Corte a corte es simplemente orden natural y significa orden de columna mayor (como Fortran). Nuestros padres / madres tenían muy buenas razones por las que lo eligieron.

Desafortunadamente, antes de que quedara claro, se crearon varias bibliotecas interesantes en orden de filas principales, probablemente debido a la falta de experiencia.

Para aclarar, recuerde la definición de orden de fila principal donde el índice derecho varía más rápido en un paso a través de la memoria, por ejemplo, A (x, y, z) es el índice z, significa que en la memoria los píxeles de diferentes segmentos son adyacentes, lo que no sería no quiero Para la película A (x, y, t) el último índice es el tiempo t. No es difícil imaginar que es simplemente imposible guardar la película en modo de fila principal.

Pablo
fuente
2

metro×norte

  • metroyo,jyo×metro+j
  • metroyo,jj×norte+yo

Ahora imagine el siguiente algoritmo:

for i from 1 to m
   for j from 1 to n
      do something with m(i,j)

yo×metro+j

Conclusiones:

  1. Sí, tiene una importancia, pero la elección depende de la forma en que se accede a los datos. Para el ejemplo anterior, si se usa el orden de columnas, lo que puede hacer es simplemente intercambiar los dos bucles.

  2. regla general: el índice que varía rápidamente debe asignarse a ubicaciones sucesivas en la memoria.

  3. Más importante aún, medir / comparar el impacto de la elección es fundamental, ya que depende de muchos parámetros (el tamaño de los datos, el tamaño de la memoria caché, la forma en que el lenguaje utilizado asigna múltiples índices a un índice lineal, la forma en que funciona el sistema administra la memoria virtual, la forma en que los bucles se anidan en la biblioteca de álgebra lineal que usa ...)

BrunoLevy
fuente