A modular method to compute the rational univariate representation of zero-dimensional ideals. (English) Zbl 0945.13010

Given an ideal \(I \subseteq K[x _1,\ldots,x _n]\), it is a difficult task to determine the set of zeros of \(I\), even if \(I\) is known to be zero-dimensional. An important tool for this is the use of Gröbner bases, which by the so-called shape lemma often have a form suitable for finding zeros.
The authors propose a new method to find a rational univariate representation (RUR) for \(I\), as defined by F. Rouillier [Appl. Algebra Eng. Commun. Comput. 9, No. 5, 433-461 (1999; Zbl 0932.12008)]. This is another ideal basis which has the form \[ \{f(u),g _1(u) x _1 - h _1(u),\ldots,g _n(u) x _n - h _n(u)\} \] with \(u \in K[x _1,\ldots,x _n]\) a “separating element” and \(f,g _i,h _i\) univariate polynomials. The advantage over a Gröbner basis is that an RUR often has smaller coefficients.
The new method applies to the case where the ground field \(K\) is \(\mathbb Q\) and uses reduction modulo a prime and Hensel lifting.


13F20 Polynomial rings and ideals; rings of integer-valued polynomials
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
14A05 Relevant commutative algebra
68W30 Symbolic computation and algebraic computation


Zbl 0932.12008


[1] Alonso, M. -E.; Becker, E.; Roy, M. -F.; Wörmann, T.: Zeros, multiplicities and idempotents for zero dimensional systems. Algorithms in algebraic geometry and applications, 1-16 (1996) · Zbl 0879.14033
[2] E. Becker, M. G. Marinari, T. Mora, C. Traverso, Proceedings of the ISSAC’94, 1994, ACM Press, New York, 129, 133 · Zbl 0925.13006
[3] Becker, T.; Weispfenning, V.: Gröbner bases. (1993) · Zbl 0772.13010
[4] B. Buchberger, 1965
[5] Buchberger, B.: Ein algorithmisches kriterium für die lösbarkeit eines algebraischen gleischunssystem. Aeq. math. 4, 374-383 (1970) · Zbl 0212.06401
[6] Faugère, J. -C.; Gianni, P.; Lazard, D.; Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. symb. Comput. 16, 329-344 (1993) · Zbl 0805.13007
[7] P. Gianni, T. Mora, Proceedings of the AAECC-5, 1989, Springer, 247, 257 · Zbl 0692.13012
[8] L. González-Vega, G. Trujillo, Proceedings of the AAECC-11, 1995, Springer, 232, 247 · Zbl 0894.12005
[9] Gräbe, H. -G.: On lucky primes. J. symb. Comput. 15, 199-209 (1993) · Zbl 0787.13016
[10] H. Kobayashi, S. Moritsugu, R. W. Hogan, Proceedings of the ISSAC’88, 1988, Springer, 139, 149
[11] Y. N. Lakshman, 1990
[12] M. Noro, T. Takeshima, Proceedings of the ISSAC’92, 1992, ACM Press, New York, 387, 396 · Zbl 0757.13013
[13] M. Noro, K. Yokoyama
[14] F. Rouillier, 1996
[15] F. Rouillier
[16] F. Rouillier
[17] Yokoyama, K.; Noro, M.; Takeshima, T.: Computing primitive elements of extension fields. J. symb. Comput. 8, 553-580 (1989) · Zbl 0697.68054
[18] Yokoyama, K.; Noro, M.; Takeshima, T.: Solution of systems of algebraic equations and linear maps on residue class rings. J. symb. Comput. 14, 399-417 (1992) · Zbl 0757.13013
[19] Wang, P. S.; Guy, J. T.; Davenport, J. H.: P-adic reconstruction of rational numbers. SIGSAM bull. 16, 2-3 (1982) · Zbl 0489.68032
[20] Zippel, R.: Interpolating polynomials from their values. J. symb. Comput. 9, 375-403 (1990) · Zbl 0702.65011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.