ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD
ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD
复制标题
多面同伦连续法组合线性不等式系统全解的枚举
DOI：
10.15807/jorsj.45.64
复制
发表时间：
2002
影响因子：
--
通讯作者：
K. Fujisawa
中科院分区：
文献类型：
--
作者：
A. Takeda;M. Kojima;K. Fujisawa
在计算复变量多项式方程组的11个解的多面体同伦延拓方法的初始阶段，出现了一个有趣的组合（计数）问题。它被公式化为一个问题，寻找一个特殊结构的线性不等式组的所有解决方案，具有一定的附加组合条件。本文充分利用对偶理论和线性规划的单纯形法，给出了该问题的一种计算方法，并给出了该方法在单CPU和并行CPU上的数值结果。
An interesting combinatorial (enumeration) problem arises in the initial phase of the polyhedral homotopy continuation method for computing a11 so1utions of a polynomial equation system in complex variables. It is formulated as a problem of finding all solutions of a specially structured system of linear inequalities with a certain additional combinatorial condition. This paper presents a computational method for the problem fully utilizing the duality theory and the simplex method for linear programs) and report numerical results on a single cpu implementation and a parallel cpu implementation of the method.