This paper presents an efficient piecewise-linear (PL) homotopy method for solving systems of nonlinear equations. In the conventional PL homotopy methods, a simplicial subdivision is used for solving general problems, and a rectangular subdivision is used for solving special problems, namely, systems of nonlinear equations with separable mappings. Although the rectangular algorithm is much more efficient than the simplicial algorithm, it cannot be applied to a problem which contains only one non-separable element. In this paper, we use a polyhedral subdivision, which is a hybrid concept of both a simplicial subdivision and a rectangular subdivision. For this purpose, we adopt the Newton homotopy as a homotopy, because it contains parameter t separately. It is shown that the polyhedral algorithm can be applied to systems of nonlinear equations with partially separable or non-separable mappings, and is much more efficient than the conventional simplicial algorithms. Then, we propose an efficient acceleration technique which improves the local convergence speed of the polyhedral algorithm. By this technique, the sequence of the approximate solutions generated by the algorithm converges to the exact solution quadratically. And in this case, the computational work involved in each iteration is almost edentical to that of Newton's method. Therefore, our algorithm becomes as efficient as Newton's method when it reaches sufficiently close to the solution.

Separability is a valuable property of nonlinear mappings. By exploiting this property, computational complexity of many numerical algorithms can be substantially reduced. In this letter, a new algorithm is presented that detects the separability of nonlinear mappings using the concept of "computational graph". A hybrid algorithm using both the top-down search and the bottom-up search is proposed. It is shown that this hybrid algorithm is advantageous in detecting the separability of nonlinear simultaneous functions.