Matriz dispersa

Las matrices de banda constituyen una clase especial de matrices dispersas donde los elementos distintos de cero se concentran cerca de la diagonal principal. Una matriz de banda se caracteriza por sus anchos de banda inferior y superior, que se refieren al número de diagonales por debajo y por encima (respectivamente) de la diagonal principal entre las que se encuentran todos los elementos distintos de cero.

Formalmente, el ancho de banda inferior de una matriz A es el número más pequeño p tal que la entrada a _{i , j} se anula siempre que i > j + p . De manera similar, el ancho de banda superior es el número más pequeño p tal que a _{i , j} = 0 siempre que i < j − p ( Golub & Van Loan 1996 , §1.2.1) . Por ejemplo, una matriz tridiagonal tiene un ancho de banda inferior de 1 y un ancho de banda superior de 1 . Como otro ejemplo, la siguiente matriz dispersa tiene un ancho de banda inferior y superior iguales a 3. Nótese que los ceros se representan con puntos para mayor claridad. $${\displaystyle {\begin{bmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end{bmatrix}}}$$

Las matrices con un ancho de banda superior e inferior razonablemente pequeño se conocen como matrices de banda y a menudo se prestan a algoritmos más sencillos que las matrices dispersas generales; o bien, en ocasiones se pueden aplicar algoritmos de matrices densas y ganar eficiencia simplemente recorriendo un número reducido de índices.

Al reorganizar las filas y columnas de una matriz A, es posible obtener una matriz A ′ con un ancho de banda menor. Existen varios algoritmos diseñados para minimizar el ancho de banda .

Una matriz dispersa simétrica surge como la matriz de adyacencia de un grafo no dirigido ; se puede almacenar de manera eficiente como una lista de adyacencia .

Una matriz diagonal por bloques consta de submatrices a lo largo de sus bloques diagonales. Una matriz diagonal por bloques A tiene la forma $${\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1}&0&\cdots &0\\0&\mathbf {A} _{2}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}\end{bmatrix}},}$$

donde A _k es una matriz cuadrada para todo k = 1, ..., n .

Los elementos que cambian de valor durante la ejecución de un algoritmo son aquellos que pasan de un valor inicial cero a un valor distinto de cero. Para reducir los requisitos de memoria y el número de operaciones aritméticas, resulta útil minimizar estos elementos intercambiando filas y columnas de la matriz. La descomposición simbólica de Cholesky permite calcular el peor resultado posible antes de realizar la descomposición de Cholesky propiamente dicha .

Existen otros métodos además de la descomposición de Cholesky . Los métodos de ortogonalización (como la factorización QR) son comunes, por ejemplo, al resolver problemas mediante el método de mínimos cuadrados. Si bien el relleno teórico sigue siendo el mismo, en la práctica los "falsos no ceros" pueden variar según el método. Además, las versiones simbólicas de estos algoritmos pueden utilizarse de la misma manera que la descomposición de Cholesky simbólica para calcular el relleno en el peor de los casos.

Para la resolución de matrices dispersas existen métodos tanto iterativos como directos.

Los métodos iterativos, como el método del gradiente conjugado y GMRES, utilizan cálculos rápidos de productos matriz-vector.${\displaystyle Ax_{i}}$donde matriz${\displaystyle A}$es escaso. El uso de precondicionadores puede acelerar significativamente la convergencia de dichos métodos iterativos.

DOK consiste en un diccionario que asigna pares ( fila, columna) al valor de los elementos. Los elementos que no están en el diccionario se consideran cero. El formato es adecuado para construir incrementalmente una matriz dispersa en orden aleatorio, pero no es eficiente para iterar sobre valores distintos de cero en orden lexicográfico. Normalmente, se construye una matriz en este formato y luego se convierte a otro formato más eficiente para su procesamiento. ^{[ 4 ]}

LIL almacena una lista por fila, donde cada entrada contiene el índice de columna y el valor. Normalmente, estas entradas se mantienen ordenadas por índice de columna para una búsqueda más rápida. Este es otro formato adecuado para la construcción incremental de matrices. ^{[ 5 ]}

COO almacena una lista de tuplas (fila, columna, valor) . Idealmente, las entradas se ordenan primero por índice de fila y luego por índice de columna para mejorar los tiempos de acceso aleatorio. Este es otro formato adecuado para la construcción incremental de matrices. ^{[ 6 ]}

El formato de fila dispersa comprimida (CSR), almacenamiento de fila comprimida (CRS) o formato Yale representa una matriz M mediante tres matrices (unidimensionales) que contienen, respectivamente, valores distintos de cero, la extensión de las filas y los índices de las columnas. Es similar al formato COO, pero comprime los índices de fila, de ahí su nombre. Este formato permite un acceso rápido a las filas y multiplicaciones matriz-vector ( M x ). El formato CSR se utiliza al menos desde mediados de la década de 1960, y la primera descripción completa apareció en 1967. ^{[ 7 ]}

El formato CSR almacena una matriz dispersa m × n , M, en forma de filas utilizando tres arreglos (unidimensionales) (V, COL_INDEX, ROW_INDEX) . Sea NNZ el número de entradas no nulas en M. (Tenga en cuenta que aquí se utilizarán índices basados ​​en cero ).

• Los arreglos V y COL_INDEX tienen una longitud de NNZ y contienen los valores distintos de cero y los índices de columna de esos valores, respectivamente.
• COL_INDEX contiene la columna en la que se encuentra la entrada V correspondiente.
• El array ROW_INDEX tiene una longitud de m + 1 y codifica el índice en V y COL_INDEX donde comienza la fila dada. Esto es equivalente a ROW_INDEX[j] codificando el número total de elementos distintos de cero por encima de la fila j . El último elemento es NNZ , es decir, el índice ficticio en V inmediatamente después del último índice válido NNZ − 1. ^{[ 8 ]}

Por ejemplo, la matriz $${\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}}$$ es una matriz de 4 × 4 con 4 elementos distintos de cero, por lo tanto

V = [ 5 8 3 6 ] COL_INDEX = [ 0 1 2 1 ] ÍNDICE_DE_FILA = [ 0 1 2 3 4 ]

suponiendo que se trata de un lenguaje con índice cero.

Para extraer una fila, primero definimos:

inicio_fila = ÍNDICE_FILA[fila] fin_fila = ÍNDICE_FILA[fila + 1]

Luego tomamos segmentos de V y COL_INDEX comenzando en row_start y terminando en row_end.

Para extraer la fila 1 (la segunda fila) de esta matriz, establecemos row_start=1y row_end=2. Luego hacemos las secciones V[1:2] = [8]y COL_INDEX[1:2] = [1]. Ahora sabemos que en la fila 1 tenemos un elemento en la columna 1 con valor 8.

En este caso, la representación CSR contiene 13 entradas, en comparación con las 16 de la matriz original. El formato CSR ahorra memoria solo cuando NNZ < ( m ( n − 1) − 1) / 2 .

Otro ejemplo, la matriz $${\displaystyle {\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}}$$ es una matriz de 4 × 6 (24 entradas) con 8 elementos distintos de cero, por lo que

V = [10 20 30 40 50 60 70 80] COL_INDEX = [ 0 1 1 3 2 3 4 5 ] ÍNDICE_DE_FILA = [ 0 2 4 7 8 ]

El conjunto se almacena como 21 entradas: 8 en V , 8 en COL_INDEX y 5 en ROW_INDEX .

• ROW_INDEX divide la matriz V en filas: (10, 20) (30, 40) (50, 60, 70) (80), indicando el índice de V (y COL_INDEX ) donde comienza y termina cada fila;
• COL_INDEX alinea los valores en las columnas: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Nótese que en este formato, el primer valor de ROW_INDEX siempre es cero y el último siempre es NNZ , por lo que resultan redundantes en cierto modo (aunque en lenguajes de programación donde la longitud de la matriz debe almacenarse explícitamente, NNZ no sería redundante). No obstante, esto evita la necesidad de gestionar un caso excepcional al calcular la longitud de cada fila, ya que garantiza que la fórmula ROW_INDEX[ i + 1] − ROW_INDEX[ i ] funcione para cualquier fila i . Además, el coste de memoria de este almacenamiento redundante probablemente sea insignificante para una matriz suficientemente grande.

Los formatos de matriz dispersa de Yale (antiguo y nuevo) son instancias del esquema CSR. El formato antiguo de Yale funciona exactamente como se describió anteriormente, con tres matrices; el nuevo formato combina ROW_INDEX y COL_INDEX en una sola matriz y maneja la diagonal de la matriz por separado. ^{[ 9 ]}

En el caso de las matrices de adyacencia lógicas , se puede omitir la matriz de datos, ya que la existencia de una entrada en la matriz de filas es suficiente para modelar una relación de adyacencia binaria.

Es probable que se le conozca como formato Yale porque fue propuesto en el informe de 1977 del paquete de matrices dispersas de Yale del Departamento de Ciencias de la Computación de la Universidad de Yale. ^{[ 10 ]}

CSC es similar a CSR excepto que los valores se leen primero por columna, se almacena un índice de fila para cada valor y se almacenan punteros de columna. Por ejemplo, CSC es (val, row_ind, col_ptr) , donde val es un arreglo de los valores no nulos de la matriz (de arriba a abajo y luego de izquierda a derecha); row_ind son los índices de fila correspondientes a los valores; y col_ptr es la lista de índices de val donde comienza cada columna. El nombre se basa en el hecho de que la información del índice de columna está comprimida en relación con el formato COO. Normalmente se utiliza otro formato (LIL, DOK, COO) para la construcción. Este formato es eficiente para operaciones aritméticas, segmentación de columnas y productos matriz-vector. Este es el formato tradicional para especificar una matriz dispersa en MATLAB (a través de la sparsefunción).