MATRICES DE TIPO SPARSE

[アタラクシア]

%% Matrices de tipo Sparse
%Esta demostración muestrea como al reordenar las filas y columnas de
una
%matriz S de tipo sparse se pueden ver afectados el tiempo y
almacenamiento
%requerido para una operación matricial como una factorización de S en
su
% descomposición Cholesky, S=L*L'.
%
% Copyright 1984-2007 The MathWorks, Inc.
% $Revisión: 5.18.4.5 $ $Date: 2007/06/20 23:23:15 $

%% Visualizando una Matriz Sparse
% Un diagrama SPY muestra los elementos diferentes de cero en una
matriz.
%
% Este diagrama spy muestra una matriz SPARSE definida simétrica
positiva
% derivada de una porción de la matriz de prueba Harwell-Boeing
"west0479",
% una matriz que describe las conexiones en un modelo de difracción de
% columna en una planta química.

load('west0479.mat')
A = west0479;
S = A * A' + speye(size(A));
pct = 100 / prod(size(A));

clf; spy(S), title('Matriz Sparse Simétrica A')
nz = nnz(S);
xlabel(sprintf('Elementos Diferentes de cero=%d (%.3f%%)',nz,nz*pct));

%% Computando el factor Cholesky
% Ahora vamos a computar el factor Cholesky L, en donde S=L*L'. Nótese
que
% L contiene MUCHOS más elementos diferentes de cero que S sin
factorizar,
% puesto que la computación de la factorización crea "rellenos" de
% elementos diferentes de cero. Esto ralentiza el algoritmo e
incrementa el
% coste de almacenamiento.

tic, L = chol(S)'; t(1) = toc;
spy(L), title('Descomposición Cholesky de S')
nc(1) = nnz(L);
xlabel(sprintf('Elementos diferentes de cero=%d (%.2f%%) Tiempo=%.2f
seg.',nc(1),nc(1)*pct,t(1)));

%% Reordenando Para acelerar el cálculo
% El reordenamiento de las filas y columnas de una matriz, puede ser
posible
% reducir la cantidad de relleno creado por la factorización,
reduciendo de
% tal modo el coste de tiempo y de almacenamiento.
%
% Ahora vamos a probar tres diferentes ordenamientos soportados por
MATLAB.
%
% * Inverso de Cuthill-McKee
% * Cuenta de Columna
% * Grado Mínimo

%% Usando el Inverso de Cuthill-McKee
% El comando SYMRCM usa el algoritmo de ordenamiento inverso Cuthill-
McKee
% para mover todos los elementos diferentes de cero cerca a la
diagonal,
% reduciendo el "Ancho de banda" de la matriz original.

p = symrcm(S);
spy(S(p,p)), title('S(p,p) Tras el ordenamiento Cuthill-McKee')
nz = nnz(S);
xlabel(sprintf('Elementos Diferentes de Cero=%d (%.3f%%)',nz,nz*pct));

%%
% El relleno producido por la factorización Cholesky es confinado a la
% banda, así que la factorización de la matriz reordenada toma menos
tiempo
% y menos almacenamiento.

tic, L = chol(S(p,p))'; t(2) = toc;
spy(L), title('chol(S(p,p)) Tras el Ordenamiento Cuthill McKee')
nc(2) = nnz(L);
xlabel(sprintf('Elementos Diferentes de Cero=%d (%.2f%%) tiempo=%.2f
seg.', nc(2),nc(2)*pct,t(2)));

%% Usando La Cuenta de Columna
% El comando COLPERM usa el algoritmo de reordenamiento de cuenta de
% columna para mover las filas y columnas con elementos diferentes de
cero
% hacia el final de la matriz.

q = colperm(S);
spy(S(q,q)), title('S(q,q) Tras el ordenamiento de cuenta de columna')
nz = nnz(S);
xlabel(sprintf('Elementos diferentes de cero=%d (%.3f%%)',nz,nz*pct));

%%
% Para este ejemplo, el ordenamiento cuenta de columna se hace para
reducir
% el tiempo y almacenamiento para la factorización Cholesky, pero ese
% comportamiento no puede ser esperado en general.

tic, L = chol(S(q,q))'; t(3) = toc;
spy(L), title('chol(S(q,q)) Tras el ordenamiento de Cuenta de
Columna')
nc(3) = nnz(L);
xlabel(sprintf('Elementos diferentes de cero=%d (%.2f%%) Tiempo=%.2f
seg.',nc(3),nc(3)*pct,t(3)));

%% Usando el Mínimo Grado
% El comando SYMAMD usa el algoritmo de mínimo grado aproximado (Una
% técnica Grafico-teórica de gran alcance) para producir largos
bloques de
% ceros en la matriz.

r = symamd(S);
spy(S(r,r)), title ('S(r,r) Tras el ordenamiento de mínimo grado')
nz = nnz(S);
xlabel(sprintf('Elementos diferentes de cero=%d (%.3f%%)',nz,nz*pct));

%%
% Los bloques de ceros producidos por el algoritmo del mínimo grado
son
% preservados durante la factorización Cholesky. Esto puede reducir
% significativamente el coste de tiempo y almacenamiento.

tic, L = chol(S(r,r))'; t(4) = toc;
spy(L), title('chol(S(r,r)) Tras el ordenamiento del mínimo grado')
nc(4) = nnz(L);
xlabel(sprintf('Elementos diferentes de cero=%d (%2f%%) Tiempo=%2f
seg.',nc(4),nc(4)*pct,t(4)));

%% Resumiendo Los Resultados

labels={'original','Cuthill-McKee','Cuenta Columna','Min Grado'};

subplot(2,1,1)
bar(nc*pct)
title('Elementos diferentes de cero Tras la Factorización Cholesky')
ylabel('Porcentaje');
set(gca,'xticklabel',labels)

subplot(2,1,2)
bar(t)
title('Tiempo para completar la Factorización Cholesky')
ylabel('Segundos');
set(gca,'xticklabel',labels)

% ________________________Traducido al español por Ataraxiainc

displayEndOfDemoMessage(mfilename)