Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Foundations of Computational Mathematics
Published in: Foundations of Computational Mathematics 1/2015

01-02-2015

Degeneracy Loci and Polynomial Equation Solving

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

Published in: Foundations of Computational Mathematics | Issue 1/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

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.
previous article A Facility Location Formulation for Stable Polynomials and Elliptic Fekete Points
next article A -Conjecture for Newton Polygons

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
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–122.
2.
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.
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.
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.
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.
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–86.
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–2085.
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–139.
12.
J. A. Eagon and M. Hochster, \(R\) -sequences and indeterminates, Quart. J. Math. Oxford Ser. (2) 25 (1974), 61–71.
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–204.
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–87.
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–317.
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–146.
19.
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.
J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277.
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–296.
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–254.
23.
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.
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–276.
27.
28.
29.
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717.
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.
33.
34.
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.
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.
Metadata
Title
Degeneracy Loci and Polynomial Equation Solving
Authors
Bernd Bank
Marc Giusti
Joos Heintz
Grégoire Lecerf
Guillermo Matera
Pablo Solernó
Publication date
01-02-2015
Publisher
Springer US
Published in
Foundations of Computational Mathematics / Issue 1/2015
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-014-9214-z

Other articles of this Issue 1/2015

Foundations of Computational Mathematics 1/2015 Go to the issue

OriginalPaper

Overdetermined Systems of Sparse Polynomial Equations

OriginalPaper

A Complexity Theory of Constructible Functions and Sheaves

OriginalPaper

A Facility Location Formulation for Stable Polynomials and Elliptic Fekete Points

OriginalPaper

A Randomized Homotopy for the Hermitian Eigenpair Problem

Foreword

Foreword

OriginalPaper

Effect of Islands in Diffusive Properties of the Standard Map for Large Parameter Values

Premium Partner

    Image Credits