On the bit complexity of polynomial system solving (Q1734694): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:43, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the bit complexity of polynomial system solving |
scientific article |
Statements
On the bit complexity of polynomial system solving (English)
0 references
27 March 2019
0 references
Let \(R=\mathbb{Z}[X_1, \ldots , X_n]\) be the ring of polynomials in terms of the variables \(X_1, \ldots , X_n\) over \(\mathbb{Z}\). Let \(F_1, \ldots , F_r , G \in R\) be a sequence of polynomials such that the sequence \(F_1, \ldots , F_r\) forms a reduced regular sequence outside the variety \(V(G)\subset \mathbb{C}^n\). Thus, for any \(s\), the ideal \(I_s=\langle F_1, \ldots , F_s \rangle:G^\infty \subset \mathbb{Q}[X_1,\ldots ,X_n]\) is radical and equidimensional of dimension \(n-s\). In [ibid. 17, No. 1, 154--211 (2001; Zbl 1003.12005)], \textit{M. Giusti} et al. presented an algorithm to compute, in \(r\) stages, a suitable parametrization, so-called Kronecker representation for \(I_r\). In addition, in order to control the bit length of intermediate results, they proposed a method to perform the computations modulo a prime number. However, in this direction, the determination of a lucky prime is crucial. By studying this concept and applying \(p\)-adic lifting, the authors describe and analyze a randomized algorithm for solving a polynomial system (via computing its Kronecker representation) and show that its bit complexity is roughly quadratic in the Bézout number of the system and linear in its bit size.
0 references
polynomial system solving over \(\mathbb{Q}\)
0 references
bit complexity
0 references
reduced regular sequence
0 references
Chow form
0 references
lifting fibers
0 references
lucky primes
0 references