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.
Citation
Research Report B-433, Deparment of Mathematical and Computing Sciences, 2-12-1-W8-29, Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan