The Ehrhart function L_P(t) of a polytope P is defined to be the number of integer points in the dilated polytope tP. Classical Ehrhart theory is mainly concerned with integer values of t; in this master thesis, we focus on how the Ehrhart function behaves when the parameter t is allowed to be an arbitrary real number. There are three main results concerning this behavior in this thesis. Some rational polytopes (like the unit cube [0, 1]^d) only gain integer points when the dilation parameter t is an integer, so that computing L_P(t) yields the same integer point count than L_P(t). We call them semi-reflexive polytopes. The first result is a characterization of these polytopes in terms of the hyperplanes that bound them. The second result is related to the Ehrhart theorem. In the classical setting, the Ehrhart theorem states that L_P(t) will be a quasipolynomial whenever P is a rational polytope. This is also known to be true with real dilation parameters; we obtained a new proof of this fact starting from the chraracterization mentioned above. The third result is about how the real Ehrhart function behaves with respect to translation in this new setting. It is known that the classical Ehrhart function is invariant under integer translations. This is far from true for the real Ehrhart function: not only there are infinitely many different functions L_{P + w}(t) (for integer w), but under certain conditions the collection of these functions identifies P uniquely. / A função de Ehrhart L_P(t) de um politopo P é definida como sendo o número de pontos com coordenadas inteiras no politopo dilatado tP. A teoria de Ehrhart clássica lida principalmente com valores inteiros de t; esta dissertação de mestrado foca em como a função de Ehrhart se comporta quando permitimos que o parâmetro t seja um número real arbitrário. São três os resultados principais desta dissertação a respeito deste comportamento. Alguns politopos racionais (como o cubo unitário [0, 1]^d) apenas ganham pontos inteiros quando o parâmetro de dilatação t é um inteiro, de tal forma que computar L_P(t) devolve a mesma contagem de pontos que L_P(t). Eles são chamados de politopos semi-reflexivos. O primeiro resultado desta dissertação é uma caracterização destes politopos em termos de suas descrições como interseção de semi-espaços. O segundo resultado é relacionado ao teorema de Ehrhart. No contexto clássico, o teorema de Ehrhart afirma que L_P(t) será um quasi-polinômio sempre que P for um politopo racional. Sabe-se que este teorema generaliza para parâmetros reais de dilatação; nesta dissertação é apresentada uma nova demonstração deste fato, baseada na caracterização mencionada acima. O terceiro resultado é sobre como a função real de Ehrhart se comporta com respeito à translação neste novo contexto. Sabe-se que a função de Ehrhart clássica é invariante sob translações por vetores com coordenadas inteiras. Por outro lado, a função real de Ehrhart está bem longe de ser invariante: não só existem infinitas funções L_{P + w}(t) distintas, mas também, sob certas condições, esta coleção de funções identifica P unicamente.

The Ehrhart function L_P(t) of a polytope P is defined to be the number of integer points in the dilated polytope tP. Classical Ehrhart theory is mainly concerned with integer values of t; in this master thesis, we focus on how the Ehrhart function behaves when the parameter t is allowed to be an arbitrary real number. There are three main results concerning this behavior in this thesis. Some rational polytopes (like the unit cube [0, 1]^d) only gain integer points when the dilation parameter t is an integer, so that computing L_P(t) yields the same integer point count than L_P(t). We call them semi-reflexive polytopes. The first result is a characterization of these polytopes in terms of the hyperplanes that bound them. The second result is related to the Ehrhart theorem. In the classical setting, the Ehrhart theorem states that L_P(t) will be a quasipolynomial whenever P is a rational polytope. This is also known to be true with real dilation parameters; we obtained a new proof of this fact starting from the chraracterization mentioned above. The third result is about how the real Ehrhart function behaves with respect to translation in this new setting. It is known that the classical Ehrhart function is invariant under integer translations. This is far from true for the real Ehrhart function: not only there are infinitely many different functions L_{P + w}(t) (for integer w), but under certain conditions the collection of these functions identifies P uniquely. / A função de Ehrhart L_P(t) de um politopo P é definida como sendo o número de pontos com coordenadas inteiras no politopo dilatado tP. A teoria de Ehrhart clássica lida principalmente com valores inteiros de t; esta dissertação de mestrado foca em como a função de Ehrhart se comporta quando permitimos que o parâmetro t seja um número real arbitrário. São três os resultados principais desta dissertação a respeito deste comportamento. Alguns politopos racionais (como o cubo unitário [0, 1]^d) apenas ganham pontos inteiros quando o parâmetro de dilatação t é um inteiro, de tal forma que computar L_P(t) devolve a mesma contagem de pontos que L_P(t). Eles são chamados de politopos semi-reflexivos. O primeiro resultado desta dissertação é uma caracterização destes politopos em termos de suas descrições como interseção de semi-espaços. O segundo resultado é relacionado ao teorema de Ehrhart. No contexto clássico, o teorema de Ehrhart afirma que L_P(t) será um quasi-polinômio sempre que P for um politopo racional. Sabe-se que este teorema generaliza para parâmetros reais de dilatação; nesta dissertação é apresentada uma nova demonstração deste fato, baseada na caracterização mencionada acima. O terceiro resultado é sobre como a função real de Ehrhart se comporta com respeito à translação neste novo contexto. Sabe-se que a função de Ehrhart clássica é invariante sob translações por vetores com coordenadas inteiras. Por outro lado, a função real de Ehrhart está bem longe de ser invariante: não só existem infinitas funções L_{P + w}(t) distintas, mas também, sob certas condições, esta coleção de funções identifica P unicamente.

Orientador: Sandro Rigo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T08:17:12Z (GMT). No. of bitstreams: 1 Vieira_CristiannoMartins_M.pdf: 1981128 bytes, checksum: 5af9a00808029ad96cd8d02e569b1cda (MD5) Previous issue date: 2010 / Resumo: Embora muitos programas possuam uma forma regular de paralelismo, que pode ser expressa em termos de laços paralelos, muitos exemplos importantes não a possuem. Loop skewing é uma transformação que remodela o espaço de iteração dos laços para que seja possível expressar o paralelismo implícito através de laços paralelos. Como consequência da complexidade em se modificar o espaço de iteração dos laços, e de possíveis problemas causados por transformações deste tipo - como o possível aumento na taxa de miss em caches -, no geral, elas não são largamente utilizadas. Neste projeto, implementamos a transformação loop skewing sobre o compilador da linguagem C presente no GCC (GNU Compiler Collection), de forma a permitir a assistência pelo programador. Utilizamos a ferramenta Graphite como base para a implementação da otimização, apenas representando-a como uma transformação afim sobre um objeto matemático multidimensional chamado polítopo. Mostramos, através de um estudo detalhado sobre o modelo matemático denominado modelo politópico, que laços com estruturas específicas - perfeitamente aninhados, com limites e acesso á memória descritos por funções afins - poderiam ser representados como polítopos, e que transformações aplicadas a estes seriam espelhadas no código gerado a partir desses polítopos. Dessa forma, qualquer transformação que possa ser estruturada como uma transformação afim sobre um polítopo, poderá ser implementada. Mostramos, ainda, durante a análise de desempenho, que transformações deste tipo são viáveis e, apesar de algumas limitações impostas pela infraestrutura do GCC, aumentam relativamente o desempenho das aplicações compiladas com ela - obtivemos um ganho máximo de aproximadamente 115% para o uso de quatro threads em uma das aplicações executadas. Verificamos o impacto do uso de programas já paralelizados manualmente sobre a plataforma, e obtivemos um ganho máximo de 11% nesses casos, mostrando que ainda aplicações paralelizadas podem conter paralelismo implícito / Abstract: Although many programs present a regular form of parallelism, which can be expressed as parallel loops, many important examples do not. Loop skewing is a transformation that reorganizes the iteration space of loops to make it possible to expose the implicit parallelism through parallel loops. In general, as a consequence of the complexity in modifying the iteration space of loops, and possible problems caused by such changes - such as the possibility of increasing the miss rate in caches -, they are not widely used. In this work, the loop skewing transformation was implemented on GCC's C compiler (GNU Compiler Collection), allowing programmer's assistance. Graphite provides us a basis for implementation of the optimization, just representing it as an a_ne transformation on a multidimensional mathematical object called polytope. We show, through a detailed study about the mathematical model called polytope model, that for a very restricted loop structure - perfectly nested, with limits and memory accesses described by a_ne functions - could be represented as polytopes, and transformations applied to these would be carried by the code generated from these polytope. Thus, any transformation that could be structured as an a_ne transformation on a polytope, could be added. We also show, by means of performance analysis, that this type of transformation is feasible and, despite some limitations imposed by the still under development GCC's infrastructure for auto-parallelization, fairly increases the performance of some applications compiled with it - we achived a maximum of about 115% using four threads with one of the applications. We also veriéd the impact of using manually parallelized programs on this platform, and achieved a maximum gain of 11% in these cases, showing that even parallel applications may have implicit parallelism / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

[pt] Um politopo convexo é semiregular se todas as suas faces forem regulares e o grupo de isometrias agir transitivamente sobre os vértices. A classificação dos politopos semiregulares inclui algumas famílias infinitas, algumas exceções em dimensão baixa e uma família, os politopos de Gosset, que está definida para dimensão entre 3 e 8. Certos grupos de isometrias de R(n) gerados por reflexões são chamados grupos de Coxeter. A classificação dos grupos de Coxeter inclui três famílias infinitas, algumas exceções em dimensão menor ou igual a 4 e os grupos excepcionais E(6), E(7) e E(8). O grupo E(n) é o grupo das isometrias do politopo de Gosset em dimensao n. Nesta dissertação construiremos os grupos de Coxeter En, os politopos de Gosset e indicaremos a relação destes objetos com os reticulados e as álgebras de Lie também conhecidos como E(n). / [en] A convex polytope is semiregular if all its faces are regular and the group of isometries acts transitively over vertices. The classification of semiregular polytopes includes a few infinite families, some low dimensional exceptions and a family, the Gosset polytopes, which is defined for dimension 3 to 8. Certain groups of isometries of R(n) generated by reflections are called Coxeter groups. The classification of finite Coxeter groups includes three infinite families, some exceptions in dimension 4 or lower and the exceptional groups E(6), E(7) and E(8). The group En is the group of isometries of the Gosset polytope in dimension n. In this dissertation we construct the Coxeter groups En, the Gosset polytopes and indicate the relationship of these objects with the lattices and Lie algebras which are also known as E(n).

Made available in DSpace on 2015-03-03T15:28:33Z (GMT). No. of bitstreams: 1 CatiaRSS_DISSERT.pdf: 4951076 bytes, checksum: 0231a1261bda878faaaf3e30a97857a0 (MD5) Previous issue date: 2012-11-27 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Um dos temas mais populares no tratamento de dados nos ?ltimos dez anos gira em torno da descoberta que a recupera??o de sinais esparsos em sistemas lineares, pode ser feita com um n?mero de equa??es bem menor que o n?mero de vari?veis. Em linhas gerais, se A = AmN, queremos resolver Ax = b e procuramos solu??es esparsas, ou seja, com apenas s << N entradas n~ao-nulas em algum sistema de coordenadas, isto pode ser feito com um n?mero de equa??es m << N, minimizando a norma l1 de x, sujeito ? restri??o Ax = b + r, sob determinadas condi??es (8). Vale dizer, com muito menos equa??es que incognitas. D? o nome de Magica l1" para esta possibilidade de recuperar um sinal esparso, resolvendo um problema de otimiza??o convexa com relativamente poucas restri??es. Para algumas poucas matrizes A, de grande import?ncia em aplica??es, ha teorias razoavelmente estabelecidas indicando esta possibilidade, para muitas n?o. O objetivo desta disserta??o e situar e discutir casos nos quais a Magica l1" funciona, com foco nas rela??es entre a esparsidade s, o n?mero de linhas m e o n?mero de vari?veis N, para algumas matrizes importantes e associadas ? codifica??o de imagens 2D. Em particular, realizamos testes num?ricos com tr?s matrizes A, visando encontrar empiricamente rela??es entre s, m e N para as quais a Magica l1 e bem sucedida. Em duas delas, ha teorias matematicas, ainda em constru??o, indicando condic~oes de sucesso, grosso modo, na forma de m=s C log(N=s), sempre com alguma probabilidade de insucesso associada. Listamos inicialmente A = G, formada por entradas aleatorias com distribui??o gaussiana i.i.d., de media zero e colunas aproximadamente unitarias. A segunda e a transformada de Fourier, que usaremos numa vers~ao de transformada de cossenos 2D. A denotamos por A = DCT. Para probabilidades esmagadoras" de sucesso na recupera??o de sinais esparsos com G, usando a Magica l1", os resultados te?ricos estabelecem regi?es menores, vale dizer, valores mais elevados para a constante C. Se relaxamos um pouco esta exig?ncia de sucesso, obtemos regi?es mais amplas, conforme teremos oportunidade de discutir na disserta ??o. m=s C log(N=s) ainda e uma conjectura no caso de Fourier, se queremos probabilidades esmagadoras" de sucesso na recupera??o de sinais esparsos pela via da otimiza??o convexa acima prescrita. Os resultados emp?ricos por nos obtidos para iv estas duas matrizes ainda s~ao muito preliminares, mas se ajustam bem , via quadrados m??nimos, a m=s C log(s=N), com C em 1:6 e em 1, correspondendo aos resultados mais otimistas encontrados na literatura para G e DCT, nos quais a eficacia da Magica l1" e assumida num sentido mais fraco, no sentido de permitir alguma taxa de insucesso n~ao totalmente desprez??vel, porem de forma probabilisticamente controlada. No caso da matriz da transformada de Radon, n?o ha previs~ao teorica consolidada para o funcionamento daMagica l1" e sequer encontramos conjecturas sobre o que se pode esperar. Em nossos testes com matrizes de Radon, encontramos uma regi~ao para a validade da Magica l1", cujo ajuste de quadrados m??nimos a m=s C log(s=N) se deu com 2; 5 e C 0; 29

Made available in DSpace on 2014-12-17T14:55:06Z (GMT). No. of bitstreams: 1 RobinsonLSA_TESE.pdf: 3429587 bytes, checksum: 6e34f5d59ebeb449eb13310ec5ff1eae (MD5) Previous issue date: 2012-11-05 / ART networks present some advantages: online learning; convergence in a few epochs of training; incremental learning, etc. Even though, some problems exist, such as: categories proliferation, sensitivity to the presentation order of training patterns, the choice of a good vigilance parameter, etc. Among the problems, the most important is the category proliferation that is probably the most critical. This problem makes the network create too many categories, consuming resources to store unnecessarily a large number of categories, impacting negatively or even making the processing time unfeasible, without contributing to the quality of the representation problem, i. e., in many cases, the excessive amount of categories generated by ART networks makes the quality of generation inferior to the one it could reach. Another factor that leads to the category proliferation of ART networks is the difficulty of approximating regions that have non-rectangular geometry, causing a generalization inferior to the one obtained by other methods of classification. From the observation of these problems, three methodologies were proposed, being two of them focused on using a most flexible geometry than the one used by traditional ART networks, which minimize the problem of categories proliferation. The third methodology minimizes the problem of the presentation order of training patterns. To validate these new approaches, many tests were performed, where these results demonstrate that these new methodologies can improve the quality of generalization for ART networks / As redes do tipo ART apresentam algumas vantagens: aprendizado online; converg?ncia em poucas ?pocas de treinamento; aprendizado incremental, etc. Contudo, alguns problemas existem: prolifera??o de categorias, sensibilidade a ordem de apresenta??o dos padr?es, escolha de um bom valor para o par?metro de vigil?ncia. O mais importante deles ? o problema da prolifera??o de categorias e ? provavelmente o mais cr?tico. Esse problema faz com que a rede crie v?rias categorias consumindo recursos (recursos para armazenar uma grande quantidade de categorias desnecess?rias impactando negativamente ou at? mesmo inviabilizando o tempo de processamento da rede) sem contribuir para a qualidade da representa??o do problema, ou seja, em muitos casos a quantidade excessiva de categorias geradas pelas redes ART faz com que a qualidade da generaliza??o da rede seja inferior. Outro fator que leva a prolifera??o de categorias das redes do tipo ART ? a dificuldade de aproximar regi?es de classes que tem geometria n?o retangular, ocasionando uma generaliza??o inferior a outros m?todos de classifica??o. A partir da observa??o desses problemas, foi desenvolvido esse trabalho que prop?e tr?s metodologias. Duas dessas metodologias utilizam uma geometria mais flex?vel do que a geometria regular retangular presente nas redes ART tradicionais e minimizam o problema da prolifera??o de categorias. A terceira metodologia minimiza o problema da ordem de apresenta??o dos padr?es e a prolifera??o de categorias. Com o objetivo de validar as novas abordagens, v?rios testes foram realizados. Os resultados obtidos nesses testes demonstram a viabilidade das metodologias propostas em reduzir o n?mero de categorias e melhorar a qualidade da generaliza??o. Em muitos desses testes a quantidade m?nima de categorias necess?rias para classificar corretamente as classes foi atingida ap?s o treinamento, o que demonstra uma significativa melhora em rela??o aos m?todos j? existentes. Al?m disso, devido a nova geometria das categorias, utilizando politopos convexos, a qualidade da generaliza??o melhorou em rala??o ao estado da arte

[pt] A análise de complexidade clássica para problemas NP-difíceis é geralmente orientada para cenários de pior caso, considerando apenas o comportamento assintótico. No entanto, existem algoritmos práticos com execução em um tempo razoável para muitos problemas clássicos. Além disso, há evidências que apontam para algoritmos polinomiais no modelo de árvore de decisão linear para resolver esses problemas, embora não muito explorados. Neste trabalho, exploramos esses resultados teóricos anteriores. Mostramos que a solução ótima para problemas combinatórios 0-1 pode ser encontrada reduzindo esses problemas para uma Busca por Vizinho Mais Próximo sobre o conjunto de vértices de Voronoi correspondentes. Utilizamos os hiperplanos que delimitam essas regiões para gerar sistematicamente uma árvore de decisão que repetidamente divide o espaço até que possa separar todas as soluções, garantindo uma resposta ótima. Fazemos experimentos para testar os limites de tamanho para os quais podemos construir essas árvores para os casos do 0-1 knapsack, weighted minimum cut e symmetric traveling salesman. Conseguimos encontrar as árvores desses problemas com tamanhos até 10, 5 e 6, respectivamente. Obtemos também as relações de adjacência completas para os esqueletos dos politopos do knapsack e do traveling salesman até os tamanhos 10 e 7. Nossa abordagem supera consistentemente o método de enumeração e os métodos baseline para o weighted minimum cut e symmetric traveling salesman, fornecendo soluções ótimas em microssegundos. / [en] Classical complexity analysis for NP-hard problems is usually oriented to worst-case scenarios, considering only the asymptotic behavior. However, there are practical algorithms running in a reasonable time for many classic problems. Furthermore, there is evidence pointing towards polynomial algorithms in the linear decision tree model to solve these problems, although not explored much. In this work, we explore previous theoretical results. We show that the optimal solution for 0-1 combinatorial problems can be found by reducing these problems into a Nearest Neighbor Search over the set of corresponding Voronoi vertices. We use the hyperplanes delimiting these regions to systematically generate a decision tree that repeatedly splits the space until it can separate all solutions, guaranteeing an optimal answer. We run experiments to test the size limits for which we can build these trees for the cases of the 0-1 knapsack, weighted minimum cut, and symmetric traveling salesman. We manage to find the trees of these problems with sizes up to 10, 5, and 6, respectively. We also obtain the complete adjacency relations for the skeletons of the knapsack and traveling salesman polytopes up to size 10 and 7. Our approach consistently outperforms the enumeration method and the baseline methods for the weighted minimum cut and symmetric traveling salesman, providing optimal solutions within microseconds.