O objetivo primordial desse trabalho está concentrado no estudo de Curvas NURBS (B-spline Racional N˜ao-Uniforme). A literatura em português sobre NURBS é escassa, pouco difundida e os textos e artigos existentes tendem a ser rigorosos, longos e teóricos. Assim, o presente estudo está direcionado para os conceitos matemáticos de NURBS, para o qual foi utilizado uma ferramenta chamada DesignMentor com a finalidade de testar os algoritmos desses conceitos. NURBS são funções paramétricas que podem representar qualquer tipo de curva. NURBS são usadas em computação gráfica na indústria de CAD/CAM e estão sendo consideradas um padrão para criar e representar objetos complexos (indústria automobilística, aviação e embarcação). As ferramentas de criação gráfica mais sofisticadas provêem uma interface para usar NURBS, que são flexíveis suficiente para projetar uma grande variedade de formas. Hoje é possível verificar o uso expandido de NURBS, modelando objetos para as artes visuais, arte e escultura; também estão sendo usados para modelar cenas para aplicações de realidade virtual. NURBS trabalha bem em modelagem 3D, permitindo facilidade para manipular e controlar vértices, controlar curvatura e suavidade de contornos. NURBS provêm uma base matemática, unificada para representar formas analíticas e livres além de manter exatidão e independência de resolução matemática.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-04-12T15:10:12Z No. of bitstreams: 1 2016_JeremiasMoreiraGomes.pdf: 12777273 bytes, checksum: f29c6daa63ea19fb36aa50a23bb3350e (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-04-12T18:41:21Z (GMT) No. of bitstreams: 1 2016_JeremiasMoreiraGomes.pdf: 12777273 bytes, checksum: f29c6daa63ea19fb36aa50a23bb3350e (MD5) / Made available in DSpace on 2016-04-12T18:41:21Z (GMT). No. of bitstreams: 1 2016_JeremiasMoreiraGomes.pdf: 12777273 bytes, checksum: f29c6daa63ea19fb36aa50a23bb3350e (MD5) / A execução eficiente de algoritmos de processamento de imagens é uma área ativa da Bioinformática. Uma das classes de algoritmos em processamento de imagens ou de padrão de computação comum nessa área é a Irregular Wavefront Propagation Pattern (IWPP). Nessa classe, elementos propagam informações para seus vizinhos em forma de ondas de propagação. Esse padrão de propagação resulta em acessos a dados e expansões irregulares. Por essa característica irregular, implementações paralelas atuais dessa classe de algoritmos necessitam de operações atômicas, o que acaba sendo muito custoso e também inviabiliza a implementação por meio de instruções Single Instruction, Multiple Data (SIMD) na arquitetura Many Integrated Core (MIC), que são fundamentais para atingir alto desempenho nessa arquitetura. O objetivo deste trabalho é reprojetar o algoritmo Irregular Wavefront Propagation Pattern, de forma a possibilitar sua eficiente execução em processadores com arquitetura Many Integrated Core que utilizem instruções SIMD. Neste trabalho, utilizando o Intel® Xeon Phi™, foram implementadas uma versão vetorizada, apresentando ganhos de até 5:63 em relação à versão não-vetorizada; uma versão paralela utilizando fila First In, First Out (FIFO) cuja escalabilidade demonstrou-se boa com speedups em torno de 55 em relação à um núcleo do coprocessador; uma versão utilizando fila de prioridades cuja velocidade foi de 1:62 mais veloz que a versão mais rápida em GPU conhecida na literatura, e uma versão cooperativa entre processadores heterogêneos que permitem processar imagens que ultrapassem a capacidade de memória do Intel® Xeon Phi™, e também possibilita a utilização de múltiplos dispositivos na execução do algoritmo. ________________________________________________________________________________________________ ABSTRACT / The efficient execution of image processing algorithms is an active area of Bioinformatics. In image processing, one of the classes of algorithms or computing pattern that works with irregular data structures is the Irregular Wavefront Propagation Pattern (IWPP). In this class, elements propagate information to neighbors in the form of wave propagation. This propagation results in irregular access to data and expansions. Due to this irregularity, current implementations of this class of algorithms requires atomic operations, which is very costly and also restrains implementations with Single Instruction, Multiple Data (SIMD) instructions in Many Integrated Core (MIC) architectures, which are critical to attain high performance on this processor. The objective of this study is to redesign the Irregular Wavefront Propagation Pattern algorithm in order to enable the efficient execution on processors with Many Integrated Core architecture using SIMD instructions. In this work, using the Intel® Xeon Phi™ coprocessor, we have implemented a vector version of IWPP with up to 5:63 gains on non-vectored version, a parallel version using First In, First Out (FIFO) queue that attained speedup up to 55 as compared to the single core version on the coprocessor, a version using priority queue whose performance was 1:62 better than the fastest version of GPU based implementation available in the literature, and a cooperative version between heterogeneous processors that allow to process images bigger than the Intel® Xeon Phi™ memory and also provides a way to utilize all the available devices in the computation.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-04-20T13:39:42Z No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-05-30T17:25:56Z (GMT) No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Made available in DSpace on 2016-05-30T17:25:56Z (GMT). No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Translocações são usadas para mensurar a distância evolutiva entre espécies. Do ponto de vista biológico dois tipos de genomas tem recebido atenção: genomas com e sem sinal. Ao considerar genomas com sinal, computar a distância mínima de translocações é linear enquanto que o caso sem sinal é NP-difícil. Propõem-se algoritmos genéticos (AGs) para resolver o problema de distância de translocação entre genomas sem sinal. A abordagem, consiste em utilizar uma população composta por indivíduos representando genomas com sinal obtidos de um genoma sem sinal provido como entrada. A solução de cada indivíduo é também uma solução admissível para o genoma dado. A função de aptidão utilizada, que é a distância para genomas com sinal, é computada linearmente com um algoritmo proposto por Bergeron et al. O AG baseado nessa abordagem foi aprimorado com duas técnicas de otimização: memética e aprendizagem baseada em oposição. Além disso, foram propostas paralelizações do AG memético buscando diminuir o tempo de processamento assim como melhorar a precisão. A qualidade dos resultados foi validada utilizando uma implementação de um algoritmo de raio de aproximação 1.5+" recentemente proposto por Cui et al. Experimentos foram realizados tomando como entrada genomas sintéticos e gerados a partir de dados biológicos. Os AGs forneceram melhores resultados que o algoritmo de controle de qualidade. As paralelizações apresentaram melhoras tanto no tempo de execução quanto na precisão dos resultados. Utilizou-se o teste de hipóteses de Wilcoxon a fim de verificar a significância estatística das melhorias fornecidas pelos AGs aprimorados em relação àquelas fornecidas pelo AG básico. Desta análise foi possível identificar que o AG memético provê resultados diferentes (melhores) que o AG básico, e que este último e o AG com aprendizagem baseada em oposição não apresentam nenhuma diferença significativa. O teste foi também aplicado para comparar as soluções das paralelizações confirmando que existem aprimoramentos dos resultados comparados com o AG memético. _______________________________________________________________________________________________ ABSTRACT / Translocations are used to measure the evolutionary distance between species. From a biological point of view two types of genomes have received attention: signed and unsigned genomes. When considering signed genomes, the problem can be solved in linear time, while, in the case of unsigned genomes the problem was shown to be NP-hard. Genetic algorithms (GAs) are proposed to solve the translocation distance problem between unsigned genomes. The approach consists in using a population composed of individuals representing signed genomes obtained from a given unsigned genome provided as input. The solution of each individual is also an admissible solution to the given genome. The fitness function used, which is the distance for signed genome, is computed linearly with an algorithm proposed by Bergeron et al. The GA based on this approach has been enhanced with two optimization techniques: memetic and opposition based learning. Also, parallelizations of the GA embedded with memetic were proposed seeking to improve both running time as the accuracy of results. The quality of the results was verified using an implementation of a 1.5+"-approximation algorithm recently proposed by Cui et al. Experiments were performed taking as input synthetic genomes and genomes generated from biological data. The GAs provided better results than the quality control algorithm. The parallelizations showed improvements both regarding runtime as well as accuracy. A statistical analysis based on the Wilcoxon test was performed to check if the improvements in the solutions provided by enhanced GAs compared to those provided by the basic GA have some significance. This analysis can identify that the GA embedded with the technical memetic provides different (better) results than GA and that the results provided by the GA embedded with opposition based learning presents no significant difference. The test was also performed to compare the solutions of the parallelizations confirming that there are improvements of the results regarding the GA embedded memetic.

A presente dissertação aborda pesquisas recentes sobre dois tópicos distintos da Matemática. Não é a primeira vez que as conexões entre geometria e álgebra são frutíferas, mas é somente agora que as idéias geométricas estão sendo aplicadas efetivamente na fatoração de polinômios, um tema puramente algébrico. Mais especificamente, estudamos a decomposição de politopos e suas aplicações na fatoração de polinômios. Começamos apresentando construções de politopos integralmente indecomponíveis que levam a critérios de irredutibilidade de polinômios. Estudamos detalhadamente algoritmos para a decomposição de politopos, sempre ilustrados com exemplos e comentários sobre suas aplicações. Terminamos apresentando um algoritmo desenvolvido por Fatima Salem, Shuhong Gao e Alan Lauder, que fatora polinômios bivariados a partir da decomposição do seu politopo de Newton associado. Esse algoritmo é um marco nessa área já que traduz, pela primeira vez, de forma eficiente, idéias geométricas para a fatoração polinomial, usando uma técnica similar ao levantamento de Hensel. / The present work deals with recent research about two distinct mathematical topics. It is not the first time that connections between geometry and algebra are fruitful, but it is only now that geometric ideas are being applied effectively in polynomial factorization, a purely algebraic theme. More specifically we study the decomposition of polytopes and their applications on polynomial factorization. We begin studying construction of indecomposable polytopes which give many irreducibility criteria polynomial. We study thoroughly algorithms for decomposition of polytopes, always illustrated with examples and comments about their applications. We finish presenting an algorithm developed by Fatima Salem, Shuhong Gao and Alan Lauder for factoring bivariate polynomials from the decomposition of the Newton polytope associated. This algorithm is a mark land in the field since it translate, for the first time, effectivelly, geometric ideas for polynomial factorization using a technic similar to Hensel lifting.

A presente dissertação aborda pesquisas recentes sobre dois tópicos distintos da Matemática. Não é a primeira vez que as conexões entre geometria e álgebra são frutíferas, mas é somente agora que as idéias geométricas estão sendo aplicadas efetivamente na fatoração de polinômios, um tema puramente algébrico. Mais especificamente, estudamos a decomposição de politopos e suas aplicações na fatoração de polinômios. Começamos apresentando construções de politopos integralmente indecomponíveis que levam a critérios de irredutibilidade de polinômios. Estudamos detalhadamente algoritmos para a decomposição de politopos, sempre ilustrados com exemplos e comentários sobre suas aplicações. Terminamos apresentando um algoritmo desenvolvido por Fatima Salem, Shuhong Gao e Alan Lauder, que fatora polinômios bivariados a partir da decomposição do seu politopo de Newton associado. Esse algoritmo é um marco nessa área já que traduz, pela primeira vez, de forma eficiente, idéias geométricas para a fatoração polinomial, usando uma técnica similar ao levantamento de Hensel. / The present work deals with recent research about two distinct mathematical topics. It is not the first time that connections between geometry and algebra are fruitful, but it is only now that geometric ideas are being applied effectively in polynomial factorization, a purely algebraic theme. More specifically we study the decomposition of polytopes and their applications on polynomial factorization. We begin studying construction of indecomposable polytopes which give many irreducibility criteria polynomial. We study thoroughly algorithms for decomposition of polytopes, always illustrated with examples and comments about their applications. We finish presenting an algorithm developed by Fatima Salem, Shuhong Gao and Alan Lauder for factoring bivariate polynomials from the decomposition of the Newton polytope associated. This algorithm is a mark land in the field since it translate, for the first time, effectivelly, geometric ideas for polynomial factorization using a technic similar to Hensel lifting.

O objetivo primordial desse trabalho está concentrado no estudo de Curvas NURBS (B-spline Racional N˜ao-Uniforme). A literatura em português sobre NURBS é escassa, pouco difundida e os textos e artigos existentes tendem a ser rigorosos, longos e teóricos. Assim, o presente estudo está direcionado para os conceitos matemáticos de NURBS, para o qual foi utilizado uma ferramenta chamada DesignMentor com a finalidade de testar os algoritmos desses conceitos. NURBS são funções paramétricas que podem representar qualquer tipo de curva. NURBS são usadas em computação gráfica na indústria de CAD/CAM e estão sendo consideradas um padrão para criar e representar objetos complexos (indústria automobilística, aviação e embarcação). As ferramentas de criação gráfica mais sofisticadas provêem uma interface para usar NURBS, que são flexíveis suficiente para projetar uma grande variedade de formas. Hoje é possível verificar o uso expandido de NURBS, modelando objetos para as artes visuais, arte e escultura; também estão sendo usados para modelar cenas para aplicações de realidade virtual. NURBS trabalha bem em modelagem 3D, permitindo facilidade para manipular e controlar vértices, controlar curvatura e suavidade de contornos. NURBS provêm uma base matemática, unificada para representar formas analíticas e livres além de manter exatidão e independência de resolução matemática.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico

Orientadores: Akebo Yamakami / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T22:32:38Z (GMT). No. of bitstreams: 1 Takahashi_MarciaTomie_D.pdf: 1514697 bytes, checksum: bf74eb1142b348387b3427a6f3cb4420 (MD5) Previous issue date: 2004 / Doutorado

Ingeniera Civil en Computación / En la actualidad, la animación de mallas faciales es un área de investigación muy amplia, con una gran cantidad de trabajos publicados con distintas técnicas desarrolladas. Como trabajo de memoria de ingeniería, un alumno del DCC desarrolló una aplicación en la que implementó un algoritmo de interpolación propio para animar una malla facial. Los principales objetivos de esta memoria son saber qué tan competitivo es este algoritmo con respecto a aquellos usados en la actualidad además de definir un buen criterio para esta comparación. Asimismo, se busca identificar otras variables en los algoritmos que pudieran generar mejorías en la calidad de la malla facial. Todo esto con el fin último de mejorar la calidad de la malla. Se propone una métrica de calidad de la malla facial que entrega información de manera rápida y sin necesidad de sujetos de prueba. Esta métrica muestra una alta relación con la evaluación perceptiva realizada a una animación específica en donde se pronuncian los sonidos que componen la base de todos los sonidos posibles. Se implementaron tres algoritmos seleccionados de la bibliografía estudiada: uno de interpolación geométrica, uno de deformación de forma libre orientada a superficies y Planar Bones. Además se propuso e implementó un algoritmo de interpolación nuevo. El diseño de la implementación permite variaciones de parámetros de los algoritmos. La comparación se hizo con una selección de 18 combinaciones entre todos los algoritmos implementados y sus variantes. Al aplicar la métrica se concluye que el algoritmo de la aplicación legada, sin ser el mejor, presenta buenos resultados en comparación a otros algoritmos similares. Además, las variantes consideradas sí muestran mejorías en la superficie de la malla. Sin embargo, se observó que los parámetros de estas variantes deben ser bien escogidos puesto que sino se obtiene el efecto contrario.

Ingeniero Civil en Computación / El modelamiento de problemas que requieren una solución aplicando métodos numéricos como el método de volúmenes finitos necesita una malla geométrica (discretización compuesta de celdas simples tales como triángulos en 2D y tetraedros en 3D) que represente de la mejor forma posible al dominio a estudiar. Un método de generación de mallas geométricas basado en octrees genera, en su proceso de refinamiento, cuboides que presentan a lo más un punto extra en cada arista, conocidos como elementos 1-irregulares, los cuales deben ser teselados en elementos finales. Las mallas mixtas estudiadas son teselaciones de Delaunay compuestas de 7 elementos coesféricos (todos sus vértices están en la superficie de una esfera) finales: tetraedro, cuboide, prisma, pirámide, complemento de tetraedro, prisma deformado y complemento de tetraedro deformado. Esta memoria se enfoca en el ámbito de teselaciones Delaunay sobre cuboides 1-irregulares para mallas mixtas en 3D con el objetivo de minimizar la cantidad de elementos usados en cada teselación, ya que esto afecta directamente el desempeño de un simulador. Se desarrollaron dos herramientas que facilitan el análisis de las teselaciones resultantes de cuboides 1-irregulares, generados por bisección (los puntos extra bisectan a las aristas) y generados por intersección (los puntos extra se ubican arbitrariamente). La primera herramienta desarrollada se encarga de la generación de datos y estadísticas que permiten analizar la teselación de cualquier cuboide 1-irregular y clasificar a qué tipo de poliedro corresponden sus elementos. Se implementó un algoritmo que permite encontrar una teselación Delaunay formada por elementos coesféricos sobre un conjunto de puntos arbitrarios, el cual fue aplicado posteriormente sobre los distintos cuboides estudiados. La segunda herramienta consiste en una aplicación GUI que permite la visualización de la teselación de cualquier cuboide 1-irregular generado por bisección especificando el tamaño del cuboide base, permitiendo interactuar independientemente con cada elemento final generado y visualizar su centroide y circuncentro. El análisis de las teselaciones de los cuboides 1-irregulares arrojó la identificación de 31 elementos coesféricos adicionales a los 7 elementos previamente conocidos, 17 en cuboides generados por bisección y 14 exclusivos de cuboides generados por intersección. Sin embargo, los 7 elementos originales representan la gran mayoría del total de apariciones en todos los cuboides estudiados: más del 95% en cuboides generados por bisección y cerca del 97% en el caso de intersección, donde además, menos del 0,07% corresponde a elementos encontrados exclusivamente en este caso. Al mismo tiempo, se realizó un análisis de las teselaciones de cuboides 1-irregulares generados por bisección bajo distintos criterios de tal manera de minimizar el número de elementos finales distintos permitiendo agregar arcos y caras interiores a la teselación obtenida. Por ejemplo, agregando caras interiores, cerca del 96,9% del total de apariciones corresponde a los 7 elementos originales. Además, se identifican proporciones óptimas del cuboide 1-irregular base para obtener teselaciones generadas por bisección que permiten la aplicación del método de volúmenes finitos. Todas las teselaciones son apropiadas si el cuboide 1-irregular tiene una razón entre su lado más largo y su lado más corto menor o igual a √2.