Show simple item record

dc.contributor.advisorTrevisan, Vilmarpt_BR
dc.contributor.authorSzutkoski, Jonaspt_BR
dc.date.accessioned2018-01-27T02:30:58Zpt_BR
dc.date.issued2017pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/172180pt_BR
dc.description.abstractIn this work, we consider the problem of computing the sub eld lattice of a separable and nite degree eld extension k( )/k. That is, we wish to nd all elds L such that k L k( ). Until recently, the algorithm used by most Computer Algebraic Systems relied on a combinatorial problem on the roots of the minimal polynomial f of over k, which can be a computationally expensive task. In 2013, another algorithm was presented to nd the sub eld lattice of k( )/k. This method computes a small set of sub elds, called principal sub elds, with the property that any other sub eld of k( )/k is the intersection of some of these principal sub elds. Thus, the problem of computing the sub eld lattice can be split into 2 steps: 1) Find the principal sub elds of k( )/k and 2) Compute all intersections of these sub elds. The rst step can be executed in polynomial time however, the second step can not and thus, dominates the algorithm complexity.Our main goal is to improve the second step, both theoretically and practically. More speci cally, we develop a method to quickly compute all intersections of principal sub elds. While the complexity is still not polynomially bounded (in fact, it can not be for the total number of sub elds is not polynomially bounded), this new method helps to improve the non-polynomial part of the complexity. Practical performance is also improved when the number of intersections is large. We also focus on two special cases: number elds and rational function elds. For the number eld case (i.e., when k = Q), we also present an improvement for the rst step. For the rational function eld case, computing the sub eld lattice of the extension K(t)=K(f(t)) de ned by f(t) 2 K(t) yields all decompositions of the rational function f(t). Our algorithm outperforms previous algorithms for computing rational function decompositions.en
dc.description.abstractNeste trabalho, consideramos o problema de calcular o reticulado de subcorpos de uma extensão separável e de grau nito k( )/k. Isto e, queremos encontrar todos os corpos L tais que k L k( ). Até recentemente, o algoritmo utilizado pela maioria dos Sistemas Algébricos Computacionais baseava-se em um problema combinatorial nas raízes do polinômio minimal f de sobre k. Em 2013, um algoritmo foi apresentado para encontrar tais subcorpos. Este método calcula um pequeno conjunto de subcorpos, chamados de subcorpos principais, com a propriedade de que todo subcorpo de k( )/k e a interseção de alguns destes subcorpos. Assim, calcular o reticulado de subcorpos e dividido em duas etapas: 1) Encontrar os subcorpos principais de k( )/k e 2) Calcular todas as interseções destes subcorpos. A primeira etapa pode ser feita em tempo polinomial. Entretanto, a segunda etapa não pode e assim, domina a complexidade do algoritmo. Nosso objetivo e melhorar a segunda etapa, tanto em teoria quanto na prática. Para isso, mostramos como rapidamente calcular todas as interseções entre os subcorpos principais. Embora a complexidade continue não sendo limitada polinomialmente (e também não poderia ser, pois o número total de subcorpos não o é), conseguimos melhorar a complexidade do algoritmo. Também notamos um melhoramento na prática, principalmente quando o número de subcorpos e grande. Além disso, estudamos dois casos especiais: corpos numéricos e o corpo das funções racionais. Para corpos numéricos (i.e., quando k = Q), também apresentamos um melhoramento para a primeira etapa. No segundo caso, os subcorpos da extensão k(t)=k(f(t)), definida por f(t) 2 k(t), nos fornecem decomposições da função racional f(t). Nosso algoritmo tem uma performance melhor que algoritmos anteriores para calcular as decomposições de funções racionais.pt_BR
dc.format.mimetypeapplication/pdf
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectÁlgebra Computacionalpt_BR
dc.subjectPartiçõespt_BR
dc.subjectFunções racionaispt_BR
dc.titleComputing Subfieldspt_BR
dc.typeTesept_BR
dc.contributor.advisor-coAllem, Luiz Emíliopt_BR
dc.identifier.nrb001059234pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Matemática e Estatísticapt_BR
dc.degree.programPrograma de Pós-Graduação em Matemáticapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2017.pt_BR
dc.degree.leveldoutoradopt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record