|
NeuroCOLT
Technical Report NC-TR-96-052
Semi-Algebraic
Complexity -- Additive Complexity of Diagonalization of QuadraticForms
Thomas
Lickteig
Universit\"at Bonn
Germany
Klaus
Meer
RWTH Aachen
Germany
Abstract
(for references see full paper):
We study matrix calculation such as diagonalization of quadratic
forms under the aspect of additive complexity and relate these complexities
to the complexity of matrix multiplication. While in \cite{BKL} 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. \cite{BCR}, \cite{Be}, \cite{KS})
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\^ole 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
\cite{Li1} which constitutes another use of exponentiation and logarithm
as it appears in the work on additive complexity by \cite{Gr} and
\cite{Ri} through the use of \cite{Kh}. We confine ourselves
here to diagonalization of quadratic forms. In the forthcoming paper
\cite{LM} further such relativizations of additive complexity will
be given for a series of matrix computational tasks.
Download Compressed
Postscript
|