Complexity of constructing Dixon resultant matrix
Complexity of constructing Dixon resultant matrix
复制标题
构造 Dixon 合成矩阵的复杂性
DOI：
10.1080/00207160.2016.1276572
复制
发表时间：
2017
影响因子：
1.8
通讯作者：
Ji Zhenyi
中科院分区：
文献类型：
--
作者：
Qin Xiaolin;Wu Dingxiong;Tang Lin;Ji Zhenyi
摘要Dixon结式是消去论在代数几何研究和实践中的基本工具。它为自动推理、自动控制和实体造型等应用领域中的一些基准问题提供了有效和实用的解决方案。解的主要任务是构造Dixon结式矩阵，其项比其他结式矩阵的项更复杂。已有的扩展递推公式可以快速构造Dixon结式矩阵。本文详细分析了一般多元情形下递推公式的计算复杂性。可以采用并行计算来加速递归过程。此外，我们还利用标准Dixon结式矩阵的构造将三个二元多项式的计算复杂性推广到一般的多元情形。一些实验结果被一系列不平凡的例子所证实。
ABSTRACT Dixon resultant is a fundamental tool of elimination theory in the study and practice of algebraic geometry. It has provided the efficient and practical solutions to some benchmark problems in a variety of application domains, such as automated reasoning, automatic control, and solid modelling. The major task of solutions is to construct the Dixon resultant matrix, the entries of which are more complicated than the entries of other resultant matrices. An existing extended recurrence formula can construct the Dixon resultant matrix fast. In this paper, we present a detailed analysis of the computational complexity of the recurrence formula for the general multivariate setting. Parallel computation can be applied to speed up the recursive procedure. Furthermore, we also generalize the computational complexity of three bivariate polynomials to the general multivariate case by using the construction of standard Dixon resultant matrix. Some experimental results are demonstrated by a range of nontrivial examples.