A novel parallel block-based anisotropic adaptive mesh refinement (AMR) technique for multi-block body-fitted grids is proposed and described. Rather than adopting the more usual isotropic approach to mesh refinement, an anisotropic refinement procedure is proposed which allows refinement of grid blocks in each coordinate direction in an independent fashion. This allows for more efficient and accurate treatment of narrow layers and/or discontinuities which occur, for example, in the boundary and mixing layers of viscous flows, and in regions of strong non-linear wave interactions with shocks. The anisotropic AMR technique is implemented within an existing finite-volume framework, which encompasses both explicit and implicit solution methods, and is capable of performing calculations with second- and higher-order spatial accuracy. To clearly demonstrate the feasibility of the proposed technique, it is applied to the unsteady and steady-state solutions of both the advection diffusion equation, as well as the Euler equations, in two space dimensions.

É de conhecimento geral que, em alguns casos, as classes são espectralmente muito similares e que não é possível separá-las usando dados convencionais em baixa dimensionalidade. Entretanto, estas classes podem ser separáveis com um alto grau de acurácia em espaço de alta dimensão. Por outro lado, classificação de dados em alta dimensionalidade pode se tornar um problema para classificadores paramétricos, como o Máxima Verossimilhança Gaussiana (MVG). Um grande número de variáveis que caracteriza as imagens hiperespectrais resulta em um grande número de parâmetros a serem estimados e, geralmente, tem-se um número limitado de amostras de treinamento disponíveis. Essa condição causa o fenômeno de Hughes que consiste na gradual degradação da acurácia com o aumento da dimensionalidade dos dados. Neste contexto, desperta o interesse a utilização de classificadores não-paramétricos, como é o caso de Support Vector Machines (SVM). Nesta dissertação é analisado o desempenho do classificador SVM quando aplicado a imagens hiperespectrais de sensoriamento remoto. Inicialmente os conceitos teóricos referentes à SVM são revisados e discutidos. Em seguida, uma série de experimentos usando dados AVIRIS são realizados usando diferentes configurações para o classificador. Os dados cobrem uma área de teste da Purdue University e apresenta classes de culturas agrícolas espectralmente muito similares. A acurácia produzida na classificação por diferentes kernels são investigadas em função da dimensionalidade dos dados e comparadas com as obtidas com o classificador MVG. Como SVM é aplicado a um par de classes por vez, desenvolveu-se um classificador multi-estágio estruturado em forma de árvore binária para lidar como problema multi-classe. Em cada nó, a seleção do par de classes mais separáveis é feita pelo critério distância de Bhattacharyya. Tais classes darão origem aos nós descendentes e serão responsáveis por definir a função de decisão SVM. Repete-se este procedimento em todos os nós da árvore, até que reste apenas uma classe por nó, nos chamados nós terminais. Os softwares necessários foram desenvolvidos em ambiente MATLAB e são apresentados na dissertação. Os resultados obtidos nos experimentos permitem concluir que SVM é uma abordagem alternativa válida e eficaz para classificação de imagens hiperespectrais de sensoriamento remoto. / This dissertation deals with the application of Support Vector Machines (SVM) to the classification of remote sensing high-dimensional image data. It is well known that in many cases classes that are spectrally very similar and thus not separable when using the more conventional low-dimensional data, can nevertheless be separated with an high degree of accuracy in high dimensional spaces. Classification of high-dimensional image data can, however, become a challenging problem for parametric classifiers such as the well-known Gaussian Maximum Likelihood. A large number of variables produce an also large number of parameters to be estimated from a generally limited number of training samples. This condition causes the Hughes phenomenon which consists in a gradual degradation of the accuracy as the data dimensionality increases beyond a certain value. Non-parametric classifiers present the advantage of being less sensitive to this dimensionality problem. SVM has been receiving a great deal of attention from the international community as an efficient classifier. In this dissertation it is analyzed the performance of SVM when applied to remote sensing hyper-spectral image data. Initially the more theoretical concepts related to SVM are reviewed and discussed. Next, a series of experiments using AVIRIS image data are performed, using different configurations for the classifier. The data covers a test area established by Purdue University and presents a number of classes (agricultural fields) which are spectrally very similar to each other. The classification accuracy produced by different kernels is investigated as a function of the data dimensionality and compared with the one yielded by the well-known Gaussian Maximum Likelihood classifier. As SVM apply to a pair of classes at a time, a multi-stage classifier structured as a binary tree was developed to deal with the multi-class problem. The tree classifier is initially defined by selecting at each node the most separable pair of classes by using the Bhattacharyya distance as a criterion. These two classes will then be used to define the two descending nodes and the corresponding SVM decision function. This operation is performed at every node across the tree, until the terminal nodes are reached. The required software was developed in MATLAB environment and is also presented in this dissertation.

É de conhecimento geral que, em alguns casos, as classes são espectralmente muito similares e que não é possível separá-las usando dados convencionais em baixa dimensionalidade. Entretanto, estas classes podem ser separáveis com um alto grau de acurácia em espaço de alta dimensão. Por outro lado, classificação de dados em alta dimensionalidade pode se tornar um problema para classificadores paramétricos, como o Máxima Verossimilhança Gaussiana (MVG). Um grande número de variáveis que caracteriza as imagens hiperespectrais resulta em um grande número de parâmetros a serem estimados e, geralmente, tem-se um número limitado de amostras de treinamento disponíveis. Essa condição causa o fenômeno de Hughes que consiste na gradual degradação da acurácia com o aumento da dimensionalidade dos dados. Neste contexto, desperta o interesse a utilização de classificadores não-paramétricos, como é o caso de Support Vector Machines (SVM). Nesta dissertação é analisado o desempenho do classificador SVM quando aplicado a imagens hiperespectrais de sensoriamento remoto. Inicialmente os conceitos teóricos referentes à SVM são revisados e discutidos. Em seguida, uma série de experimentos usando dados AVIRIS são realizados usando diferentes configurações para o classificador. Os dados cobrem uma área de teste da Purdue University e apresenta classes de culturas agrícolas espectralmente muito similares. A acurácia produzida na classificação por diferentes kernels são investigadas em função da dimensionalidade dos dados e comparadas com as obtidas com o classificador MVG. Como SVM é aplicado a um par de classes por vez, desenvolveu-se um classificador multi-estágio estruturado em forma de árvore binária para lidar como problema multi-classe. Em cada nó, a seleção do par de classes mais separáveis é feita pelo critério distância de Bhattacharyya. Tais classes darão origem aos nós descendentes e serão responsáveis por definir a função de decisão SVM. Repete-se este procedimento em todos os nós da árvore, até que reste apenas uma classe por nó, nos chamados nós terminais. Os softwares necessários foram desenvolvidos em ambiente MATLAB e são apresentados na dissertação. Os resultados obtidos nos experimentos permitem concluir que SVM é uma abordagem alternativa válida e eficaz para classificação de imagens hiperespectrais de sensoriamento remoto. / This dissertation deals with the application of Support Vector Machines (SVM) to the classification of remote sensing high-dimensional image data. It is well known that in many cases classes that are spectrally very similar and thus not separable when using the more conventional low-dimensional data, can nevertheless be separated with an high degree of accuracy in high dimensional spaces. Classification of high-dimensional image data can, however, become a challenging problem for parametric classifiers such as the well-known Gaussian Maximum Likelihood. A large number of variables produce an also large number of parameters to be estimated from a generally limited number of training samples. This condition causes the Hughes phenomenon which consists in a gradual degradation of the accuracy as the data dimensionality increases beyond a certain value. Non-parametric classifiers present the advantage of being less sensitive to this dimensionality problem. SVM has been receiving a great deal of attention from the international community as an efficient classifier. In this dissertation it is analyzed the performance of SVM when applied to remote sensing hyper-spectral image data. Initially the more theoretical concepts related to SVM are reviewed and discussed. Next, a series of experiments using AVIRIS image data are performed, using different configurations for the classifier. The data covers a test area established by Purdue University and presents a number of classes (agricultural fields) which are spectrally very similar to each other. The classification accuracy produced by different kernels is investigated as a function of the data dimensionality and compared with the one yielded by the well-known Gaussian Maximum Likelihood classifier. As SVM apply to a pair of classes at a time, a multi-stage classifier structured as a binary tree was developed to deal with the multi-class problem. The tree classifier is initially defined by selecting at each node the most separable pair of classes by using the Bhattacharyya distance as a criterion. These two classes will then be used to define the two descending nodes and the corresponding SVM decision function. This operation is performed at every node across the tree, until the terminal nodes are reached. The required software was developed in MATLAB environment and is also presented in this dissertation.

É de conhecimento geral que, em alguns casos, as classes são espectralmente muito similares e que não é possível separá-las usando dados convencionais em baixa dimensionalidade. Entretanto, estas classes podem ser separáveis com um alto grau de acurácia em espaço de alta dimensão. Por outro lado, classificação de dados em alta dimensionalidade pode se tornar um problema para classificadores paramétricos, como o Máxima Verossimilhança Gaussiana (MVG). Um grande número de variáveis que caracteriza as imagens hiperespectrais resulta em um grande número de parâmetros a serem estimados e, geralmente, tem-se um número limitado de amostras de treinamento disponíveis. Essa condição causa o fenômeno de Hughes que consiste na gradual degradação da acurácia com o aumento da dimensionalidade dos dados. Neste contexto, desperta o interesse a utilização de classificadores não-paramétricos, como é o caso de Support Vector Machines (SVM). Nesta dissertação é analisado o desempenho do classificador SVM quando aplicado a imagens hiperespectrais de sensoriamento remoto. Inicialmente os conceitos teóricos referentes à SVM são revisados e discutidos. Em seguida, uma série de experimentos usando dados AVIRIS são realizados usando diferentes configurações para o classificador. Os dados cobrem uma área de teste da Purdue University e apresenta classes de culturas agrícolas espectralmente muito similares. A acurácia produzida na classificação por diferentes kernels são investigadas em função da dimensionalidade dos dados e comparadas com as obtidas com o classificador MVG. Como SVM é aplicado a um par de classes por vez, desenvolveu-se um classificador multi-estágio estruturado em forma de árvore binária para lidar como problema multi-classe. Em cada nó, a seleção do par de classes mais separáveis é feita pelo critério distância de Bhattacharyya. Tais classes darão origem aos nós descendentes e serão responsáveis por definir a função de decisão SVM. Repete-se este procedimento em todos os nós da árvore, até que reste apenas uma classe por nó, nos chamados nós terminais. Os softwares necessários foram desenvolvidos em ambiente MATLAB e são apresentados na dissertação. Os resultados obtidos nos experimentos permitem concluir que SVM é uma abordagem alternativa válida e eficaz para classificação de imagens hiperespectrais de sensoriamento remoto. / This dissertation deals with the application of Support Vector Machines (SVM) to the classification of remote sensing high-dimensional image data. It is well known that in many cases classes that are spectrally very similar and thus not separable when using the more conventional low-dimensional data, can nevertheless be separated with an high degree of accuracy in high dimensional spaces. Classification of high-dimensional image data can, however, become a challenging problem for parametric classifiers such as the well-known Gaussian Maximum Likelihood. A large number of variables produce an also large number of parameters to be estimated from a generally limited number of training samples. This condition causes the Hughes phenomenon which consists in a gradual degradation of the accuracy as the data dimensionality increases beyond a certain value. Non-parametric classifiers present the advantage of being less sensitive to this dimensionality problem. SVM has been receiving a great deal of attention from the international community as an efficient classifier. In this dissertation it is analyzed the performance of SVM when applied to remote sensing hyper-spectral image data. Initially the more theoretical concepts related to SVM are reviewed and discussed. Next, a series of experiments using AVIRIS image data are performed, using different configurations for the classifier. The data covers a test area established by Purdue University and presents a number of classes (agricultural fields) which are spectrally very similar to each other. The classification accuracy produced by different kernels is investigated as a function of the data dimensionality and compared with the one yielded by the well-known Gaussian Maximum Likelihood classifier. As SVM apply to a pair of classes at a time, a multi-stage classifier structured as a binary tree was developed to deal with the multi-class problem. The tree classifier is initially defined by selecting at each node the most separable pair of classes by using the Bhattacharyya distance as a criterion. These two classes will then be used to define the two descending nodes and the corresponding SVM decision function. This operation is performed at every node across the tree, until the terminal nodes are reached. The required software was developed in MATLAB environment and is also presented in this dissertation.

In this thesis we study the isoperimetric problem on trees and graphs with bounded treewidth. Let G = (V,E) be a finite, simple and undirected graph. For let δ(S,G)= {(u,v) ε E : u ε S and v ε V – S }be the edge boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the edge isoperimetric value of G at I be defined as be(i,G)= mins v;|s|= i | δ(S,G)|. For S V, let φ(S,G) = {u ε V – S : ,such that be the vertex boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the vertex isoperimetric value of G at I be defined as bv(i,G)= The edge isoperimetric peak of G is defined as be(G) =. Similarly the vertex isoperimetric peak of G is defined as bv(G)= .The problem of determining a lower bound for the vertex isoperimetric peak in complete k-ary trees of depth d,Tdkwas recently considered in[32]. In the first part of this thesis we provide lower bounds for the edge and vertex isoperimetric peaks in complete k-ary trees which improve those in[32]. Our results are then generalized to arbitrary (rooted)trees. Let i be an integer where . For each i define the connected edge isoperimetric value and the connected vertex isoperimetric value of G at i as follows: is connected and is connected A meta-Fibonacci sequence is given by the reccurence a(n)= a(x1(n)+ a1′(n-1))+ a(x2(n)+ a2′(n -2)), where xi: Z+ → Z+ , i =1,2, is a linear function of n and ai′(j)= a(j) or ai′(j)= -a(j), for i=1,2. Sequences belonging to this class have been well studied but in general their properties remain intriguing. In the second part of the thesis we show an interesting connection between the problem of determining and certain meta-Fibonacci sequences. In the third part of the thesis we study the problem of determining be and bv algorithmically for certain special classes of graphs. Definition 0.1. A tree decomposition of a graph G = (V,E) is a pair where I is an index set, is a collection of subsets of V and T is a tree whose node set is I such that the following conditions are satisfied: (For mathematical equations pl see the pdf file)

A three-dimensional, parallel, anisotropic, block-based, adaptive mesh refinement (AMR) algorithm is proposed and described for the solution of fluid flows on body-fitted, multi-block, hexahedral meshes. Refinement and de-refinement in any grid block computational direction, or combination of directions, allows the mesh to rapidly adapt to anisotropic flow features such as shocks, boundary layers, or flame fronts, common to complex flow physics. Anisotropic refinements and an efficient and highly scalable parallel implementation lead to a potential for significant reduction in computational cost as compared to a more typical isotropic approach. Unstructured root-block topology allows for greater flexibility in the treatment of complex geometries. The AMR algorithm is coupled with an upwind finite-volume scheme for the solution of the Euler equations governing inviscid, compressible, gaseous flow. Steady-state and time varying, three-dimensional, flow problems are investigated for various geometries, including the cubed-sphere mesh.

A three-dimensional, parallel, anisotropic, block-based, adaptive mesh refinement (AMR) algorithm is proposed and described for the solution of fluid flows on body-fitted, multi-block, hexahedral meshes. Refinement and de-refinement in any grid block computational direction, or combination of directions, allows the mesh to rapidly adapt to anisotropic flow features such as shocks, boundary layers, or flame fronts, common to complex flow physics. Anisotropic refinements and an efficient and highly scalable parallel implementation lead to a potential for significant reduction in computational cost as compared to a more typical isotropic approach. Unstructured root-block topology allows for greater flexibility in the treatment of complex geometries. The AMR algorithm is coupled with an upwind finite-volume scheme for the solution of the Euler equations governing inviscid, compressible, gaseous flow. Steady-state and time varying, three-dimensional, flow problems are investigated for various geometries, including the cubed-sphere mesh.

Monte Carlo simulations are embarrassingly parallel in nature, so having a parallel and efficient random number generator becomes crucial. To have a parallel generator with uncorrelated processors, parallelization methods are implemented together with a binary tree mapping. Although, this method has considerable advantages, because of the constraints arising from the binary tree structure, a situation defined as problem of falling off the tree occurs. In this thesis, a new spawning method that is based on binary tree traversal and new spawn processor appointment is proposed to use when falling off the tree problem is encountered. With this method, it is seen that, spawning operation becomes more costly but the independency of parallel processors is guaranteed. In Monte Carlo simulations, random number generation time should be unperceivable when compared with the execution time of the whole simulation. That is why / linear congruential generators with Mersenne prime moduli are used. In highly branching Monte Carlo simulations, cost of parameterization also gains importance and it becomes reasonable to consider other types of primes or other parallelization methods that provide different balance between parameterization cost and random number generation cost. With this idea in mind, in this thesis, for improving performance of linear congruential generators, two approaches are proposed. First one is using Sophie-Germain primes as moduli and second one is using a hybrid method combining both parameterization and splitting techniques. Performance consequences of Sophie-Germain primes over Mersenne primes are shown through graphics. It is observed that for some cases proposed approaches have better performance consequences.

The goal of this thesis has been to implement a hardware architecture for FPGA that calculates the fast Fourier transform (FFT) of a signal using one million samples. The FFT has been designed using a single-delay feedback architecture withrotators and butterflies, including a three-stage rotator with one million rotation angles. The design has been implemented onto a single FPGA and has a throughput of 233 Msamples/s. The calculated FFT has high accuracy with a signal to quantization noise ratio (SQNR) of 95.6 dB.

>Magister Scientiae - MSc / This dissertation studies the computation methods of pricing of Asian options. Asian options are options in which the underlying variable is the average price over a period of time. Because of this, Asian options have a lower volatility and this render them cheaper relative to their European counterparts. Asian options belong to the so-called path-dependent derivatives; they are among the most difficult to price and hedge both analytically and numerically. In practice, it is only discrete Asian options that are traded, however continuous Asian options are used for studying purposes. Several approaches have been proposed in the literature, including Monte Carlo simulations, tree-based methods, Taylor’s expansion, partial differential equations, and analytical ap- proximations among others. When using partial differential equations for pricing of continuous time Asian options, the high dimensionality is problematic. In this dissertation we focus on the discrete time methods. We start off by explaining the binomial tree method, and our last chapter presents the very exciting and relatively simple method of Tsao and Huang, using Taylor approximations. The main papers that are used in this dissertation are articles by Jan Vecer (2001); LCG Rogers (1995); Eric Benhamou (2001); Gianluca Fusai (2007); Kamizono, Kariya and Nakatsuma (2006) and Tsao and Huang (2007). The author has provided computations, including graphs and tables dispersed over the different chapters, to demonstrate the utility of the methods. We observe various parameters of influence such as correlation, volatility, strike, etc. A further contribution by the author of this dissertation is, in particular, in Chapter 5, in the presentation of the work of Tsao et al. Here we have provided slightly more detailed explanations and again some further computational tables.