Complexity of constructing Dixon resultant matrix

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.

KEYWORDS:

• Polynomial system solving
• elimination theory
• Dixon resultant matrix
• recursive algorithm
• computational complexity

2010 AMS Subject Classifications:

• 11Y16
• 13P99
• 33F10
• 68W30

Acknowledgments

The first author is grateful to Dr Shizhong Zhao for his valuable discussions about constructing the Dixon resultant matrix. The authors are also grateful to the anonymous referees for their helpful comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. n+1 polynomials $f_1,\dots ,f_{n+1}$ with $x_1,\dots ,x_n$ are called $n-$degree if there exist nonnegative integers $m_1,\dots ,m_n$ such that each $f_j=\sum _{i_1=0}^{m_1}\cdots \sum _{i_n=0}^{m_n}{a}_{j,i_1,\dots ,i_n}{x}_1^{i_1}\cdots x_n^{i_n},1\le j\le n+1.$

2. A multi-homogeneous polynomial set of type $(l_1,\dots ,l_r;d_1,\dots ,l_r)$ with n+1 polynomials, where $n=\sum _{i=1}^r{l}_i$ is the total number of variables.

Additional information

Funding

This work was supported by National Natural Science Foundation of China [grant numbers 61402537 and 11671377], Youth Innovation Promotion Association of the Chinese Academy of Sciences (2012335), and West Light Foundation of the Chinese Academy of Sciences.