Degeneracy Loci and Polynomial Equation Solving
详细信息 查看全文
- 作者：Bernd Bank (1)
Marc Giusti (2)
Joos Heintz (3) (4) (5)
Gr茅goire Lecerf (2)
Guillermo Matera (6) (7)
Pablo Solern贸 (8) (9)
1. Institut f眉r Mathematik ; Humboldt-Universit盲t zu Berlin ; 10099聽 ; Berlin ; Germany
2. Laboratoire d鈥檌nformatique ; LIX ; UMR 7161 CNRS ; Campus de l鈥櫭塩ole Polytechnique ; 91128聽 ; Palaiseau Cedex ; France
3. Departamento de Computaci贸n ; Universidad de Buenos Aires ; Ciudad Univ. ; Pab.I ; 1428聽 ; Buenos Aires ; Argentina
4. CONICET ; Ciudad Univ. ; Pab.I ; 1428聽 ; Buenos Aires ; Argentina
5. Departamento de Matem谩ticas ; Estad铆stica y Computaci贸n ; Facultad de Ciencias ; Universidad de Cantabria ; 39071聽 ; Santander ; Spain
6. Instituto del Desarrollo Humano ; Universidad Nacional de General Sarmiento ; J. M. Gutierrez 1150 ; B1613GSX聽 ; Los Polvorines ; Buenos Aires ; Argentina
7. CONICET ; J. M. Gutierrez 1150 ; B1613GSX聽 ; Los Polvorines ; Buenos Aires ; Argentina
8. Instituto Matem谩tico Luis Santal贸 ; CONICET ; Buenos Aires ; 1428 ; Argentina
9. Departamento de Matem谩ticas ; Facultad de Ciencias Exactas y Naturales ; Universidad de Buenos Aires ; Buenos Aires ; 1428 ; Argentina - 关键词：Polynomial equation solving ; Pseudo ; polynomial complexity ; Degeneracy locus ; Degree of varieties ; 14M10 ; 14M12 ; 14Q20 ; 14P05 ; 68W30
- 刊名：Foundations of Computational Mathematics
- 出版年：2015
- 出版时间：February 2015
- 年：2015
- 卷：15
- 期：1
- 页码：159-184
- 全文大小：462 KB
- 参考文献：1. B. Bank, M. Giusti, J. Heintz, L. Lehmann, and L. M. Pardo, / Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, Found. Comput. Math. 12 (2012), no. 1, 75鈥?22.
2. B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop, / Polar varieties and efficient real elimination, Math. Z. 238 (2001), no. 1, 115鈥?44.
3. B. Bank, M. Giusti, J. Heintz, and L. M. Pardo, / Generalized polar varieties and an efficient real elimination, Kybernetika 40 (2004), no. 5, 519鈥?50.
4. B. Bank, M. Giusti, J. Heintz, and L. M. Pardo, / Generalized polar varieties: geometry and algorithms, J. Complexity 21 (2005), no. 4, 377鈥?12.
5. B. Bank, M. Giusti, J. Heintz, M. Safey El Din, and 脡. Schost, / On the geometry of polar varieties, Appl. Algebra Eng. Commun. Comput. 21 (2010), no. 1, 33鈥?3.
6. W. Bruns and U.聽Vetter, / Determinantal rings, Lecture Notes in Mathematics, vol. 1327, Springer Berlin Heidelberg, 1988.
7. P. B眉rgisser, M. Clausen, and M. A. Shokrollahi, / Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften, vol. 315, Springer Berlin Heidelberg, 1997.
8. P. B眉rgisser and M. Lotz, / The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties, Found. Comput.Math. 7 (2007), no. 1, 59鈥?6.
9. A. Cafure and G. Matera, / Fast computation of a rational point of a variety over a finite field, Math. Comp. 75 (2006), no.聽256,2049鈥?085.
10. M. Demazure, / Catastrophes et bifurcations, Ellipses, Paris, 1989.
11. C. Durvye and G. Lecerf, / A concise proof of the Kronecker polynomial system solver from scratch, Expo. Math. 26 (2008), no. 2, 101鈥?39.
12. J. A. Eagon and M. Hochster, \(R\) / -sequences and indeterminates, Quart. J. Math. Oxford Ser. (2) 25 (1974), 61鈥?1.
13. J. A. Eagon and D.聽G. Northcott, / Ideals defined by matrices and a certain complex associated with them, Proc. Roy. Soc. Ser. A 269 (1962), 188鈥?04.
14. D. Eisenbud, / Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995.
15. J.-C. Faug猫re, / FGb: A Library for Computing Gr枚bner Bases, Mathematical Software - ICMS 2010 (K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama, eds.), Lecture Notes in Comput. Sci., vol. 6327, Springer-Verlag, 2010, pp. 84鈥?7.
16. W. Fulton, / Intersection theory, second ed., Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics, vol. 2, Springer-Verlag, Berlin, 1998.
17. M. Giusti, J. Heintz, K. H盲gele, J. E. Morais, L. M. Pardo, and J. L. Monta帽a, / Lower bounds for Diophantine approximations, J. Pure Appl. Algebra 117/118 (1997), 277鈥?17.
18. M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo, / Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra 124 (1998), no. 1-3, 101鈥?46.
19. M. Giusti, G. Lecerf, and B. Salvy, / A Gr枚bner free alternative for polynomial system solving, J. Complexity 17 (2001), no. 1, 154鈥?11.
20. J. Heintz, / Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239鈥?77.
21. J. Heintz, G. Matera, and A. Waissbein, On the time-space complexity of geometric elimination procedures, Appl. Algebra Engrg. Comm. Comput. 11 (2001), no. 4, 239鈥?96.
22. J. Heintz and C.-P. Schnorr, / Testing polynomials which are easy to compute, International Symposium on Logic and Algorithmic (Zurich, 1980) (Geneva), Monograph. Enseign. Math., vol. 30, Univ. Gen猫ve, 1982, pp. 237鈥?54.
23. E. Kaltofen and B. D. Saunders, / On Wiedemann鈥檚 method of solving sparse linear systems, Applied algebra, algebraic algorithms and error-correcting codes (New Orleans, LA, 1991), Lecture Notes in Comput. Sci., vol. 539, Springer, Berlin, 1991, pp. 29鈥?8.
24. H. Matsumura, / Commutative ring theory, Cambridge Studies in Advanced Mathematics, vol. 8, Cambridge University Press, Cambridge, 1986, Translated from the Japanese by M. Reid.
25. D. Mumford, / The red book of varieties and schemes, Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1988.
26. R. Piene, / Polar classes of singular varieties, Ann. Sci. 脡cole Norm. Sup. (4) 11 (1978), no. 2, 247鈥?76.
27. M. Safey El Din, / RAGLib (Real Algebraic Geometry Library), Maple (TM) package, from 2007, http://www-polsys.lip6.fr/~safey/RAGLib.
28. M. Safey El Din and Ph. Tr茅buchet, / Strong bi-homogeneous B茅zout theorem and its use in effective real algebraic geometry, Tech. Report 6001, INRIA, 2006, http://hal.inria.fr/inria-00105204.
29. J. T. Schwartz, / Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701鈥?17.
30. I. R. Shafarevich, / Basic algebraic geometry. 1, second ed., Springer-Verlag, Berlin, 1994, Varieties in projective space, Translated from the 1988 Russian edition and with notes by Miles Reid.
31. I. R. Shafarevich, / Basic algebraic geometry. 2, second ed., Springer-Verlag, Berlin, 1994, Schemes and complex manifolds, Translated from the 1988 Russian edition by Miles Reid.
32. M. Turrel聽Bardet, / 脡tude des syst猫mes alg茅briques surd茅termin茅s. Applications aux codes correcteurs et 脿 la cryptographie, Ph.D. thesis, Universit茅 Paris 6, 2004, http://tel.archives-ouvertes.fr/tel-00449609.
33. J. van der Hoeven, G. Lecerf, B. Mourain, et al., / Mathemagix, from 2002, http://www.mathemagix.org.
34. W. Vogel, / Lectures on results on Bezout鈥檚 theorem, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 74, Published for the Tata Institute of Fundamental Research, Bombay, 1984, Notes by D. P. Patil.
35. R. Zippel, / Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM 鈥?9, Internat. Sympos., Marseille, 1979), Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin, 1979, pp. 216鈥?26. - 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Numerical Analysis
Computer Science, general
Math Applications in Computer Science
Linear and Multilinear Algebras and Matrix Theory
Applications of Mathematics - 出版者：Springer New York
- ISSN：1615-3383
文摘
Let \(V\) be a smooth, equidimensional, quasi-affine variety of dimension \(r\) over \(\mathbb {C}\) , and let \(F\) be a \((p\times s)\) matrix of coordinate functions of \(\mathbb {C}[V]\) , where \(s\ge p+r\) . The pair \((V,F)\) determines a vector bundle \(E\) of rank \(s-p\) over \(W:=\{x\in V \mid \mathrm{rk }F(x)=p\}\) . We associate with \((V,F)\) a descending chain of degeneracy loci of \(E\) (the generic polar varieties of \(V\) represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded-error probabilistic pseudo-polynomial-time algorithm that we will design and that solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space.