EFFICIENT DEGREE-COMPUTATION METHOD FOR A GENERALIZED-METHOD OF BISECTION

Let P be an n-dimensional polyhedron and let {Mathematical expression} be the oriented boundary of P in terms of the oriented (n-1)-simplexes Sq=〈X1q,..., Xnq〉, q=1,..., m. Let F=(f1,..., fn):P→Rn, and assume F(X)≠θ for X∈b(P). For each 〈X1q,..., Xnq〉∈b(P) define a matrix ℛ(SqF) by setting the entry in the i-th row, j-th column of ℛ(SqF) equal to 1 if sgn(fj(Xiq))≠1 and 0 if sgn(fj(Xiq))=-1, where sgn(y)=1 if y≧0, and sgn(y)=-1 otherwise. To each such matrix ℛ(SqF) assign a number (ℛ(SqF)) in the following way: Set Par (ℛ(SqF))=+1 if the entries on and below the main diagonal of ℛ(SqF) are 1 and the entries one row above the main diagonal are 0. Also set Par (ℛ(SqF))=1 if ℛ(SqF) can be put into this form by an even permutation of its rows, and set Par (ℛ(SqF))=-1 if ℛ(SqF) can be put into form by an odd permutation of rows. Set Par (ℛ(SqF))=0 for all other matrices ℛ(SqF). Then, under rather general hypotheses and assuming diameter of each Sq∈b(P) is small, the topological degree of F at θ relative to P is given by: {Mathematical expression} The assumptions are identical to those used by Stenger (Numer. Math. 25, 23-28). Use of the characterization is illustrated, an algorithm for automatic computation is presented, and an application of this algorithm to finding roots of F(X)=θ is explained. The degree computation algorithm requires storage of a number of (n-1)-simplexes proportional to log n, and sgn(fj(Siq) is evaluated once at most for each i,j, and q. © 1979 Springer-Verlag.