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
Applicable Algebra in Engineering, Communication and Computing
Published in: Applicable Algebra in Engineering, Communication and Computing 2/2020

25-07-2019 | Original Paper

Real root finding for low rank linear matrices

Authors: Didier Henrion, Simone Naldi, Mohab Safey El Din

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 2/2020

Log in

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

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.
previous article Algorithms for group actions in arbitrary characteristic and a problem in singularity theory
next article Linear codes over and the MacWilliams identities

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 "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

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
Literature
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
Metadata
Title
Real root finding for low rank linear matrices
Authors
Didier Henrion
Simone Naldi
Mohab Safey El Din
Publication date
25-07-2019
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 2/2020
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-019-00396-w

Premium Partner

    Image Credits