Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Applicable Algebra in Engineering, Communication and Computing
Erschienen in: Applicable Algebra in Engineering, Communication and Computing 2/2020

25.07.2019 | Original Paper

Real root finding for low rank linear matrices

verfasst von: Didier Henrion, Simone Naldi, Mohab Safey El Din

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 2/2020

Einloggen

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

search-config
loading …

Abstract

We consider \(m \times s\) matrices (with \(m\ge s\)) in a real affine subspace of dimension n. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank real algebraic set. The complexity of our algorithm is studied thoroughly. It is polynomial in \(\left( {\begin{array}{c}n+m(s-r)\\ n\end{array}}\right) \). It improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.
Vorheriger Artikel Algorithms for group actions in arbitrary characteristic and a problem in singularity theory
Nächster Artikel Linear codes over and the MacWilliams identities

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
1.
Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2009)MATH
2.
Arbarello, E., Cornalba, M., Griffiths, P.A.: Geometry of Algebraic Curves: Volume II with a Contribution by Joseph Daniel Harris, vol. 267. Springer, Berlin (2011)CrossRef
3.
Bank, B., Giusti, M., Heintz, J., Lecerf, G., Matera, G., Solernó, P.: Degeneracy loci and polynomial equation solving. Found. Comput. Math. 15(1), 159–184 (2015)MathSciNetCrossRef
4.
Bank, B., Giusti, M., Heintz, J., Mbakop, G.-M.: Polar varieties and efficient real elimination. Math. Z. 238(1), 115–144 (2001)MathSciNetCrossRef
5.
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic in Mathematics. Algorithms and Computation in Mathematics, vol. 10, 2nd edn. Springer, Berlin (2006)CrossRef
6.
Bonnard, B., Faugère, J-C., Jacquemard, A., Safey El Din, M., Verron, T.: Determinantal sets, singularities and application to optimal control in medical imagery. In: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’16, pp. 103–110, ACM, New York (2016)
7.
Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Automata Theory and Formal Languages (Second GI Conf., Kaiserslautern, 1975), pp. 134–183. Lecture Notes in Computer Science, vol. 33. Springer, Berlin (1975)
8.
Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry. Graduate Texts in Mathematics, vol. 150. Springer, Berlin (1995)MATH
9.
Faugère, J-C.: Fgb: a library for computing Gröbner bases. In: International Congress on Mathematical Software, pp. 84–87. Springer, Berlin (2010)CrossRef
10.
Faugère, J.-C., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993)CrossRef
11.
Faugère, J.-C., Safey El Din, M., Spaenlehauer, P.-J.: On the complexity of the generalized minrank problem. J. Symb. Comput. 55, 30–58 (2013)MathSciNetCrossRef
12.
Gianni, P., Mora, T.: Algebraic solution of systems of polynomial equations using Groebner bases. In: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, vol. 356 of Lecture Notes in Computer Science, pp. 247–257. Springer, Berlin (1989)CrossRef
13.
Giusti, M., Lecerf, G., Salvy, B.: A Gröbner-free alternative for polynomial system solving. J. Complex. 17(1), 154–211 (2001)CrossRef
14.
Greuet, A., Safey El Din, M.: Probabilistic algorithm for the global optimization of a polynomial over a real algebraic set. SIAM J. Optim. 24(3), 1313–1343 (2014)MathSciNetCrossRef
15.
Grigoriev, D., Vorobjov, N.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1/2), 37–64 (1988)MathSciNetCrossRef
16.
Harris, J.: Algebraic Geometry: A First Course, vol. 133. Springer, Berlin (1992)CrossRef
17.
Hartshorne, R.: Algebraic Geometry, vol. 52. Springer, Berlin (2013)MATH
18.
Henrion, D., Naldi, S., Safey El Din, M.: Real root finding for determinants of linear matrices. J. Symb. Comput. 74, 205–238 (2015)MathSciNetCrossRef
19.
Henrion, D., Naldi, S., Safey El Din, M.: Real root finding for rank defects in linear Hankel matrices. In: Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation, Bath (UK), pp. 221–228 (2015)
20.
Henrion, D., Naldi, S., Safey El Din, M.: Exact algorithms for linear matrix inequalities. SIAM J. Optim. 26(4), 2512–2539 (2016)MathSciNetCrossRef
21.
Henrion, D., Naldi, S., Safey El Din, M.: Spectra: a Maple library for solving linear matrix inequalities in exact arithmetic. Optim. Methods Softw. 34(1), 62–78 (2019)MathSciNetCrossRef
22.
Jeronimo, G., Matera, G., Solernó, P., Waissbein, A.: Deformation techniques for sparse systems. Found. Comput. Math. 9(1), 1–50 (2009)MathSciNetCrossRef
23.
Kileel, J., Kukelova, Z., Pajdla, T., Sturmfels, B.: Distortion varieties. Found. Comput. Math. 18(4), 1043–1071 (2018)MathSciNetCrossRef
24.
Kronecker, L.: Grundzüge einer arithmetischen theorie der algebraischen Grössen. J. für die Reine und angewandte Math. 92, 1–122 (1882)MathSciNetMATH
25.
Lasserre, J.-B.: Moments, Positive Polynomials and Their Applications. Optimization Series, vol. 1. Imperial College Press, London (2010)MATH
26.
Lecerf, G.: Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions. In: Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, ISSAC ’00, pp. 209–216, New York. ACM (2000)
27.
Macaulay, F.S.: The Algebraic Theory of Modular Systems. Cambridge University Press, Cambridge (1916)MATH
28.
Ottaviani, G., Spaenlehauer, P.-J., Sturmfels, B.: Exact solutions in structured low-rank approximation. SIAM J. Matrix Anal. Appl. 35(4), 1521–1542 (2014)MathSciNetCrossRef
29.
Poteaux, A., Schost, É.: On the complexity of computing with zero-dimensional triangular sets. J. Symb. Comput. 50, 110–138 (2013)MathSciNetCrossRef
30.
Ranestad, K.: Algebraic degree in semidefinite and polynomial optimization. In: Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 61–75. Springer, Berlin (2012)MATH
31.
Rouillier, F.: Solving zero-dimensional systems through the rational univariate representation. Appl. Algebra Eng. Commun. Comput. 9(5), 433–461 (1999)MathSciNetCrossRef
32.
Safey El Din, M.: Raglib (Real Algebraic Geometry library), Maple package (2007)
33.
Safey El Din, M., Schost, É.: Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ISSAC ’03, pp. 224–231, New York, NY. ACM (2003)
34.
Safey El Din, M., Schost, E.: A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. J. ACM 63(48), (2017)
35.
Safey El Din, M., Schost, É.: Bit complexity for multi-homogeneous polynomial system solving: application to polynomial minimization. J. Symb. Comput. 87, 176–206 (2018)MathSciNetCrossRef
36.
Shafarevich, I.: Basic Algebraic Geometry 1. Springer, Berlin (1977)
37.
Tarski, A.: A Decision Method for Elementary Algebra and Geometry. University of California Press, California (1951)MATH
Metadaten
Titel
Real root finding for low rank linear matrices
verfasst von
Didier Henrion
Simone Naldi
Mohab Safey El Din
Publikationsdatum
25.07.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing / Ausgabe 2/2020
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-019-00396-w