Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.

Título inglés	Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.
Título español	Complejidad semialgebraica aditiva de complejidad, de la diagonalización de formas cuadráticas.
Autor/es	Lickteig, Thomas ; Meer, Klaus
Organización	Inst. Inform. Univ. Bonn, Bonn, Alemania;Rhein. Westf. Tech. Hochschul. Aachen, Aquisgrán, Alemania
Revista	0214-3577
Publicación	1997, 10 (Supl.): 183-207, 33 Ref.
Tipo de documento	articulo
Idioma	Inglés
Resumen inglés	We study matrix calculations such as diagonalization of quadratic forms under the aspect of additive complexity and relate these complexities to the complexity of matrix multiplication. While in Bürgisser et al. (1991) for multiplicative complexity the customary thick path existence argument was sufficient, here for additive complexity we need the more delicate finess of the real spectrum (cf. Bochnak et al. (1987), Becker (1986), Knebusch and Scheiderer (1989)) to obtain a complexity relativization. After its outstanding success in semi-algebraic geometry the power of the real spectrum method in complexity theory becomes more and more apparent. Our discussions substantiate once more the signification and future rôle of this concept in the mathematical evolution of the field of real algebraic algorithmic complexity. A further technical tool concerning additive complexity is the structural transport metamorphosis from Likteig (1990) which constitutes another use of the exponential and the logarithm as it appears in the work on additive complexity by Yu and Grigoriev (1982) and Risler (1985) through the use of Khovanskii (1980). We confine ourselves here to diagonalization of quadratic forms. In the forthcoming paper Lickteig and Meer (to appear, 1997) further such relativizations of additive complexity will be given for a series of matrix computational tasks.
Clasificación UNESCO	120610 ; 120111
Palabras clave español	Cálculo matricial ; Geometría algebraica ; Adición ; Complejidad de problemas ; Formas cuadráticas ; Funciones reales
Código MathReviews	MR1485299
Código Z-Math	Zbl 0899.68043
Acceso al artículo completo