Full paper in PDF:
$%T. Lickteig and K. Meer, Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms, Rev. Mat. Univ. Complut. Madrid 10 (1997), supplementary, 183–207. %$

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.

1991 Mathematics Subject Classification: Primary: 68Q05, 68Q25, 68Q40; secondary: 14P10, 14P20.