[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. / [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.

[ES] El procesado de señal sobre grafos es un campo emergente de técnicas que combinan conceptos de dos áreas muy consolidadas: el procesado de señal y la teoría de grafos. Desde la perspectiva del procesado de señal puede obtenerse una definición de la señal mucho más general asignando cada valor de la misma a un vértice de un grafo. Las señales convencionales pueden considerarse casos particulares en los que los valores de cada muestra se asignan a una cuadrícula uniforme (temporal o espacial). Desde la perspectiva de la teoría de grafos, se pueden definir nuevas transformaciones del grafo de forma que se extiendan los conceptos clásicos del procesado de la señal como el filtrado, la predicción y el análisis espectral. Además, el procesado de señales sobre grafos está encontrando nuevas aplicaciones en las áreas de detección y clasificación debido a su flexibilidad para modelar dependencias generales entre variables. En esta tesis se realizan nuevas contribuciones al procesado de señales sobre grafos. En primer lugar, se plantea el problema de estimación de la matriz Laplaciana asociada a un grafo, que determina la relación entre nodos. Los métodos convencionales se basan en la matriz de precisión, donde se asume implícitamente Gaussianidad. En esta tesis se proponen nuevos métodos para estimar la matriz Laplaciana a partir de las correlaciones parciales asumiendo respectivamente dos modelos no Gaussianos diferentes en el espacio de las observaciones: mezclas gaussianas y análisis de componentes independientes. Los métodos propuestos han sido probados con datos simulados y con datos reales en algunas aplicaciones biomédicas seleccionadas. Se demuestra que pueden obtenerse mejores estimaciones de la matriz Laplaciana con los nuevos métodos propuestos en los casos en que la Gaussianidad no es una suposición correcta. También se ha considerado la generación de señales sintéticas en escenarios donde la escasez de señales reales puede ser un problema. Los modelos sobre grafos permiten modelos de dependencia por pares más generales entre muestras de señal. Así, se propone un nuevo método basado en la Transformada de Fourier Compleja sobre Grafos y en el concepto de subrogación. Se ha aplicado en el desafiante problema del reconocimiento de gestos con las manos. Se ha demostrado que la extensión del conjunto de entrenamiento original con réplicas sustitutas generadas con los métodos sobre grafos, mejora significativamente la precisión del clasificador de gestos con las manos. / [CAT] El processament de senyal sobre grafs és un camp emergent de tècniques que combinen conceptes de dues àrees molt consolidades: el processament de senyal i la teoria de grafs. Des de la perspectiva del processament de senyal pot obtindre's una definició del senyal molt més general assignant cada valor de la mateixa a un vèrtex d'un graf. Els senyals convencionals poden considerar-se casos particulars en els quals els valors de la mostra s'assignen a una quadrícula uniforme (temporal o espacial). Des de la perspectiva de la teoria de grafs, es poden definir noves transformacions del graf de manera que s'estenguen els conceptes clàssics del processament del senyal com el filtrat, la predicció i l'anàlisi espectral. A més, el processament de senyals sobre grafs està trobant noves aplicacions en les àrees de detecció i classificació a causa de la seua flexibilitat per a modelar dependències generals entre variables. En aquesta tesi es donen noves contribucions al processament de senyals sobre grafs. En primer lloc, es planteja el problema d'estimació de la matriu Laplaciana associada a un graf, que determina la relació entre nodes. Els mètodes convencionals es basen en la matriu de precisió, on s'assumeix implícitament la gaussianitat. En aquesta tesi es proposen nous mètodes per a estimar la matriu Laplaciana a partir de les correlacions parcials assumint respectivament dos models no gaussians diferents en l'espai d'observació: mescles gaussianes i anàlisis de components independents. Els mètodes proposats han sigut provats amb dades simulades i amb dades reals en algunes aplicacions biomèdiques seleccionades. Es demostra que poden obtindre's millors estimacions de la matriu Laplaciana amb els nous mètodes proposats en els casos en què la gaussianitat no és una suposició correcta. També s'ha considerat el problema de generar senyals sintètics en escenaris on l'escassetat de senyals reals pot ser un problema. Els models sobre grafs permeten models de dependència per parells més generals entre mostres de senyal. Així, es proposa un nou mètode basat en la Transformada de Fourier Complexa sobre Grafs i en el concepte de subrogació. S'ha aplicat en el desafiador problema del reconeixement de gestos amb les mans. S'ha demostrat que l'extensió del conjunt d'entrenament original amb rèpliques substitutes generades amb mètodes sobre grafs, millora significativament la precisió del classificador de gestos amb les mans. / [EN] Graph signal processing appears as an emerging field of techniques that combine concepts from two highly consolidated areas: signal processing and graph theory. From the perspective of signal processing, it is possible to achieve a more general signal definition by assigning each value of the signal to a vertex of a graph. Conventional signals can be considered particular cases where the sample values are assigned to a uniform (temporal or spatial) grid. From the perspective of graph theory, new transformations of the graph can be defined in such a way that they extend the classical concepts of signal processing such as filtering, prediction and spectral analysis. Furthermore, graph signal processing is finding new applications in detection and classification areas due to its flexibility to model general dependencies between variables. In this thesis, new contributions are given to graph signal processing. Firstly, it is considered the problem of estimating the Laplacian matrix associated with a graph, which determines the relationship between nodes. Conventional methods are based on the precision matrix, where Gaussianity is implicitly assumed. In this thesis, new methods to estimate the Laplacian matrix from the partial correlations are proposed respectively assuming two different non-Gaussian models in the observation space: Gaussian Mixtures and Independent Component Analysis. The proposed methods have been tested with simulated data and with real data in some selected biomedical applications. It is demonstrate that better estimates of the Laplacian matrix can be obtained with the new proposed methods in cases where Gaussianity is not a correct assumption. The problem of generating synthetic signal in scenarios where real signals scarcity can be an issue has also been considered. Graph models allow more general pairwise dependence models between signal samples. Thus a new method based on the Complex Graph Fourier Transform and on the concept of subrogation is proposed. It has been applied in the challenging problem of hand gesture recognition. It has been demonstrated that extending the original training set with graph surrogate replicas, significantly improves the accuracy of the hand gesture classifier. / Belda Valls, J. (2022). Nuevas contribuciones a la teoría y aplicación del procesado de señal sobre grafos [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/191333