La complejidad algorítmica del álgebra lineal en anillos de polinomios-teorema de Serre-Quillen-Suslin en cálculo formal

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

1990

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Descripción:

Sea F una matriz de r filas y s columnas con coeficientes enun anillo de polinomios de n variables sobre un cuerpo infinito k. Notemos con deg(F) el máximo de los grados de los coeficientes de F ysea d:= 1+ deg(F). Se describe un algoritmo que computa una matriz unimodular M de sfilas y s columnas, con deg(H)=(rd)^O(n), y tal que F.M= [Ir,O], donde [Ir,O] nota la matriz de r filas y s columnas obtenida agregando a lamatriz identidad Ir, s-r columnas de ceros. El algoritmo se presenta comouna red aritmética con entradas enk y para la complejidad se considera que el costo de cada operación en ky decada comparación es 1. La complejidad secuencial de este algoritmo es s^o(r²) r^o(n²) d^o(n²+r²) (o sea cantidad de operaciones en el cuerpo y comparaciones), mientrasque la complejidad paralela es O(n^4 r^4 log² (srd)). Se demuestra que las cotas para el grado de M y para las complejidadesmencionadas, son óptimas en orden. Este algoritmo está inspirado enla demostración de Suslin de la Conjetura de Serre.

Identificador:

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