ISSN 2317-3297
Aplicação do Algoritmo de Cuthill-McKee em Matrizes de
Hodge para o Método da Esparsificação Recursiva
Bruno F.C. da Silva,
Glauciléia M.C. Magalhães,
José Lucas P. Luiz,
Universidade Federal dos Vales do Jequitinhonha e Mucuri - UFVJM
Licenciatura em Matemática
E-mail: [email protected], [email protected], [email protected]
Alex Sander de Moura
Universidade Federal de Juiz de Fora - UFJF
Programa de Pós-Graduação Engenharia Elétrica, UFMG
Rodney Rezende Saldanha,
Élson José da Silva
Universidade Federal de Minas Gerais - UFMG
Departamento de Engenharia Elétrica
Palavras-chave: Método Numérico, Sistemas lineares esparsos, Esparsificação recursiva, Matriz de Hodge, Algoritmo de Cuthill-McKee
Resumo: Neste trabalho combina-se o método da esparsificação recursiva com o algoritmo de
Cuthill-McKee para obter uma aproximação esparsa para a inversa de uma classe de matrizes
esparsas denominadas matrizes de Hodge.
1
Introdução
A solução de sistemas lineares esparsos de alta ordem está inserido em vários ramos da ciência,
como por exemplo a engenharia. Por conseguinte, tem havido um grande esforço para resolver
ou apresentar soluções aproximadas de tais sistemas de forma eficiente.
Em [3] é apresentado uma técnica de esparsificação da inversa da matriz de Hodge pelo
particionamento recursivo da matriz em blocos. A ideia fundamental é aproximar as submatrizes
por matrizes esparsas durante o processo de inversão por blocos.
Neste paper será mostrado que a utilização do algoritmo de Cuthill-McKee [2] sobre as
matrizes de Hodge pode diminuir de uma maneira considerável o tempo de processamento para
esparsificação recursiva.
2
O método da Esparsificação Recursiva
A técnica de Esparsificação Recursiva consiste no particionamento recursivo desta matriz em
blocos e na aproximação das submatrizes por matrizes esparsas durante a inversão por blocos.
O método de esparsificação recursiva da inversa da matriz de Hodge é baseada na seguinte
fórmula de inversão por bloco:
[
]
Q−1
Xi
−1
i
Di−1 =
(1)
XTi
Si
−1 e
onde D−1
0 =M
T
Qi = Ai − Bi D−1
i Bi
−1
Xi = −Q−1
i Bi Di
Si =
D−1
i
−
T
D−1
i Bi Xi
14
(2)
ISSN 2317-3297
As expressões em 1 e 2 surgem a partir do particionamento de uma matriz que é descrito da
seguinte maneira:
[
]
Ai B i
Di−1 =
.
(3)
BT
Di
i
Note que a inversão da matriz D0 de ordem n × n se reduz a inversão de uma matriz D1
de ordem (n − q × n − q) e uma matriz Q1 de ordem (q × q), onde 0 < q < n. A fórmula de
inversão pode ser aplicada recursivamente na matriz D1 , levando a uma sequência de tamanho
decrescente de matrizes.
M = D0 , D1 , D2 , . . . , Dk
(4)
onde
k = ⌊logq/n (1/n)⌋
(5)
e Di é o bloco de Di−1 , para i = 1, 2, . . . , k, tal que a inversa M−1 é obtida pelas substituições
sucessivas através da sequência
−1
−1
−1
−1
D−1
k , Dk−1 , . . . , D1 , D0 = M
(6)
As matrizes em 10 podem ser aproximadas por matrizes esparsas, para se obter uma sequência
de matrizes esparsas
−1
−1
−1
D−1
(7)
ks , D(k−1) , . . . , D0s = Ms
s
para aproximar a sequência descrita em 10.
Após cada inversão das matrizes em 10, a respectiva matriz D−1
k é esparsificada para uma
matriz D−1
de
maneira
que
os
coeficiente
fora
da
diagonal
da
matriz
D−1
ks
k = [dij ] são zerados
quando
|di̸=j | ≤ r min diag D−1
(8)
k onde 0 < r < 1 é o parâmetro threshold.
3
Algoritmo de Cuthill-McKee
Dada uma matriz M = (mi,j ), de dimensões n × n, define-se largura de banda como sendo:
β = max|i − j|, mi, j ̸= 0
(9)
O objetivo do Algoritmo de Cuthill-Mckee é diminuir a largura de banda da matriz (β). Para
isso ele usa uma prática muito comum em Álgebra Linear, a Permutação de Matrizes.
A ideia do algoritmo é encontrar e efetuar uma permutação em M de forma que as entradas
não nulas se aproximem da diagonal. Para encontrar tal permutação ele percorre todas as
entradas da matriz verificando as não nulas e armazenado os valores i e j de sua posição numa
matriz unidimensional que é gerada durante o processo, esses valores representam os nós de
um grafo gerado pela matriz, que posteriormente será percorrido partindo sempre dos nós que
possuem menos ligações, gerando assim a permutação que será aplicada em M.




M=


1
0
0
3
2
0
2
1
0
8
0
9
3
0
6
4
0
0
4
0
1
4
7
0
5











M =


89:;
=⇒ ?>=<
4
?>=<
/ 89:;
1
>=<
/ ?89:;
5
89:;
?>=<
2
>=<
/ ?89:;
3
′
4
4
0
0
0
3
1
2
0
0
0
1
5
4
7
0
0
8
2
1
0
0
6
9
3




 (10)


Ao combinar o método da esparsificação recursiva com o algoritmo de Cuthill-Mckee observase uma redução considerável do tempo de processamento. Isso decorre da necessidade de menos
inversão de blocos, sendo que o algoritmo faz com que os blocos Bi e BTi (3) transformem-se em
matrizes com pouquı́ssimos elementos não nulos, assim como pode ser observado na matriz de
Hodge (figura 1) e em (10), onde foi aplicada uma permutação q = {4, 1, 5, 2, 3} na matriz M .
15
ISSN 2317-3297
Figura 1: (a) Matriz de Hodge convencional. (b) Matriz de Hodge tratada pelo algorı́timo Cuthill-Mckee.
4
Resultados
Nesta seção, compararemos o tempo de processamento computacional na aplicação da diagonalização de Cuthill-Mckee com o método da Esparsificação Recursiva.
Para se mostrar a redução do tempo de processamento devido a aplicação da diagonalização
de Cuthill-McKee, é fixado o parâmetro threshold em r = 1 × 10−5 e comparamos o tempo de
processamento do método da esparsificação recursiva com e sem a aplicação da diagonalização
da matriz, para matrizes de Hodge de ordem n × n, com n variando entre 50.000 a 75.000.
Tamanho da matriz
n
50.000
55.000
60.000
65.000
70.000
75.000
CM
(s)
17,58
21,70
29,27
42,42
396,41
853,08
ER
(s)
28,85
46,48
76,99
422,87
1002,4
1513,9
Speedup
CM/ER
0,6094
0,4667
0,3815
0,1003
0,3955
0,5635
Tabela 1: Tempo de Computação: Cuthill-Mckee (CM) X Esparsificação Recursiva(ER)
Tabela (1) mostra os resultados obtidos neste experimento, percebe-se uma redução significativa no tempo de processamento pela aplicação da diagonalização. Destacamos que para uma
matriz de ordem 65.000 × 65.000 obtivemos um redução de 90% no tempo de processamento.
5
Conclusão
Nesse trabalho mostra-se uma redução expressiva no tempo de processamento para o método da
Esparsificação Recursiva com o uso do algoritmo de Cuthill-Mckee devido ao fato de se gerar após
a diagonalização da matriz blocos quase-nulos o que proporciona a diminuição das operações.
Referências
[1] A. Bossavit, Computational Electromagnetism: variational formulation, complementarity,
edge elements, Academic Press, San Diego,1994.
[2] A. George, J. Liu, Computer Solution of Large Sparse Positive Definite Systems, PrenticeHall, 1981.
[3] A. S. Moura, R. R. Saldanha, E. J. Silva, A. C. Lisboa, W. G. Facco, N. Z. Lima, A
Recursive Sparsification of the Inverse Hodge Matrix, Magnetics, IEEE Transactions on vol
48,pp 611-614,2012.
16