Un algoritmo superfast para descomponer formas binarias

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2015-11-02

Tipo de documento: 

info:eu-repo/semantics/bachelorThesis
 

Formato:

application/pdf

Idioma:

eng

Temas:

FORMAS BINARIAS - DESCOMPOSICION DE TENSORES - RANGO TENSORIAL - ALGORITMOS SUPERFAST - MATRICES DE HANKEL - BINARY FORM - TENSOR DECOMPOSITION - TENSOR RANK - SUPERFAST ALGORITHM - HANKEL MATRIX

Descripción:

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).

Identificador:

https://hdl.handle.net/20.500.12110/seminario_nCOM000435_Bender