[en] RESEQUENCING TECHNIQUES FOR SOLVING LARGE SPARSE SYSTEMS

IVAN FABIO MOTA DE MENEZES

[pt] TÉCNICAS DE REORDENAÇÃO PARA SOLUÇÃO DE SISTEMAS ESPARSOS

dc.contributor	MARCELO GATTASS
dc.creator	IVAN FABIO MOTA DE MENEZES
dc.date	2002-07-26
dc.date.accessioned	2022-09-21T21:40:13Z
dc.date.available	2022-09-21T21:40:13Z
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=2779@1
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=2779@2
dc.identifier	http://doi.org/10.17771/PUCRio.acad.2779
dc.identifier.uri	https://hdl.handle.net/20.500.12032/41935
dc.description	[pt] 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.
dc.description	[en] This work presents resequencing techniques for minimizing bandwidth, profile and wavefront of finite element meshes. A unified approach relating a finite element mesh, its associated graphs, and the corresponding matrices is proposed. The geometrical information available from conventional finite element program is also used in order to improve heuristic algorithms. Following these ideas, the algorithms are classified here as a nodal graph (G), a dual graph (G) or a communication graph (G.) associated with a generic finie element mesh. The most widely used topological algorithms, such as Reverse-Cuthill-McKee (RCM), Collins, Gibbs-Poole-Stockmeyer (GPS), Gibbs-King (GK), Snay, and Sloan, are investigated in detail. In particular, the Collins algorithm is extended to consider nonconnected components in associated graph and the ordering provide by this algorithm is reverted for improved profile. This new version is called Modified Reverse Collins (MRCollins). A purely geometrical algorithm, called Coordinate Based Bandwidth and Profile Reduction (CBBPR), is presented. A new hybrid reordering algorithm (HybWP) for wavefront and profile reduction is proposed. The Laplacian matrix [L(G), L(G) or L(G.)], used for the study of spectral properties of an FEG, is constructed from usual vertex and edge conectivities of a graph. An automatic algorithm, based on spectral properties of an FEG, is proposed to reorder the nodes and/or elements of the associated finite element meshes. The new algorithm, called Spectral FEG Resequencing (SFR), uses global information in the graph; it does not depende on a pseudoperipheral vertex in the resequencing process; and it does not use any kind of level structure of the graph. A new spectral algorithm for finding pseudoperipheral vertices in graphs is also proposed. The algorithmpresented herein are computationally implemented and tested against several numerical examples. Finally, conclusions are drawn and directions for futue work are given.
dc.language	pt
dc.publisher	MAXWELL
dc.subject	[pt] MATRIZES ESPARSAS
dc.subject	[pt] FRENTE
dc.subject	[pt] PROPRIEDADES ESPECTRAIS DE GRAFOS
dc.subject	[pt] MATRIZ LAPLACIANA
dc.subject	[pt] PERFIL
dc.subject	[pt] MINIMIZACAO DE BANDA
dc.subject	[pt] ALGORITMOS DE REORDENACAO
dc.subject	[en] SPARSE MATRICES
dc.subject	[en] FRONT
dc.subject	[en] SPECTRAL PROPERTIES OF A GRAPH
dc.subject	[en] LAPLACIAN MATRIX
dc.subject	[en] PROFILE
dc.subject	[en] BANDWIDTH
dc.subject	[en] RESEQUENCING ALGORITHMS
dc.title	[en] RESEQUENCING TECHNIQUES FOR SOLVING LARGE SPARSE SYSTEMS
dc.title	[pt] TÉCNICAS DE REORDENAÇÃO PARA SOLUÇÃO DE SISTEMAS ESPARSOS
dc.type	TEXTO

Files in this item

Files	Size	Format	View
There are no files associated with this item.

This item appears in the following Collection(s)

Documentos - PUC-RIO

Show simple item record