Complexity of Computing the Local Dimension of a Semialgebraic Set

The paper describes several algorithms related to a problem of computing the local dimension of a semialgebraic set. Let a semialgebraic set V be defined by a system of k inequalities of the formf ≥ 0 with f R [ X1, ,Xn ], deg(f) < d , andx V . An algorithm is constructed for computing the dimension of the Zariski tangent space to V at x in time (kd)O(n). Let x belong to a stratum of codimensionlxinV with respect to a smooth stratification ofV . Another algorithm computes the local dimension dimx(V) with the complexity (k(lx + 1)d)O(lx2n). Ifl = maxx Vlx, and for every connected component the local dimension is the same at each point, then the algorithm computes the dimension of every connected component with complexity (k(l + 1)d)O(l2n). If V is a real algebraic variety defined by a system of equations, then the complexity of the algorithm is less thankdO(l2n) , and the algorithm also finds the dimension of the tangent space to V at x in time kdO(n). Whenl is fixed, like in the case of a smooth V , the complexity bounds for computing the local dimension are (kd)O(n)andkdO(n) respectively. A third algorithm finds the singular locus ofV in time (kd)O(n2).