Dima Grigoriev
ABSTRACT
Let F be an algebraically closed field of zero characteristic, a polynomial @@@@ ∈ F[X1, … , Xn have a multiplicative complexity r and ƒ1, … ƒk ∈ F[X1, … , Xn] be some polynomials of degrees not exceeding d, such that @@@@ = ƒ1 = ··· = ƒk = 0 has a finite number of roots. We show that the number of possible distinct vectors of multiplicities of these roots is small when r, d and k are small. As technical tools we design algorithms which produce Gröbner bases and vectors of multiplicities of the roots for a parametric zero-dimensional system. The complexities of these algorithms are singly exponential. We also describe an algorithm for parametric absolute factorization of multivariate polynomials. This algorithm has subexponential complexity in the case of a small (relative to the number of variables) degree of the polynomials.
- ABRW 96.Alonso, M., Becker, E., Roy, M.-F., WSrmann, T., Zeros, multiplicities and idempotents for zero-dimensional systems, Algorithms in Algebraic Geometry and Applications. Progress in Math., 143, 1996, 1-20. Google Scholar
Digital Library
- BW 93.Becker, T., Weispfenning, V., Grb'bner Bases, Springer-Verlag, New-York, 1993.Google Scholar
- B 85.Buchberger, B., GrSbner bases: An algorithmic method in polynomial ideal theory. In: Bose, N.K. (Ed.), Multidimensional Systems Theory, Reidel, Dordrecht, 1985, 184-232.Google ScholarCross Ref
- BCS 97.Btirgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic Complexity Theory, Berlin: Springer-Verlag, 1997. Google ScholarDigital Library
- CGH 89.Caniglia, L., Galligo, A., Heintz, J., Some new effectivity bounds in computational geometry, Lecture Notes Camp. Sci., 357, 1989, 131-151. Google ScholarDigital Library
- Ca 89.Canny, J., Generalized characteristic polynomials, Lecture Notes Camp. Sci., 358, 1989, 293-299. Google ScholarDigital Library
- C 84.Chistov, A., Algorithm of polynomial complexity for factoring polynomials and finding the components of the varieties in subexponential time, In: Zapiski Nauchnyh Seminarav LOMI, 137, 1984, 124-188. English translation in: J. Soviet Math., 34, 1838-1882.Google Scholar
- CG 84.Chistov, A., Grigoriev, D., Complexity of quantifier elimination in the theory of algebraically closed fields, Lecture Notes Camp. Sci., 176, 1984, 17-31. Google ScholarDigital Library
- Co 67.Collins, G.E., Subresultants and reduced polynomial reminder sequences, or. A UM, 14, 1967, 128-142. Google ScholarDigital Library
- DGFS 89.Dickenstein, A., Giusti, M., Fitchas, N., Sessa, C., The membership problem for unmixed polynomial ideals is solvable in single exponential time, Proceedings 7th Intern. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-7, Discrete Appl. Math., aa, 1989, 73-94. Google ScholarDigital Library
- FGLM 93.Faug~re, J.C., Gianni, P., Lazard, D., Mora, T., Efficient computation of zero-dimensional Gr6bner bases by change of ordering, J. Symbolic Computation, 16, 1993, 329-344. Google ScholarDigital Library
- FG 90.Fitchas, N., Galligo, A., Nullstellensatz effectif et conjacture de Serre (th~or~me de Quillen-Suslin) pour le calcul formel, Math. Nachrichten, 149, 1990, 231-253.Google ScholarCross Ref
- Ca 84.Gathen, von zur., Hensel and Newton methods in valuation rings, Math. Camp., 42, 1984, 637-661.Google ScholarCross Ref
- GK 85.Gathen, von zur J., Kaltofen, E., Factoring sparse multivariate polynomials, d. Camput. System Sci., 31, 1985. Google ScholarDigital Library
- Gi 89.Gianni, P., Properties of GrSbner bases under specializations, Lecture Notes Camp. Sci., 378, 1989, 293-297. Google ScholarDigital Library
- GM 89.Gianni, P., Mora, T., Algebraic solution of systems of polynomial equations using Groebner bases, Lecture Notes Camp. Sci., 356, 1989, 247-257. Google ScholarDigital Library
- GH 93.Giusti, M., Heintz, J., La d~termination des points isol~s et de la dimension d'une vari~t~ alg~brique peut se faire en temps polynomial, Computational Algebraic Geometry and Commutative Algebra. Symposia Mathematica, 34, 1993, 216-256.Google Scholar
- G 84.Grigoriev, D., Factorization of polynomials over finite field and the solution of systems of algebraic equations, In: Zapiski Nauchnyh Seminarav LOMI, 137, 1984, 20-79. English translation in: J. Soviet Math., 34, 1762-1803.Google Scholar
- G 86.Grigoriev, D., Complexity of deciding the firstorder theory of algebraically closed fields, Izvestia of Academy of Sciences of the USSR, 50, 1986, 1106-1120 (in Russian, English translation in Math. USSR Izvestia, 29, 1987, 459-475).Google Scholar
- G 87.Grigoriev, D., Complexity of quantifier elimination in the theory of ordinary differential equations, Lecture Notes in Computer Sci., 378, 1987, 11-25. Google ScholarDigital Library
- G 88.Grigoriev, D., Complexity of deciding Tarski algebra. J. Symbolic Camput., 5, 1988, 65-108. Google ScholarDigital Library
- G 90.Grigoriev, D., Complexity of factoring and GCD calculating of ordinary linear differential operators, J. Symbolic Camput., 10, 1990, 7-37. Google ScholarDigital Library
- GKS 90.Grigoriev, D., Karpinski, M., Singer, M., Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM J. Camput., 19, 1990, 1059-1063. Google ScholarDigital Library
- H 83.Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Thear. Camput. Sci., 24, 1983, 239-277.Google ScholarCross Ref
- K 89.Kalkbrener, M., Solving systems of algebraic equations by using GrSbner bases, Lecture Notes Camp. Sci., 378, 1989, 282-292. Google ScholarDigital Library
- Kal 85.Kaltofen, E., Sparse Hensel lifting, Lecture Notes Camp. Sci., 204, 1985, 4-17. Google ScholarDigital Library
- KMH 89.Kobayashi, H., Moritsugu, S., Hogan, R.W., Solving systems of algebraic equations, Lecture Notes Camp. Sci., 358, 1989, 139-149. Google ScholarDigital Library
- KP 94.Krick,T., Pardo, L.M., Une approche informatique pour l'approximation diophantienne, C.R. Acad. Sci. Paris, S~rie I, 318, 1994, 407-412.Google Scholar
- Lak 91.Lakshman, Y.N., A single exponential bound on the complexity of computing GrSbner bases of zero dimensional ideals, Effective methods in algebraic geometry, Progress in Mathematics, 94, Birkhiiuser Verlag, Basel, 1991, 227-234.Google Scholar
- Laz 81.Lazard, D., Resolution des systemes d'equations algebriques, Theoretical Computer Science, 15, 1981, 77- 110.Google ScholarCross Ref
- PS 64.P61ya, G., SzegS, G., Aufgaben und Lehrsiitze aus der Analysis, Springer-Verlag, Berlin, 1964.Google Scholar
- Ro 99.Rouillier, F., Solving zero-dimensional systems through rational univariate representations, Applic. Algebra in Eng. Cammun. Computing, 9, 1999, 433-461.Google ScholarCross Ref
- T 78.Trinks, W., Uber Buchbergers Verfahren, Systeme algebraisher Gleichungen zu 15sen, J. Number Th., 10, 1978, 475-488.Google ScholarCross Ref
- W 89.Weispfenning, V., Constructing universal Groebner bases, Lecture Notes Camp. Sci., 356, 1989, 408-417. Google ScholarDigital Library
Index Terms
- Bounds on numers of vectors of multiplicities for polynomials which are easy to compute
Recommendations
Computing the nearest singular univariate polynomials with given root multiplicities
In this paper, we derive explicit expressions for the nearest singular polynomials with given root multiplicities and its distance to the given polynomial. These expressions can be computed recursively. These results extend previous results of Zhi et ...
A Method to Compute Minimal Polynomials
Let $f ( X )$ and $g ( X )$ be polynomials with coefficients in an arbitrary field K. Assume that $f ( X )$ is irreducible and let r be a root of $f ( X )$. We describe a new algorithm for computing the minimal polynomial of $g ( r )$ over K. The novelty ...
Nonnegative Quadratic Forms and Bounds on Orthogonal Polynomials
We show that some nonnegative quadratic forms containing orthogonal polynomials, such as e.g. the Christoffel-Darboux kernel for x=y in the classical case, provide a lot of information about behavior of the polynomials on the real axis. We illustrate ...
Comments