Made available in DSpace on 2016-12-23T14:33:41Z (GMT). No. of bitstreams: 1 Dissertacao de Philippe Leal Freire dos Santos.pdf: 1222437 bytes, checksum: 0b5ab3d6e8b9f4b4640e53168b2d042d (MD5) Previous issue date: 2010-08-23 / In this work we investigated the use of concepts from Spectral Graph Theory (SGT) to support the construction of algorithms that solve the Graph Isomorphism Problem (GIP). Three theoretical results which consider information from the spectrum of the graphs and from the eigenvector centralities were presented. Furthermore, an algorithm for detection of graph isomorphism based on two of these results was proposed. Finally, we present the computational results comparing this algorithm with others from literature. / Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram apresentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura

In this thesis a known heuristic for decreasing a node's centrality scores while maintaining influence, called ROAM, is compared to a modified version specifically designed to decrease eigenvector centrality. The performances of these heuristics are also tested against the Shapley values of a cooperative game played over the considered network, where the game is such that influential nodes receive higher Shapley values. The modified heuristic performed at least as good as the original ROAM, and in some instances even better (especially when the terrorist network behind the World Trade Center attacks was considered). Both heuristics increased the influence score for a given targeted node when applied consecutively on the WTC network, and consequently the Shapley values increased as well. Therefore the Shapley value of the game considered in this thesis seems to be well suited for discovering individuals that are assumed to actively trying to evade social network analysis.

This dissertation presents the solution of difference equations and focuses on a method of difference equations solution with the aid of eigenvectors. The first part reminds the basic terms from area of difference equations such as dynamic of difference equations and linear difference equations of first order and higher order. Then the second section recalls also the system of difference equations including the fundamental matrix and general solution description. Afterthat, the method of solving the difference equations with a variation of constants and transform of scalar equations to the system are shown. The second part of the dissertation analyses some known algorithms and methods for the solution of linear difference equations. The Z-transform, its importance and usage for finding the solution of difference equation is recalled. Then the discrete analogue of Putzer's algorithm is mentioned because this algorithm was often used to check the results obtained by the newly described algorithm in further parts of this thesis. Also some ways of the system matrix power are stated. The next section then describes the principle of Weyr's method which is the basic point for further development of the theory including the presentation of the research results gained by Jiří Čermák in this area. The third part describes own solution of the difference equations system via eigenvectors based on the principle of Weyr's method for differential equations. The solution of system of linear homogeneous difference equtions with constant coefficients including the proof is presented and this solution is then extended to nonhomogeneous systems. Consequently to the theory, the influence of a nulity and the multiplicity of roots on the form of the solution is discussed. The last section of this part shows the implementation of the algorithm in Matlab program (for basic simpler cases) and its application to some cases of difference equations and systems with these equations. The final part of the thesis is more practical and it presents the usage of the designed algorithm and theory. Firstly, the algorithm is compared with Z-transform and the method of variation of constants and it is illustrated how to obtain the same results by using these three approaches. Then an example of current response solution in RLC circuit is demonstrated. The continuous case is solved and then the problem is transferred to discrete case and solved with the Z-transform and the method of eigenvectors. The obtained results are compared with the result of the continuous case.

No / A new approach for implementing QO-STBC and DHSTBC over OFDM for four, eight and sixteen transmitter antennas is presented, which eliminates interference from the detection matrix and improves performance by increasing the diversity order on the transmitter side. The proposed code promotes diversity gain in comparison with the STBC scheme, and also reduces Inter Symbol Interference.

In this project, various computational energy landscape methods were accelerated using graphics processing units (GPUs). Basin-hopping global optimisation was treated using a version of the limited-memory BFGS algorithm adapted for CUDA, in combination with GPU-acceleration of the potential calculation. The Lennard-Jones potential was implemented using CUDA, and an interface to the GPU-accelerated AMBER potential was constructed. These results were then extended to form the basis of a GPU-accelerated version of hybrid eigenvector-following. The doubly-nudged elastic band method was also accelerated using an interface to the potential calculation on GPU. Additionally, a local rigid body framework was adapted for GPU hardware. Tests were performed for eight biomolecules represented using the AMBER potential, ranging in size from 81 to 22\,811 atoms, and the effects of minimiser history size and local rigidification on the overall efficiency were analysed. Improvements relative to CPU performance of up to two orders of magnitude were obtained for the largest systems. These methods have been successfully applied to both biological systems and atomic clusters. An existing interface between a code for free energy basin-hopping and the SuiteSparse package for sparse Cholesky factorisation was refined, validated and tested. Tests were performed for both Lennard-Jones clusters and selected biomolecules represented using the AMBER potential. Significant acceleration of the vibrational frequency calculations was achieved, with negligible loss of accuracy, relative to the standard diagonalisation procedure. For the larger systems, exploiting sparsity reduces the computational cost by factors of 10 to 30. The acceleration of these computational energy landscape methods opens up the possibility of investigating much larger and more complex systems than previously accessible. A wide array of new applications are now computationally feasible.

Cette thèse s'articule autour d'une notion spectrale assez récente, appelée le spectre étendu des opérateurs. Dans la première partie nous fournissons des propriétés générales du spectre étendu d'un opérateur dans certains cas particuliers, tels que le cas de dimension finie et celui des opérateurs inversibles. Nous nous intéressons dans la deuxième partie à l'étude du spectre étendu de l'opérateur shift tronqué Su. En particulier, nous donnons une description complète des vecteurs propres étendus associes à chaque valeur propre étendue de Sb, ou b est un produit de Blaschke quelconque. Dans la troisième partie nous décrirons complètement le spectre étendu et les sous espaces propres étendus d'une classe d'opérateurs très importante : celle des opérateurs normaux. Nous commençons d'abord par la classe des opérateurs qui sont produits d'un opérateur positif par un autoadjoint. Ensuite, nous utilisons le théorème de Fuglede-Putnam pour déduire une description complète des valeurs et des vecteurs propres étendus des opérateurs normaux, en fonction de leur mesure spectrale. Dans la dernière partie, nous appliquons nos résultats des trois premières parties sur des exemples concrets. En particulier, nous traitons= le problème des sous espaces propres étendus des opérateurs définis dans un espace de dimension finie. Ensuite, nous montrons l'existence d'un opérateur compact quasinilpotent dont le spectre étendu est réduit au singleton {1}. Enfin, nous traitons deux opérateurs de Cesaro très importants dans les applications / This thesis is based on a relatively new spectral notion, called extended spectrum of operators. In the first part, we provide general properties of extended spectrum of an operator in some special cases, such as the case of finite dimension and the case of invertible operator. We focused in the second part on characterizing the extended spectrum of truncated shift operator Su. In particular, we give a complete description of the extended eigenvectors associated to each extended eigenvalue of Sb, where b is a Blaschke product. In the third part, we describe the extended spectrum and the extended eigenvectors of a very important class of operators , that is the normal operators. We first start by describing these last sets for the product of a positive and a self-adjoint operator which are both injective. After, we use the Fuglede-Putnam theorem to describe the same sets for normal operators, in terms of their spectral measure. In the last part, we apply our results from the last three parts on concrete examples. In particular, we address the problem of extended eigenvectors of operators defined in a finite dimension space. Next, we show the existence of a quasinilpotent compact operator whose extended spectrum is reduced to {1}. Finally, we study two Cesaro operators which are very important in applications

Least Squares Kinetic Upwind Method (LSKUM), a grid free method based on kinetic schemes has been gaining popularity over the conventional CFD methods for computation of inviscid and viscous compressible flows past complex configurations. The main reason for the growth of popularity of this method is its ability to work on any point distribution. The grid free methods do not require the grid for flow simulation, which is an essential requirement for all other conventional CFD methods. However, they do require point distribution or a cloud of points. Point generation is relatively simple and less time consuming to generate as compared to grid generation. There are various methods for point generation like an advancing front method, a quadtree based point generation method, a structured grid generator, an unstructured grid generator or a combination of above, etc. One of the easiest ways of point generation around complex geometries is to overlap the simple point distributions generated around individual constituent parts of the complex geometry. The least squares grid free method has been successfully used to solve a large number of flow problems over the years. However, it has been observed that some problems are still encountered while using this method on point distributions around complex configurations. Close analysis of the problems have revealed that bad connectivity of the nodes is the cause and this leads to bad connectivity related code divergence. The least squares (LS) grid free method called LSKUM involves discretization of the spatial derivatives using the least squares approach. The formulae for the spatial derivatives are obtained by minimizing the sum of the squares of the error, leading to a system of linear algebraic equations whose solution gives us the formulae for the spatial derivatives. The least squares matrix A for 1-D and 2-D cases respectively is given by (Refer PDF File for equation) The 1-D LS formula for the spatial derivatives is always well behaved in the sense that ∑∆xi2 can never become zero. In case of 2-D problems can arise. It is observed that the elements of the Ls matrix A are functions of the coordinate differentials of the nodes in the connectivity. The bad connectivity of a node thus can have an adverse effect on the nature of the LS matrices. There are various types of bad connectivities for a node like insufficient number of nodes in the connectivity, highly anisotropic distribution of nodes in the connectivity stencil, the nodes falling nearly on a line (or a plane in 3-D), etc. In case of multidimensions, the case of all nodes in a line will make the matrix A singular thereby making its inversion impossible. Also, an anisotropic distribution of nodes in the connectivity can make the matrix A highly illconditioned thus leading to either loss in accuracy or code divergence. To overcome this problem, the approach followed so far is to modify the connectivity by including more neighbours in the connectivity of the node. In this thesis, we have followed a different approach of using weights to alter the nature of the LS matrix A. (Refer PDF File for equation) The weighted LS formulae for the spatial derivatives in 1-D and 2-D respectively are are all positive. So we ask a question : Can we reduce the multidimensional LS formula for the derivatives to the 1-D type formula and make use of the advantages of 1-D type formula in multidimensions? Taking a closer look at the LS matrices, we observe that these are real and symmetric matrices with real eigenvalues and a real and distinct set of eigenvectors. The eigenvectors of these matrices are orthogonal. Along the eigendirections, the corresponding LS formulae reduce to the 1-D type formulae. But a problem now arises in combining the eigendirections along with upwinding. Upwinding, which in LS is done by stencil splitting, is essential to provide stability to the numerical scheme. It involves choosing a direction for enforcing upwinding. The stencil is split along the chosen direction. But it is not necessary that the chosen direction is along one of the eigendirections of the split stencil. Thus in general we will not be able to use the 1-D type formulae along the chosen direction. This difficulty has been overcome by the use of weights leading to WLSKUM-ED (Weighted Least Squares Kinetic Upwind Method using Eigendirections). In WLSKUM-ED weights are suitably chosen so that a chosen direction becomes an eigendirection of A(w). As a result, the multi-dimensional LS formulae reduce to 1-D type formulae along the eigendirections. All the advantages of the 1-D LS formuale can thus be made use of even in multi-dimensions. A very simple and novel way to calculate the positive weights, utilizing the coordinate differentials of the neighbouring nodes in the connectivity in 2-D and 3-D, has been developed for the purpose. This method is based on the fact that the summations of the coordinate differentials are of different signs (+ or -) in different quadrants or octants of the split stencil. It is shown that choice of suitable weights is equivalent to a suitable decomposition of vector space. The weights chosen either fully diagonalize the least squares matrix ie. decomposing the 3D vector space R3 as R3 = e1 + e2 + e3, where e1, e2and e3are the eigenvectors of A (w) or the weights make the chosen direction the eigendirection ie. decomposing the 3D vector space R3 as R3 = e1 + ( 2-D vector space R2). The positive weights not only prevent the denominator of the 1-D type LS formulae from going to zero, but also preserve the LED property of the least squares method. The WLSKUM-ED has been successfully applied to a large number of 2-D and 3-D test cases in various flow regimes for a variety of point distributions ranging from a simple cloud generated from a structured grid generator (shock reflection problem in 2-D and the supersonic flow past hemisphere in 3-D) to the multiple chimera clouds generated from multiple overlapping meshes (BI-NACA test case in 2-D and FAME cloud for M165 configuration in 3-D) thus demonstrating the robustness of the WLSKUM-ED solver. It must be noted that the second order acccurate computations using this method have been performed without the use of the limiters in all the flow regimes. No spurious oscillations and wiggles in the captured shocks have been observed, indicating the preservation of the LED property of the method even for 2ndorder accurate computations. The convergence acceleration of the WLSKUM-ED code has been achieved by the use of LUSGS method. The use of 1-D type formulae has simplified the application of LUSGS method in the grid-free framework. The advantage of the LUSGS method is that the evaluation and storage of the jacobian matrices can be eliminated by approximating the split flux jacobians in the implicit operator itself. Numerical results reveal the attainment of a speed up of four by using the LUSGS method as compared to the explicit time marching method. The 2-D WLSKUM-ED code has also been used to perform the internal flow computations. The internal flows are the flows which are confined within the boundaries. The inflow and the outflow boundaries have a significant effect on these flows. The accurate treatment of these boundary conditions is essential particularly if the flow condition at the outflow boundary is subsonic or transonic. The Kinetic Periodic Boundary Condition (KPBC) which has been developed to enable the single-passage (SP) flow computations to be performed in place of the multi-passage (MP) flow computations, utilizes the moment method strategy. The state update formula for the points at the periodic boundaries is identical to the state update formula for the interior points and can be easily extended to second order accuracy like the interior points. Numerical results have shown the successful reproduction of the MP flow computation results using the SP flow computations by the use of KPBC. The inflow and the outflow boundary conditions at the respective boundaries have been enforced by the use of Kinetic Outer Boundary Condition (KOBC). These boundary conditions have been validated by performing the flow computations for the 3rdtest case of the 4thstandard blade configuration of the turbine blade. The numerical results show a good comparison with the experimental results.

Gravity gradient tensor (GGT) data contains the second derivatives of the Earth’s gravitational potential in three orthogonal directions. GGT data can be measured either using land, airborne, marine or space platforms. In the last two decades, the applications of GGT data in hydrocarbon exploration, mineral exploration and structural geology have increased considerably. This work focuses on developing new interpretation techniques for GGT data as well as pseudo-gravity gradient tensor (PGGT) derived from measured magnetic field. The applications of developed methods are demonstrated on a GGT data set from the Vredefort impact structure, South Africa and a magnetic data set from the Särna area, west central Sweden. The eigenvectors of the symmetric GGT can be used to estimate the position of the causative body as well as its strike direction. For a given measurement point, the eigenvector corresponding to the maximum eigenvalue points approximately toward the center of mass of the source body. For quasi 2D structures, the strike direction of the source can be estimated from the direction of the eigenvectors corresponding to the smallest eigenvalues. The same properties of GGT are valid for the pseudo-gravity gradient tensor (PGGT) derived from magnetic field data assuming that the magnetization direction is known. The analytic signal concept is applied to GGT data in three dimensions. Three analytic signal functions are introduced along x-, y- and z-directions which are called directional analytic signals. The directional analytic signals are homogenous and satisfy Euler’s homogeneity equation. Euler deconvolution of directional analytic signals can be used to locate causative bodies. The structural index of the gravity field is automatically identified from solving three Euler equations derived from the GGT for a set of data points located within a square window with adjustable size. For 2D causative bodies with geometry striking in the y-direction, the measured gxz and gzz components of GGT can be jointly inverted for estimating the parameters of infinite dike and geological contact models. Once the strike direction of 2D causative body is estimated, the measured components can be transformed into the strike coordinate system. The GGT data within a set of square windows for both infinite dike and geological contact models are deconvolved and the best model is chosen based on the smallest data fit error. / Felaktigt tryckt som Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology 730

La compréhension des processus écologiques qui sous-tendent l’assemblage des communautés végétales et la coexistence des espèces est un objectif central en écologie. Ces processus sont potentiellement nombreux et de natures contrastées. Ainsi, la composition d’une communauté de plantes dépend de processus déterministes liés aux conditions environnementales abiotiques (climat, conditions physiques et chimiques du sol, lumière) et d’interactions biotiques complexes, positives (facilitation, symbioses) comme négatives (compétition, prédation, pathogènes). En outre, les communautés sont influencées par des processus stochastiques (capacité de dispersion limitée, dérive écologique). Si les mécanismes à l’origine de ces processus sont très différents, ils ont néanmoins en commun la génération de motifs (patterns) spatiaux de distribution d’espèces dans les communautés. L’analyse de la structure spatiale des communautés permet ainsi une étude indirecte des processus régissant les communautés. La nature complexe de ces patterns spatiaux a mené au développement de nombreuses méthodes statistiques de détection et de description de patterns. Les méthodes basées sur des vecteurs propres spatiaux sont parmi les plus puissantes et précises pour détecter des patterns complexes et multi-échelles. Ces vecteurs propres, utilisés comme prédicteurs spatiaux, peuvent être combinés à un ensemble de variables environnementales dans un cadre de partition de variation. Celui-ci permet, en théorie, de démêler les effets uniques et l’effet conjoint des variables environnementales et spatiales sur la variation de composition d’une communauté. Il mène ainsi à une quantification de l’action des processus déterministes et des processus stochastiques sur l’assemblage de la communauté. Néanmoins, je montre dans cette thèse qu’un certain flou méthodologique concernant deux étapes déterminantes des analyses basées sur les vecteurs propres spatiaux a mené une proportion élevée d’études à utiliser ces méthodes de manière sous-optimale, voire fortement biaisée. Ceci compromet la fiabilité des patterns spatiaux détectés et des processus écologiques inférés. Une autre limitation de ce cadre d’analyse concerne la fraction de la partition de variation décrivant l’effet environnemental spatialement structurés qu’aucune méthode ne permet de tester.Cette thèse présente des solutions non biaisées, puissantes et précises à ces différentes limitations méthodologiques et permet d’élargir le cadre de l’inférence de processus écologique à partir de patterns spatiaux de communautés. Les différentes étapes d’amélioration de ces méthodes ont également été illustrées dans la thèse au travers de trois cas d’études fournis par deux communautés d’arbres tropicale et tempérée et une communauté de champignons symbiotiques des arbres. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Rivers and their catchments are under mounting pressure from direct channel modification, intensification of land use, and from a legacy of decades of channelisation. Recent legislation, in the form of the EU Water Framework Directive, places a greater emphasis on the management of water bodies as holistic systems, and includes the explicit consideration of hydromorphological quality, which describes the hydrologic and geomorphic elements of river habitats. These are defined specifically as hydrological regime, river continuity and river morphology. This appreciates that sediment and flow regimes, along with the channel structure, provides the 'template' on which stream ecological structure and function is built. Invertebrate fauna contribute significantly to the biodiversity of rivers, and often form the basis of monitoring river health. However much of the fundamental ecological knowledge base on the response of invertebrates to hydromorphological change needed to make informed decisions and accurate predictions, is either lacking, inadequate or contradictory. This thesis addresses some of the key potential shortcomings in recent bio-assessment that others have alluded to, but which have rarely been explored in the context of direct channel manipulations. By using two case studies of, realignment in a natural upland catchment, and flood protection engineering in an urban stream, this study investigates the sensitivity of hydromorphological impact assessment methods that rely on biodiversity patterns of benthic riverfly (Ephemeroptera, Plecoptera and Trichoptera) larva. This work employed widely used biomonitoring indices of benthic riverfly larva abundance, species richness, alpha and beta diversity, and community composition, applied over a range of spatial scales, in combination with spatially contemporaneous physical habitat data, to describe and explain community changes in response to disturbance, and patterns of natural variation. The effects of restoration were investigated using a high degree of sample replication within channels and across the wider catchment, as well as contrasting spring and autumn seasons. To assess change in a small urban channel, approaches that explicitly consider spatial elements of community data, using spatial eigenvectors analysis, were applied to spatially detrend community data and directly investigate spatial patterns. Restoration of the Rottal Burn was found to be successful in restoring habitat diversity and geomorphic processes, and in turn increasing reach scale species richness and beta diversity through the gradual arrival of rare and specialist taxa into novel habitats. Catchment scale replication revealed high variation in diversity indices of modified and undisturbed streams, and a strong temporal pattern related to antecedent flow conditions. Channels with greater habitat heterogeneity were able to maintain high gamma diversity during times of high flow stress by providing a number of low flow refuges along their length. The urban Brox Burn had surprisingly high riverfly richness and diversity driven by small scale hydraulic heterogeneity, created by bed roughness resulting in a range of microhabitats. Riverfly community responses to direct channel dredging could not be detected by measurements of average richness and diversity, however distinct changes were seen in gamma diversity, the identity of community members and their arrangement among sample patches. Impacts of sediment pollution release due to engineering were short lived and apparently had little detrimental impact on biodiversity. Strong spatial patterns of community assembly on the stream bed were uncovered, relating to longitudinal, edge and patchy patterns. Significant habitat drivers of community composition were confounded by high amounts of spatial autocorrelation, especially hydraulic variables. Due to the strongly physical and spatial nature of hydromorphological disturbance, turnover of species between sample locations at a range of scales, and the spatial arrangement of habitats and communities is of more use for detecting these types of subtle changes compared to mean richness or diversity. These findings have implications for the targeting of resources for monitoring of restoration, or engineering disturbances, in order to be sensitive to hydromorphological change. Efforts should target the main area of natural variability within the system, either replicating sampling in time or space to distinguish effects of impact. Spatial patterns, measures of beta diversity and species identity can be better exploited to identify systems with functioning geomorphological processes. Channel typologies proved misleading, and quantification of habitat and selection of control sites using multiple pre-defined criteria should be carried out. Studies of restoration operations and engineering impacts provide considerable opportunities for advancing our knowledge of the mechanisms that drive community response under a range of conditions to improve impact detection.