Skip to main content
Erschienen in: Foundations of Computational Mathematics 1/2015

01.02.2015

Degeneracy Loci and Polynomial Equation Solving

verfasst von: Bernd Bank, Marc Giusti, Joos Heintz, Grégoire Lecerf, Guillermo Matera, Pablo Solernó

Erschienen in: Foundations of Computational Mathematics | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat 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–122. 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–122.
2.
Zurück zum Zitat B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop, Polar varieties and efficient real elimination, Math. Z. 238 (2001), no. 1, 115–144. B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop, Polar varieties and efficient real elimination, Math. Z. 238 (2001), no. 1, 115–144.
3.
Zurück zum Zitat B. Bank, M. Giusti, J. Heintz, and L. M. Pardo, Generalized polar varieties and an efficient real elimination, Kybernetika 40 (2004), no. 5, 519–550. B. Bank, M. Giusti, J. Heintz, and L. M. Pardo, Generalized polar varieties and an efficient real elimination, Kybernetika 40 (2004), no. 5, 519–550.
4.
Zurück zum Zitat B. Bank, M. Giusti, J. Heintz, and L. M. Pardo, Generalized polar varieties: geometry and algorithms, J. Complexity 21 (2005), no. 4, 377–412. B. Bank, M. Giusti, J. Heintz, and L. M. Pardo, Generalized polar varieties: geometry and algorithms, J. Complexity 21 (2005), no. 4, 377–412.
5.
Zurück zum Zitat 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–83. 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–83.
6.
Zurück zum Zitat W. Bruns and U. Vetter, Determinantal rings, Lecture Notes in Mathematics, vol. 1327, Springer Berlin Heidelberg, 1988. W. Bruns and U. Vetter, Determinantal rings, Lecture Notes in Mathematics, vol. 1327, Springer Berlin Heidelberg, 1988.
7.
Zurück zum Zitat P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften, vol. 315, Springer Berlin Heidelberg, 1997. P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften, vol. 315, Springer Berlin Heidelberg, 1997.
8.
Zurück zum Zitat 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–86. 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–86.
9.
Zurück zum Zitat 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–2085. 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–2085.
10.
Zurück zum Zitat M. Demazure, Catastrophes et bifurcations, Ellipses, Paris, 1989. M. Demazure, Catastrophes et bifurcations, Ellipses, Paris, 1989.
11.
Zurück zum Zitat C. Durvye and G. Lecerf, A concise proof of the Kronecker polynomial system solver from scratch, Expo. Math. 26 (2008), no. 2, 101–139. C. Durvye and G. Lecerf, A concise proof of the Kronecker polynomial system solver from scratch, Expo. Math. 26 (2008), no. 2, 101–139.
12.
Zurück zum Zitat J. A. Eagon and M. Hochster, \(R\) -sequences and indeterminates, Quart. J. Math. Oxford Ser. (2) 25 (1974), 61–71. J. A. Eagon and M. Hochster, \(R\) -sequences and indeterminates, Quart. J. Math. Oxford Ser. (2) 25 (1974), 61–71.
13.
Zurück zum Zitat 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–204. 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–204.
14.
Zurück zum Zitat D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995.
15.
Zurück zum Zitat 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–87. 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–87.
16.
Zurück zum Zitat 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. 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.
Zurück zum Zitat 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–317. 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–317.
18.
Zurück zum Zitat 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–146. 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–146.
19.
Zurück zum Zitat M. Giusti, G. Lecerf, and B. Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity 17 (2001), no. 1, 154–211. M. Giusti, G. Lecerf, and B. Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity 17 (2001), no. 1, 154–211.
20.
Zurück zum Zitat J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277.
21.
Zurück zum Zitat 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–296. 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–296.
22.
Zurück zum Zitat 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–254. 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–254.
23.
Zurück zum Zitat E. Kaltofen and B. D. Saunders, On Wiedemann’s 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–38. E. Kaltofen and B. D. Saunders, On Wiedemann’s 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–38.
24.
Zurück zum Zitat H. Matsumura, Commutative ring theory, Cambridge Studies in Advanced Mathematics, vol. 8, Cambridge University Press, Cambridge, 1986, Translated from the Japanese by M. Reid. 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.
Zurück zum Zitat D. Mumford, The red book of varieties and schemes, Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1988. D. Mumford, The red book of varieties and schemes, Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1988.
26.
Zurück zum Zitat R. Piene, Polar classes of singular varieties, Ann. Sci. École Norm. Sup. (4) 11 (1978), no. 2, 247–276. R. Piene, Polar classes of singular varieties, Ann. Sci. École Norm. Sup. (4) 11 (1978), no. 2, 247–276.
29.
Zurück zum Zitat J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717.
30.
Zurück zum Zitat 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. 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.
Zurück zum Zitat 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. 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.
34.
Zurück zum Zitat W. Vogel, Lectures on results on Bezout’s 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. W. Vogel, Lectures on results on Bezout’s 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.
Zurück zum Zitat R. Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979), Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin, 1979, pp. 216–226. R. Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979), Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin, 1979, pp. 216–226.
Metadaten
Titel
Degeneracy Loci and Polynomial Equation Solving
verfasst von
Bernd Bank
Marc Giusti
Joos Heintz
Grégoire Lecerf
Guillermo Matera
Pablo Solernó
Publikationsdatum
01.02.2015
Verlag
Springer US
Erschienen in
Foundations of Computational Mathematics / Ausgabe 1/2015
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-014-9214-z

Weitere Artikel der Ausgabe 1/2015

Foundations of Computational Mathematics 1/2015 Zur Ausgabe

Foreword

Foreword