EFFICIENT EVALUATION OF POLYNOMIALS AND THEIR PARTIAL DERIVATIVES IN HOMOTOPY CONTINUATION METHODS

スポンサーリンク

概要

• 論文の詳細を見る

• 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 Horner scheme, which is popular in evaluating a univariate polynomial, to a multivariate polynomial. But the extension is not unique, and there are many Horner factorizations of a given multivariate polynomial which require different numbers of multiplications. We present exact method for computing a minimum Horner factorization, which can process smaller size polynomials, as well as heuristic methods for a small number of multiplications, which can process larger size polynomials. Based on these Horner 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.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Kojima Masakazu

  Tokyo Institute of Technology

関連論文

• EQUALITY BASED CONTRACTION OF SEMIDEFINITE PROGRAMMING RELAXATIONS IN POLYNOMIAL OPTIMIZATION
• SOLVING LARGE SCALE OPTIMIZATION PROBLEMS VIA GRID AND CLUSTER COMPUTING(Network Design, Control and Optimization)
• ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD
• EFFICIENT EVALUATION OF POLYNOMIALS AND THEIR PARTIAL DERIVATIVES IN HOMOTOPY CONTINUATION METHODS
• Computational Aspects of Bilinear Matrix Inequality Problems
• SPARSE SECOND ORDER CONE PROGRAMMING FORMULATIONS FOR CONVEX OPTIMIZATION PROBLEMS
• A GENERAL FRAMEWORK FOR CONVEX RELAXATION OF POLYNOMIAL OPTIMIZATION PROBLEMS OVER CONES

スポンサーリンク