El algoritmo de Disección Unidireccional para mallas regulares

              © Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Rev.Acad.Canar.Cienc., VIII (Núm. 1), 135-142 (1996)
El algoritmo de Disección Unidireccional para
mallas regulares
P.R. Almeida Benítez •
U. Las Palmas de Gran Canaria
J.R. Franco Hrañas t
U. La Laguna
Resumen. En este artículo se conside"ra el algoritmo de Disección Unidireccional
para resolver sistemas lineales de ecuaciones con grafo en forma. de malla. Este algcr
ritmo fue diseñado originalmente por Alan Qeorge para resolver problemas de apli­caciones
de Elementos Finitos. Aquí se compara el modo habitual de reordenar los
nodos de los bloques con el reordenamiento obtenido al aplicar el algoritmo de Grado
Mínimo a cada bloque. La reducción en el efecto f ill - in es mayor que al aplicar los
algoritmos de Disección Anidada, Cuthill,McKee o Grado Mínimo.
Palabras Clave. Sistemas sparse, eliminación gaussiana, mallas de Elementos
Finitos.
1 Introducción.
Sea A una matriz simétrica definida positiva nxn. Se quiere resolver el sistema
de ecuaciones lineales
Ax=b
donde x y b son vectores columna de orden n y A es una matriz no singu­lar
de orden n. Si A es una matriz simétrica y definida positiva, entonces la
factorización de Cholesky es el mejor método para obtener la descomposición
triangular
A= LL'
donde L es una matriz triangular inferior. Finalmente, se resuelven los sistemas
triangulares Ly =by L'x =y.
Si A es densa, el número de multiplicaciones/divisiones necesarias para la
factorización de Cholesky es n3/6+0(n2). Si A es sparse, será posible ahorrar
tiempo y almacenamiento manipulando los ceros, y será muy ventajoso reducir
el efecto fil/ - in en la factorización de A.
Existen diferentes algoritmos que intentan minimizar el efecto fil/ - in du­raiite
la factorización. Unos lo consiguen mediante una minimización local de
•Departamento of Matemáticas
t Del?artamento de Análisis Matemático
135
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
dicho efecto fil/ - in. Son las estrategias de Markowitz (15], Grado Mínimo
(4], etc. Algunos intentan reducir el ancho de banda: Cuthill-McKee (2], King
(12], etc. Finalmente, otros intentan dividir el grafo de la matriz A en bloques
sin fil/ - in entre los diferentes bloques: Disección Unidireccional (8], Disección
Anidada (4], Go-Away (1], etc.
En el presente artículo se considera el algoritmo de Disección Unidirec­cional
para resolver sistemas de ecuaciones lineales con grafo en forma de malla,
comparando el modo habitual de reordenar los bloques con el reordenamiento
obtenido al aplicar el algoritmo de Grado Mínimo a cada bloque.
Las líneas generales de este artículo fueron expuestas en el XIV CEDY A - IV
Congreso de Matemática Aplicada, celebrado en Vic del 18 al 22 de Septiembre
de 1995.
2 El algoritmo de Disección Unidireccional
El algoritmo conocido como Disección Unidireccional fue diseñado por Alan
Georg¡! (7] para resolver problemas que aparecen en aplicaciones de Elementos
Finitos. La ventaja del algoritmo es que la demanda de almacenamiento es
generalmente menor que en otros algoritmos. Se verá que, con una adecuada
renumeración de los nodos de los bloques, este algoritmo permite obtener una
reducción sustancial del efecto fil/ - in con respecto a los algoritmos antes
mencionados.
La idea principal del algoritmo consiste en dividir el grafo o malla retirando
de él líneas verticales de nodos (llamadas separadores) que dividen el grafo
en bloques de aproximadamente el mismo tamaño. El método se basa en el
paradigma "divide y vencerás". Por ejemplo, si .el rectángulo de la figura 1 re­presenta
el grafo de la matriz de un sistema Ax = b y se toman tres separadores
81 , 82 y 83, el grafo queda dividido en cuatro bloques independientes: 8 1, 8 2,
8 3 y 8 4 , que se renumeran en primer lugar, comenzando por la última fila de
8 1 de izquierda a derecha.
81 81 82 82 8a 8a 84
Figura 1
136
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Finalmente, se renumeran los 'separadores S1 , S2 y S3 , de abajo arriba. La
matriz reordenada A tendrá el perfil de la zona cuadriculada de la figura 2.
Así, los posibles fil/ - ins occuren en el interior de esas zonas y las zonas
punteadas. Por otra parte, dichas zonas no son densas sino con perfil en banda.
B3
::lt!::t: ......... .
~ ........ ..
S3
.......... rii:tt
··· · ······~
Figura 2
Se considera una malla con m filas y 1 columnas (con N = mxl nodos) tal
que m ~ l. Si un elemento de A es distinto de cero, a;j f. O, entonces los nodos i
y j están conectados en las malla mediante una arista. Si se retiran u columnas
de la malla, ésta queda dividida en u+ 1 bloques independientes (u E N, 1 ~u).
La distancia ó entre separadores será:
ó = (1- u)/(u + 1)
y la matriz queda dividida en q2 submatrices, donde q = 2u + l.
Ejemplo. Sea la malla de la figura 3 (m=3, 1=8):
137
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
¡-¡¡1 lr-11¡16 r-r 2-- 5 8 11-14 17 20-23 !_! l J_J 118 L_L
Figura 3
Se toman los separadores S1 y S2 . Como u= 2:
ó = (8 - 2)/(2+ 1) = 2 .
donde ó es la distancia entre los separadores. He aquí la matriz reordenada,
donde los "o" representan los fil/ - in producidos en la eliminación gaussiana:
3 :r :r
:r 6 o :r
:r o 2 :r :r
:r :r 5 o :r
:r o 1 :r
:r :r 4
12 :r :r
:r 15 o :r
:r o 11 :r :r
:r :r 14 o :r
:r o 10 :r
:r :r 13
21 :r :r
:r 24 o :r
:r o 20 :r :r
:r :r 23 o :r
:r o 19 :r
:r :r 22
:r
o
o :r
o o
o o :r
:r
o :r
o :r o
o o o :r
o o :r o o
o o o o o :r
:r
o
o :r
o o
o o :r
o o o
xooooxooooo 9xoooo
:r 8 :r o o o
ox1lr•,oo
:r o o
:r
:r o o o
:r o
:r o o o o :r o o o o o o o o 18 :r o
:r o o
:r
Figura 4
138
:r o o o o o o :r 17 :r
:r o o o o o :r 16
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Como se puede apreciar, el factor L de la matriz ha sufrido 47 fil/ - ins.
3 Descripción del algoritmo
El algoritmo intenta encontrar un conjunto de separadores paralelos que dividan
. el grafo en un conjunto de bloques independientes.
Sea un grafo conexo G = (X,E). Un subconjunto de nodos Y C X es
un separador del grafo conexo G si la sección G(X - Y) es no conexa. Sea
N = IXI = mxl. Entonces las etapas del algoritmo serán:
Etapa 1 (Generar una estructura de niveles) Encontrar un nodo pseudo­periférico
x y generar la estructura de niveles enraizada en x:
L(x)={L;,L1 , .. .,L1}
Etapa 2 (Estimar 6) Calcular 6 = J 3'{13 . Este valor de 6 fue obtenido
por Alan George [8] basándose en experimentos numéricos y análisis de mallas
regulares al objeto de minimizar los costes de almacenamiento.
Etapa 3 (Encontrar separadores) Sea
j = [i6+ 0.51 i = 1, 2,. ..
donde [] es la parte entera de un número, y S = 0. Mientras j < 1 hacer:
3a) Elegir S; = {x E L;/Ady(x) n L;+1 :/: 0}.
3b) S +-Su S;.
3c) S +- i + 1 y j = [i6 + 0.5].
Etapa 4 (Definir los bloques) Sean Bk, k = 1,2,. . .,p- l, las componentes
conexas de la sección de grafo G(X - S). Sea Bp =S.
Etapa 5 (Numeración de los bloques) Se numera cada bloque Bk, k =
1, 2, .. ., p, consecutivamente como se indica en la figura l.
4 Renumeración interna de los bloques
Los nodos de cada bloque han sido renumerados fila por fila como se indica en
la figura l. Desde luego, el efecto f ill - in podría reducirse todavía más si se
renumeran los nodos atendiendo a su grado (número de conexiones en el grafo)
usando el algoritmo de Grado Mínimo. Se modificará la etapa 5 en el algoritmo
previo. Sea P = {B1 , B2, .. ., Bp}· Para cada bloque Bk, 1 :'.S k :'.S p- 1, de grafo
asociado G 0 = (Z, E) en P, el algoritmo básico será el siguiente:
Etapa 5a (Inicialización) i +- l.
139
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Etapa 5b (Selección del nodo de grado mínimo) En el grafo de eliminación
G;_1 se elige un nodo x de grado mínimo.
Etapa 5c (Transformación del grafo) Se forma el nuevo grafo de eliminación
G; eliminando el nodo x en G;-1.
Etapa 5d (Bucle/Parada) i +-- i + l. Si i > IZI, stop. en otro caso, volver a
etapa 5b. .
En la malla anterior resulta el ordenamiento siguiente:
X X
3 X X
X X 2 O O X
X o 4 O X
X O O 6 X
X X X 5
X O O
X O
X
10 X X
12 X X
X 13 O X
X 15 O X
xxoollx
X X X 14
X o o o
X o o o
X o
X o o
X o o
X
22
X
X X
24 X X
19
X
O X
21 O X
X
O X
O O X
X
X
o X
O X
O O X O O
ooooox
X
X
xxoo23x o o
X X X 20 O O X
1oxooo
o9xooo
xx8ooo
X O O O O O 16 O X
X O O O O O O 18 X
X O O O X X 17
Figura 5
Se observa que el número de fill-ins en el factor triangular L se ha reducido
de 47 a 36.
Se va a hacer una tabla resumen del efecto fill-in para distintos algoritmos,
Grado Mínimo (GM), Disección Unidireccional (DU), Disección Unidireccional
con reordenamiento interno de los bloques (DU(Re)), Disección Anidada (DA),
140
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Cuthill-McKee (CM) e Inverso de Cuthill-McKee (ICM):
Dimension Natural GM DU DU(Re) DA CM ICM
3x5 28 23 '20 13 16 15 14
4x4 27 26 24 14 18 22 22
5x5 64 81 59 48 51 50 49
6x6 125 191 117 94 98 95 95
7x7 210 356 198 152 159 161 160
lOxlO 619 1181 579 398 426 469 469
20x20 349~ 7506 3344 1998 2226 2735 2734
Tabla 1
5 Conclusiones
Se ha visto que un reordenamiento interno de los bloques en el algoritmo de
Disección Unidireccional redunda en una disminución del efecto fil/ - in. Esta
reducción es mayor que al aplicar los algoritmos de Cuthill-McKee, Inverso de
Cuthill-McKee o Disección Anidada a la malla. Desde luego, el Algoritmo de
Grado Mínimo produce un mayor fil/ - in y no es un buen algoritmo para este
tipo de mallas.
Por otra parte, suele ocurrir que aparece más de un nodo de grado rrúnimo en
la etapa 2 del algoritmo. Se ha resuelto el problema renumerando los nodos en el
orden generado por el algoritmo de Disección Unidireccional, v.g., de un modo
prácticamente arbitrario. Desde luego, la estrategia a seguir para resolver los
"empates" no es una cuestión trivial en muchos casos. Duff et al. [3] proponen
varias estrategias llegando a la conclusión de que es una cuestión sin resolver.
Una buena técnica podría ser renumerar en primer lugar aquellos nodos con
menor grado interno en cada ·bloque, pues un posible fil/ - in en el bloque
diagonal podría producir nuevos fil/ - ins en las matrices subdiagonales.
6 Referencias
[l] P. R. ALMEIDA BENITEZ y J. R. FRANCO BRAÑAS, The Go-Away
algorithm for Block Factorization of a Sparse Matrix. Course on algorithms for
Sparse Large Scale Linear Algebraic Systems. NATO ASI SERIES. Ed. Kluwer.
Londres. 1996. (To appear).
[2] E. CUTHILL, Severa! Strategies for Reducing the Bandwith of Matrices,
Papers of the Symposium on Sparse Matrices and Their Applications, IBM
Thomas J . Watson Research Center, New York, 1971.
[3] J .J . DONGARRA et al., Solving Linear Systems on Vector and Shared
Memory Computers, SIAM, Philadelphia, 1991.
141
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
[4) I.S. DUFF, A.M. ERISMAN and J.K. REID, Direct Methods for Sparse
Matrices, Monographs on Numerical Analysis, Oxford Press, Oxford, 1989.
[5) J .L. DE LA FUENTE O'CONNOR, Tecnologías Computacionales para
Sistemas de Ecuaciones, Optimización Lineal y Entera, Ed. Reverté, Barcelona,
1993.
[6) K.A. GALLIVAN et al., Parallel Algorithms for Matrix Computations,
SIAM, Philadelphia, 1991.
[7) A. GEORG E, Block Elimination ofFinite Elements Systems ofEquations,
The IBM Symposia Series, pp. 101-114, Plenum Press, New York , 1972.
(8) A. GEORG E, An Automatic One-Way Dissection Algorithm for Irregular
Finite Elements Problems, SIAM J. Num. Anal. 17, pp. 740-751, Philadelphia,
1980.
[9) A. GEORGE et al., Computer Solution of Large Sparse Positive Defined
Systems, Prentice-Hall, London, 1981.
[10) A. GEORGE and E. NG, Waterloo Sparse Matrix Package. User guide
for SPARSPAK-B. Research Report CS-84-37, Departament of Computer Sci­ence,
University of Waterloo, Ontario, Canada, 1984.
[11) A. GEORGE and E. NG, An Implementation of Gaussian Elimination
with Partial Pivoting for Sparse Systems, SIAM, J . Sci. Stat. Com. 6, pp.
390-409, Philadelphia, 1985.
[12) A. JENNINGS and J.J . MCKEOWN, Matrix Computation, Ed. John
Wiley and Sons, Chichester (U.K.), 1992.
[13) D.J. ROSE, R.E. TARJAN and J .S. LUEKER, Algorithmic aspects of
vertex elimination on graphs, SIAM, J . Comput., pp. 266-283, 1976.
[14) H.A.G. WIJSHOFF, Direct Methods for Solving Linear Systems, Papers
ofthe Large-Scale Scientific Parallel Computing Coutse, Abingdon (U .K.), 1992.
[15) Z. ZLATEV, Computational Methods for General Sparse Matrices, Klu­wer
Academic Publishers, London, 1991.
Recibido: 30 Diciembre 1996
142