Registro:
Documento: | Tesis de Grado |
Título: | Un algoritmo superfast para descomponer formas binarias |
Título alternativo: | A Superfast Algorithm for the Decomposition of Binary Forms |
Autor: | Bender, Matías Rafael |
Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
Publicación en la web: | 2023-03-27 |
Fecha de defensa: | 2015-11-02 |
Fecha en portada: | 2015 |
Grado Obtenido: | Grado |
Título Obtenido: | Licenciado en Ciencias de la Computación |
Director: | Heintz, Joos U. |
Director Asistente: | Faugère, Jean-Charles |
Idioma: | Inglés |
Palabras clave: | FORMAS BINARIAS; DESCOMPOSICION DE TENSORES; RANGO TENSORIAL; ALGORITMOS SUPERFAST; MATRICES DE HANKELBINARY FORM; TENSOR DECOMPOSITION; TENSOR RANK; SUPERFAST ALGORITHM; HANKEL MATRIX |
Formato: | PDF |
Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000435_Bender |
PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000435_Bender.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000435_Bender |
Ubicación: | Dep.COM 000435 |
Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Bender, Matías Rafael. (2015). Un algoritmo superfast para descomponer formas binarias. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000435_Bender |
Resumen:
Descomponer una Forma Binaria consiste en reescribir un polinomio homogéneo en dos variables de grado D como una combinación lineal de D-esimas potencias de factores lineales. En este trabajo nos concentraremos en las combinaciones lineales con la mínima cantidad posible de sumandos, valor conocido como el Rango de la forma binaria. Nuestro problema es equivalente al de la Descomposición de Tensores Simétricos cuando el tensor simétrico tiene dimensión 2. En esta tesis proponemos un algoritmo para la descomposición de formas binarias, el cual se basa en el trabajo de Sylvester del siglo XIX. Retomamos su aporte utilizando técnicas del Algebra Lineal y resultados sobre Secuencias Linealmente Recurrentes. De esta manera ofrecemos un nuevo enfoque para la descomposición de formas binarias con una complejidad aritmética cuasi-lineal en el grado de la forma dada, óptima si no consideramos los factores poli-logarítmicos. La descomposición involucra números algebraicos sobre el cuerpo original, por lo que demostramos una cota superior para el grado de la extensión algebraica necesaria, la cual es Min(rango; D− rango + 1).
Abstract:
To decompose a Binary Form we write an homogeneous polynomial on two variables and degree D as a linear combination of D-powers of linear forms. In this work we focus on the smallest possible number of summands in the linear combination, a quantity known as Rank. Our problem is equivalent to the Symmetric Tensor Decomposition problem when the symmetric tensor has dimension 2. In this thesis we focus on an algorithm for the decomposition of binary forms, which relies on the work from Sylvester in the 19th century. We revisit this work using linear algebra techniques and results from linear recurrent sequences. We propose a new approach for the decomposition of binary forms with soft linear arithmetic complexity in the degree of the given form, and hence optimal, up to poly-logarithmic factors. The solution of the decomposition problem requires to deal with algebraic numbers over the ground field whose degree we surprisingly succeed to bound by Min(rank; D − rank + 1).
Citación:
---------- APA ----------
Bender, Matías Rafael. (2015). Un algoritmo superfast para descomponer formas binarias. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000435_Bender
---------- CHICAGO ----------
Bender, Matías Rafael. "Un algoritmo superfast para descomponer formas binarias". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2015.https://hdl.handle.net/20.500.12110/seminario_nCOM000435_Bender
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000435_Bender.pdf
Distrubución geográfica