Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Reordenación de matrices dispersas

Este ejemplo muestra cómo reordenar las filas y columnas de una matriz dispersa puede influir en los requisitos de velocidad y almacenamiento de una operación matricial.

Visualizando una matriz dispersa

Una gráfica muestra los elementos distintos de cero en una matriz.spy

Esta trama de espionaje muestra una matriz definida simétrica positiva dispersa derivada de una porción de la matriz de prueba de Harwell-Boeing.west0479 Esta matriz describe las conexiones en un modelo de una columna de difracción en una planta química.

load west0479.mat A = west0479; S = A * A' + speye(size(A)); pct = 100 / numel(A);  spy(S) title('A Sparse Symmetric Matrix') nz = nnz(S); xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

Calculando el factor Cholesky

Calcule el factor Cholesky, donde.LS = L*L' Tenga en cuenta que contiene más elementos distintos de cero que el no factorizado, porque el cálculo de la factorización de Cholesky crea nonceros.LmanySfill-in Estos valores de relleno ralentizan el algoritmo y aumentan el costo de almacenamiento.

L = chol(S,'lower'); spy(L) title('Cholesky Decomposition of S') nc(1) = nnz(L); xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(1),nc(1)*pct));

Reordenar para acelerar el cálculo

Reordenando las filas y columnas de una matriz, es posible reducir la cantidad de relleno que crea la factorización, reduciendo así el tiempo y el costo de almacenamiento.

Tres reordenamientos diferentes soportados por MATLAB® son:

  • Reverse Cuthill-McKee

  • El recuento de columnas

  • Grado mínimo

Pruebe los efectos de estas reordenaciones de matriz dispersa en la matriz.west0479

Reordenar 1: Reverse Cuthill-McKee

El comando utiliza el algoritmo de reordenación de Cuthill-McKee inverso para mover todos los elementos distintos de cero más cerca de la diagonal, reduciendo el ancho de banda de la matriz original.symrcm

p = symrcm(S); spy(S(p,p)) title('S(p,p) After Cuthill-McKee Ordering') nz = nnz(S); xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

El relleno producido por factorización Cholesky se limita a la banda, por lo que factorizar la matriz reordenada toma menos tiempo y menos almacenamiento.

L = chol(S(p,p),'lower'); spy(L) title('chol(S(p,p)) After Cuthill-McKee Ordering') nc(2) = nnz(L); xlabel(sprintf('Nonzeros = %d (%.2f%%)', nc(2),nc(2)*pct));

Reordenar 2: recuento de columnas

El comando utiliza el algoritmo de reordenación de recuento de columnas para mover filas y columnas con un recuento más alto distinto de cero hacia el final de la matriz.colperm

q = colperm(S); spy(S(q,q)) title('S(q,q) After Column Count Ordering') nz = nnz(S); xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

Para esta matriz, el orden de recuento de columnas se produce para reducir el tiempo y el almacenamiento de la factorización de Cholesky, pero este comportamiento no está garantizado en general.

L = chol(S(q,q),'lower'); spy(L) title('chol(S(q,q)) After Column Count Ordering') nc(3) = nnz(L); xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(3),nc(3)*pct));

Reordenar 3: grado mínimo

El comando utiliza el algoritmo de grado mínimo aproximado (una poderosa técnica de teoría de grafos) para producir grandes bloques de ceros en la matriz.symamd

r = symamd(S); spy(S(r,r)) title('S(r,r) After Minimum Degree Ordering') nz = nnz(S); xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

La factorización Cholesky preserva los bloques de ceros producidos por el algoritmo de grado mínimo. Esta estructura puede reducir significativamente los costos de tiempo y almacenamiento.

L = chol(S(r,r),'lower'); spy(L) title('chol(S(r,r)) After Minimum Degree Ordering') nc(4) = nnz(L); xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(4),nc(4)*pct));

Resumiendo los resultados

Este gráfico de barras resume los efectos de reordenar la matriz antes de realizar la factorización de Cholesky. Mientras que la factorización Cholesky de la matriz original tenía alrededor del 13% de sus elementos como nonceros, el uso reduce esa densidad a sólo alrededor del 4%.symamd

labels = {'Original','Cuthill-McKee','Column Count','Min Degree'}; bar(nc*pct) title('Nonzeros After Cholesky Factorization') ylabel('Percent'); ax = gca; ax.XTickLabel = labels; ax.XTickLabelRotation = -45;

Consulte también

| | | | |