A Piecewise-Linear Homotopy Method with the Use of the Newton Homotopy and a Polyhedral Subdivision

Kiyotaka YAMAMURA; Masahiro KIYOI

A Piecewise-Linear Homotopy Method with the Use of the Newton Homotopy and a Polyhedral Subdivision

Kiyotaka YAMAMURA, Masahiro KIYOI

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on transactions Vol.E73-E No.1 pp.140-148

Publication Date: 1990/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Nonlinear Problems

Authors

Kiyotaka YAMAMURA
Masahiro KIYOI

Keyword

Cite this

Copy

Kiyotaka YAMAMURA, Masahiro KIYOI, "A Piecewise-Linear Homotopy Method with the Use of the Newton Homotopy and a Polyhedral Subdivision" in IEICE TRANSACTIONS on transactions, vol. E73-E, no. 1, pp. 140-148, January 1990, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e73-e_1_140/_p

Copy

@ARTICLE{e73-e_1_140,
author={Kiyotaka YAMAMURA, Masahiro KIYOI, },
journal={IEICE TRANSACTIONS on transactions},
title={A Piecewise-Linear Homotopy Method with the Use of the Newton Homotopy and a Polyhedral Subdivision},
year={1990},
volume={E73-E},
number={1},
pages={140-148},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - A Piecewise-Linear Homotopy Method with the Use of the Newton Homotopy and a Polyhedral Subdivision
T2 - IEICE TRANSACTIONS on transactions
SP - 140
EP - 148
AU - Kiyotaka YAMAMURA
AU - Masahiro KIYOI
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 1
JA - IEICE TRANSACTIONS on transactions
Y1 - January 1990
AB - 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.
ER -