Optimization Online


Efficient Evaluation of Polynomials and Their Partial Derivatives in Homotopy Continuation Methods

Masakazu Kojima (kojima***at***is.titech.ac.jp)

Abstract: The aim of this paper is to study how efficiently we evaluate a system of multivariate polynomials and their partial derivatives in homotopy continuation methods. Our major tool is an extension of the Hornor scheme, which is popular in evaluating a univariate polynomial, to a multivariate polynomial. But the extension is not unique, and there are many Hornor factorizations of a given multivariate polynomial which require different numbers of multiplications. We present exact method for computing a minimum Hornor factorization, which can process smaller size polynomials, as well as heuristic methods for a smaller number of multiplicatios, which can process larger size polynomials. Based on these Hornor factorization methods, we then present methods to evaluate a system of multivariate polynomials and their partial derivatives. Numerical results are shown to verify the effectiveness and the efficiency of the proposed methods.

Keywords: Hornor scheme, multivariate polynomial, homotopy continuation method

Category 1: Other Topics (Other )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Research Report B-433, Deparment of Mathematical and Computing Sciences, 2-12-1-W8-29, Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan

Download: [PDF]

Entry Submitted: 09/09/2006
Entry Accepted: 09/11/2006
Entry Last Modified: 09/09/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society