`symrcm`

Ordenação de Cuthill-McKee reversa que reduz a largura de banda de uma matriz esparsa.

Categoria: Mathematics > Sparse Matrices

Sintaxe

p = symrcm(S)

Retorna um vetor de permutação p tal que S(p,p) tenha largura de banda menor.

Descrição

O método numera os nós do grafo da matriz em largura, partindo de um nó distante do centro, e depois inverte a ordem. Linhas e colunas ligadas ficam próximas, e os não nulos se reúnem perto da diagonal. Uma banda mais estreita significa menos preenchimento em fatorações de Cholesky ou LU em banda, e um produto matriz-vetor mais amigável ao cache.

Aplique-a simetricamente, S(p,p), para manter simétrica uma matriz simétrica.

Argumentos de entrada

S: Matriz esparsa quadrada, tratada como simétrica pelo seu padrão.

Argumentos de saída

p: Vetor linha, uma permutação de 1:size(S,1).

Exemplo

Reordenando uma matriz

S = sparse([1 0 0 1; 0 1 1 0; 0 1 1 0; 1 0 0 1]);
p = symrcm(S)
full(S(p, p))

Saída

p = 1×4

     2     3     1     4
ans = 4×4

     1     1     0     0
     1     1     0     0
     0     0     1     1
     0     0     1     1

Veja também

colperm etree spy symbfact