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

Revista Matemática de la Universidad Complutense de Madrid (1997)

- Volume: 10, Issue: Supl., page 183-207
- ISSN: 1139-1138

## Access Full Article

top## Abstract

top## How to cite

topLickteig, 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.