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

Lickteig, Thomas, and Meer, Klaus. "Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.." Revista Matemática de la Universidad Complutense de Madrid 10.Supl. (1997): 183-207. <http://eudml.org/doc/44259>.

@article{Lickteig1997,
abstract = {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.},
author = {Lickteig, Thomas, Meer, Klaus},
journal = {Revista Matemática de la Universidad Complutense de Madrid},
keywords = {Cálculo matricial; Geometría algebraica; Adición; Complejidad de problemas; Formas cuadráticas; Funciones reales; matrix calculations; multiplicative complexity},
language = {eng},
number = {Supl.},
pages = {183-207},
title = {Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.},
url = {http://eudml.org/doc/44259},
volume = {10},
year = {1997},
}

TY - JOUR
AU - Lickteig, Thomas
AU - Meer, Klaus
TI - Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.
JO - Revista Matemática de la Universidad Complutense de Madrid
PY - 1997
VL - 10
IS - Supl.
SP - 183
EP - 207
AB - 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.
LA - eng
KW - Cálculo matricial; Geometría algebraica; Adición; Complejidad de problemas; Formas cuadráticas; Funciones reales; matrix calculations; multiplicative complexity
UR - http://eudml.org/doc/44259
ER -