RESEQUENCING TECHNIQUES FOR SOLVING LARGE SPARSE SYSTEMS / TÉCNICAS DE REORDENAÇÃO PARA SOLUÇÃO DE SISTEMAS ESPARSOS

AUTOR(ES)
DATA DE PUBLICAÇÃO

1995

RESUMO

Este trabalho apresenta técnicas de reordenação para minimização de banda, perfil e frente de malhas de elementos finitos. Um conceito unificado relacionando as malhas de elementos finitos, os grafos associados e as matrizes correspondentes é proposto. As informações geométricas, disponíveis nos programans de elemnetos finitos, são utilizadas para aumentar a eficiência dos algoritmos heurísticos. Com base nestas idéias, os algoritmos são classificados em topológicos, geométricos, híbridos e espectrais. Um Grafo de Elementos Finitos - Finite Element Graph (FEG)- é definido coo um grafo nodal(G), um garfo dual(G*) ou um grafo de comunicação(G.), associado a uma dada malha de elementos finitos. Os algoritmos topológicos mais utilizados na literatura técnica, tais como, Reverse- CuthiiMcKee (RCM), Collins, Gibbs-Poole-Stockmeyer(GPS), Gibbs-King (GK), Snay e Sloan, são inventigados detalhadamente. Em particular, o algoritmo de Collins é estendido para consideração de componentes não conexos nos grafos associados e a numeração é invertida para uma posterior redução do perfil das matrizer correspondentes. Essa nova versão é denominada Modified Reverse Collins (MRCollins). Um algoritmo puramente geométrico, denominado Coordinate Based Bandwidth and Profile Reduction (CBBPR), é apresentado. Um novo algoritmo híbrido (HybWP) para redução de frente e perfil é proposto. A matriz Laplaciana [L(G), L(G*) ou L (G.)], utilizada no estudo de propriedades espectrais de grafos, é construída a partir das relações usuais de adjacências entre vértices e arestas. Um algoritmo automático, baseado em propriedades espectrais de FEGs, é proposto para reordenação de nós e/ou elementos das malhas associadas. Este algoritmo, denominado Spectral FEG Resequencing (SFR), utiliza informações globais do grafo; não depende da escolha de um vértice pseudo- periférico; e não utiliza o conceito de estrutura de níveis. Um novo algoritmo espectral para determinação de vértices pseudo-periféricos em grafos também é proposto. Os algoritmos apresentados neste trabalho são implementados computacionalmente e testados utilizando- se diversos exemplos numéricos. Finalmente, conclusões são apresentadas e algumas sugestões para trabalhos futuros são propostas.

ASSUNTO(S)

minimizacao de banda matriz laplaciana laplacian matrix perfil frente profile spectral properties of a graph resequencing algorithms front matrizes esparsas bandwidth sparse matrices propriedades espectrais de grafos algoritmos de reordenacao

ACESSO AO ARTIGO

Documentos Relacionados