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

Masakazu Kojima (kojimais.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