×
Dahan, Xavier; Kadri, Abdulilah; Schost, Éric

Bit-size estimates for triangular sets in positive dimension. (English) Zbl 1246.13039

J. Complexity 28, No. 1, 109-135 (2012).
Bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over \(Q\) are given. The estimates are worst case upper bounds and depend on the degree and height of the underlying algebraic sets. The use of these results is demonstrated in the context of a modular algorithm. This work extends the results confined to the case of dimension \(0\), provided by X. Dahan and E. Schost, in: ISSAC 2004. Proceedings of the 2004 international symposium on symbolic and algebraic computation, Santander, Spain, July 4–7, 2004. 103–110 (2004; Zbl 1134.13308)]. The proposed strategy goes back to dimension \(0\) by evaluation and interpolation techniques. Even though the main tool (height theory) remains the same, new difficulties arise to control the growth of the coefficients during the interpolation process.
Reviewer: Vasilis Dimitriou (Chania)

Cited in 4 Documents

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
65H10 Numerical computation of solutions to systems of equations

Keywords:

triangular sets; bit size; regular chain; height function

Citations:

Zbl 1134.13308

Software:

mctoolbox; Kronecker; Magma; ISOLATE
PDF BibTeX XML Cite
\textit{X. Dahan} et al., J. Complexity 28, No. 1, 109--135 (2012; Zbl 1246.13039)
Full Text: DOI arXiv

References:

[1] Alonso, M. E.; Becker, E.; Roy, M. F.; Wörmann, T., Zeroes, multiplicities and idempotents for zerodimensional systems, (MEGA’94. MEGA’94, Progress in Mathematics, vol. 142 (1996), Birkhäuser), 1-15
[2] Aubry, P.; Valibouze, A., Using Galois ideals for computing relative resolvents, J. Symbolic Comput., 30, 6, 635-651 (2000) · Zbl 0989.12004
[3] Aubry, P.; Lazard, D.; Moreno Maza, M., On the theories of triangular sets, J. Symbolic Comput., 28, 1-2, 45-124 (1999) · Zbl 0943.12003
[4] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symbolic Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039
[5] Bürgisser, P.; Clausen, M.; Shokrollahi, A., Algebraic Complexity Theory (1997), Springer · Zbl 1087.68568
[6] Conway, J. B., A Course in Functional Analysis, (Graduate Texts in Mathematics, vol. 96 (1990), Springer-Verlag: Springer-Verlag New York) · Zbl 0706.46003
[7] Cox, D.; Little, J.; O’Shea, D., (Using Algebraic Geometry. Using Algebraic Geometry, Graduate Texts in Mathematics (1998), Springer-Verlag) · Zbl 0920.13026
[8] Dahan, X.; Schost, É., Sharp estimates for triangular sets, (ISSAC’04 (2004), ACM), 103-110 · Zbl 1134.13308
[9] Dahan, X.; Moreno Maza, M.; Schost, É.; Wu, W.; Xie, Y., Lifting techniques for triangular decompositions, (ISSAC’05 (2005), ACM), 108-115 · Zbl 1360.14146
[10] Dahan, X.; Jin, X.; Moreno Maza, M.; Schost, É., Change of order for regular chains in positive dimension, Theoret. Comput. Sci., 392, 1-3, 37-65 (2008) · Zbl 1131.14065
[11] Gallo, G.; Mishra, B., Efficient algorithms and bounds for Wu-Ritt characteristic sets, (Mora, T.; Traverso, C., Proceedings MEGA’90. Proceedings MEGA’90, Progress in Math., vol. 94 (1990), Birkhäuser), 235-248
[12] Geddes, K. O.; Czapor, S. R.; Labahn, G., Algorithms for Computer Algebra (1992), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 0805.68072
[13] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complexity, 17, 2, 154-211 (2001) · Zbl 1003.12005
[14] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24, 3, 239-277 (1983) · Zbl 0546.03017
[15] Higham, N., Accuracy and Stability of Numerical Algorithms (2002), SIAM · Zbl 1011.65010
[16] Jelonek, Z., On the effective Nullstellensatz, Invent. Math., 162, 1, 1-17 (2005) · Zbl 1087.14003
[17] Krick, T.; Pardo, L. M.; Sombra, M., Sharp estimates for the arithmetic Nullstellensatz, Duke Math. J., 109, 521-598 (2001) · Zbl 1010.11035
[18] Lang, S., Fundamentals of Diophantine Geometry (1983), Springer-Verlag: Springer-Verlag New York · Zbl 0528.14013
[19] Lazard, D., Solving zero-dimensional algebraic systems, J. Symbolic Comput., 13, 147-160 (1992) · Zbl 0753.13013
[20] McCarthy, P. J., Algebraic Extensions of Fields (1991), Dover: Dover New York · Zbl 0143.05802
[21] Philippon, P., Sur des hauteurs alternatives III, J. Math. Pures Appl., 74, 4, 345-365 (1995) · Zbl 0878.11025
[22] Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Engrg. Comm. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008
[23] Sabia, J.; Solernó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz, Appl. Algebra Engrg. Comm. Comput., 6, 6, 353-376 (1995) · Zbl 0844.14018
[24] Schost, É., Complexity results for triangular sets, J. Symbolic Comput., 36, 3-4, 555-594 (2003) · Zbl 1074.68082
[25] Schost, É., Computing parametric geometric resolutions, Appl. Algebra Engrg. Comm. Comput., 13, 5, 349-393 (2003) · Zbl 1058.68123
[27] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 0936.11069
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.