An efficient degree-computation method for a generalized method of bisection

Summary

LetP be ann-dimensional polyhedron and let$b(P) = \sum\limits_{q = 1}^m {\langle X_1^q , \ldots ,X_n^q \rangle }$ be the oriented boundary ofP in terms of the oriented (n−1)-simplexesS _q =〈X ^q₁ ,...,X ^q_n 〉,q=1,...,m. LetF=(f ₁,...,f _n):P→R ⁿ, and assumeF(X)≠θ forX∈b(P). For each 〈X ^q₁ ,...,X ^q_n 〉∈b(P) define a matrix ℛ(S _q F) by setting the entry in thei-th row,j-th column of ℛ(S _q F) equal to 1 if sgn(f _j(X ^q_i ))≠1 and 0 if sgn(f _j(X ^q_i ))=−1, where sgn(y)=1 ify≧0, and sgn(y)=−1 otherwise. To each such matrix ℛ(S _q F) assign a number (ℛ(S _q F)) in the following way: Set Par (ℛ(S _q F))=+1 if the entries on and below the main diagonal of ℛ(S _q F) are 1 and the entries one row above the main diagonal are 0. Also set Par (ℛ(S _q F))=1 if ℛ(S _q F) can be put into this form by an even permutation of its rows, and set Par (ℛ(S _q F))=−1 if ℛ(S _q F) can be put into form by an odd permutation of rows. Set Par (ℛ(S _q F))=0 for all other matrices ℛ(S _q F). Then, under rather general hypotheses and assuming diameter of eachS _q ∈b(P) is small, the topological degree ofF at θ relative toP is given by:

$$d(F.P,\theta ) = \sum\limits_{q = 1}^m {Par(\mathcal{R}(S_q ,F)).} $$

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 ofF(X)=θ is explained. The degree computation algorithm requires storage of a number of (n−1)-simplexes proportional to logn, and sgn(f _j(S ^q _i ) is evaluated once at most for eachi,j, andq.