|
NeuroCOLT
Technical Report NC-TR-96-004
Nash Trees and
Nash Complexity
Felipe
Cucker
Universitat Pompeu Fabra
Spain
Thomas
Lickteig
Universität Bonn
Germany
Abstract
Numerical analysis computational problems such as Cholesky decomposition
of a positive definite matrix, or unitary transformation of a complex
matrix into upper triangular form (for instance by the Householder
algorithm), require algorithms that use also ``non-arithmetical''
operations such as square roots. The aim of this paper is twofold:
1. Generalizing the notions of arithmetical semi-algebraic decision
trees and computation trees (that is, with outputs) we suggest a definition
of Nash trees and Nash straight line programs (SLPs), necessary to
formalize and analyse numerical analysis algorithms and their complexity
as mentioned above. These trees and SLPs have a Nash operational signature
$N^R$ over a real closed field $R$. Based on the sheaf of abstract
Nash functions over the real spectrum of a ring as introduced
by M.-F. Roy, we propose a category nash_R of partial (homogeneous)
N^R-algebras in which these Nash operations make sense in a natural
way.
2. Using this framework, in particular the execution of $N^R$-SLPs
in appropriate $N^R$-algebras, we extend the degree-gradient lower
bound to Nash decision complexity of the membership problem of co-one-dimensional
semi-algebraic subsets of open semi-algebraic subsets.
Download Compressed
Postscript
|