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

Noro, Masayuki; Yokoyama, Kazuhiro

J. Symb. Comput. 28, No. 1-2, 243-263 (1999).

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.

Reviewer: Gregor Kemper (Heidelberg)

MSC:

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

Keywords:

zeros of ideals; modular methods; shape lemma; rational univariate representation; Gröbner basis; Hensel lifting

Citations:

Zbl 0932.12008

References:

[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