{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:19:50Z","timestamp":1758709190704},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T00:00:00Z","timestamp":1564012800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T00:00:00Z","timestamp":1564012800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s00200-019-00396-w","type":"journal-article","created":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T07:33:11Z","timestamp":1564039991000},"page":"101-133","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Real root finding for low rank linear matrices"],"prefix":"10.1007","volume":"31","author":[{"given":"Didier","family":"Henrion","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simone","family":"Naldi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohab Safey El","family":"Din","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,25]]},"reference":[{"key":"396_CR1","volume-title":"Optimization Algorithms on Matrix Manifolds","author":"P-A Absil","year":"2009","unstructured":"Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2009)"},{"key":"396_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69392-5","volume-title":"Geometry of Algebraic Curves: Volume II with a Contribution by Joseph Daniel Harris","author":"E Arbarello","year":"2011","unstructured":"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)"},{"issue":"1","key":"396_CR3","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10208-014-9214-z","volume":"15","author":"B Bank","year":"2015","unstructured":"Bank, B., Giusti, M., Heintz, J., Lecerf, G., Matera, G., Solern\u00f3, P.: Degeneracy loci and polynomial equation solving. Found. Comput. Math. 15(1), 159\u2013184 (2015)","journal-title":"Found. Comput. Math."},{"issue":"1","key":"396_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/PL00004896","volume":"238","author":"B Bank","year":"2001","unstructured":"Bank, B., Giusti, M., Heintz, J., Mbakop, G.-M.: Polar varieties and efficient real elimination. Math. Z. 238(1), 115\u2013144 (2001)","journal-title":"Math. Z."},{"key":"396_CR5","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic in Mathematics","author":"S Basu","year":"2006","unstructured":"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)","edition":"2"},{"key":"396_CR6","doi-asserted-by":"crossref","unstructured":"Bonnard, B., Faug\u00e8re, J-C., Jacquemard, A., Safey El\u00a0Din, 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 \u201916, pp. 103\u2013110, ACM, New York (2016)","DOI":"10.1145\/2930889.2930916"},{"key":"396_CR7","first-page":"134","volume-title":"Lecture Notes in Computer Science","author":"George E. Collins","year":"1975","unstructured":"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\u2013183. Lecture Notes in Computer Science, vol. 33. Springer, Berlin (1975)"},{"key":"396_CR8","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-5350-1","volume-title":"Commutative Algebra with a View Toward Algebraic Geometry","author":"D Eisenbud","year":"1995","unstructured":"Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry. Graduate Texts in Mathematics, vol. 150. Springer, Berlin (1995)"},{"key":"396_CR9","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-15582-6_17","volume-title":"Mathematical Software \u2013 ICMS 2010","author":"Jean-Charles Faug\u00e8re","year":"2010","unstructured":"Faug\u00e8re, J-C.: Fgb: a library for computing Gr\u00f6bner bases. In: International Congress on Mathematical Software, pp. 84\u201387. Springer, Berlin (2010)"},{"issue":"4","key":"396_CR10","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1006\/jsco.1993.1051","volume":"16","author":"J-C Faug\u00e8re","year":"1993","unstructured":"Faug\u00e8re, J.-C., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gr\u00f6bner bases by change of ordering. J. Symb. Comput. 16(4), 329\u2013344 (1993)","journal-title":"J. Symb. Comput."},{"key":"396_CR11","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.jsc.2013.03.004","volume":"55","author":"J-C Faug\u00e8re","year":"2013","unstructured":"Faug\u00e8re, J.-C., Safey El\u00a0Din, M., Spaenlehauer, P.-J.: On the complexity of the generalized minrank problem. J. Symb. Comput. 55, 30\u201358 (2013)","journal-title":"J. Symb. Comput."},{"key":"396_CR12","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-51082-6_83","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"Patrizia Gianni","year":"1989","unstructured":"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\u2013257. Springer, Berlin (1989)"},{"issue":"1","key":"396_CR13","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/jcom.2000.0571","volume":"17","author":"M Giusti","year":"2001","unstructured":"Giusti, M., Lecerf, G., Salvy, B.: A Gr\u00f6bner-free alternative for polynomial system solving. J. Complex. 17(1), 154\u2013211 (2001)","journal-title":"J. Complex."},{"issue":"3","key":"396_CR14","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1137\/130931308","volume":"24","author":"A Greuet","year":"2014","unstructured":"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\u20131343 (2014)","journal-title":"SIAM J. Optim."},{"issue":"1\/2","key":"396_CR15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"D Grigoriev","year":"1988","unstructured":"Grigoriev, D., Vorobjov, N.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1\/2), 37\u201364 (1988)","journal-title":"J. Symb. Comput."},{"key":"396_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2189-8","volume-title":"Algebraic Geometry: A First Course","author":"J Harris","year":"1992","unstructured":"Harris, J.: Algebraic Geometry: A First Course, vol. 133. Springer, Berlin (1992)"},{"key":"396_CR17","volume-title":"Algebraic Geometry","author":"R Hartshorne","year":"2013","unstructured":"Hartshorne, R.: Algebraic Geometry, vol. 52. Springer, Berlin (2013)"},{"key":"396_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/j.jsc.2015.06.010","volume":"74","author":"D Henrion","year":"2015","unstructured":"Henrion, D., Naldi, S., Safey El Din, M.: Real root finding for determinants of linear matrices. J. Symb. Comput. 74, 205\u2013238 (2015)","journal-title":"J. Symb. Comput."},{"key":"396_CR19","doi-asserted-by":"crossref","unstructured":"Henrion, D., Naldi, S., Safey El\u00a0Din, 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\u2013228 (2015)","DOI":"10.1145\/2755996.2756667"},{"issue":"4","key":"396_CR20","doi-asserted-by":"publisher","first-page":"2512","DOI":"10.1137\/15M1036543","volume":"26","author":"D Henrion","year":"2016","unstructured":"Henrion, D., Naldi, S., Safey El Din, M.: Exact algorithms for linear matrix inequalities. SIAM J. Optim. 26(4), 2512\u20132539 (2016)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"396_CR21","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1080\/10556788.2017.1341505","volume":"34","author":"D Henrion","year":"2019","unstructured":"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\u201378 (2019)","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"396_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10208-008-9024-2","volume":"9","author":"G Jeronimo","year":"2009","unstructured":"Jeronimo, G., Matera, G., Solern\u00f3, P., Waissbein, A.: Deformation techniques for sparse systems. Found. Comput. Math. 9(1), 1\u201350 (2009)","journal-title":"Found. Comput. Math."},{"issue":"4","key":"396_CR23","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1007\/s10208-017-9361-0","volume":"18","author":"J Kileel","year":"2018","unstructured":"Kileel, J., Kukelova, Z., Pajdla, T., Sturmfels, B.: Distortion varieties. Found. Comput. Math. 18(4), 1043\u20131071 (2018)","journal-title":"Found. Comput. Math."},{"key":"396_CR24","first-page":"1","volume":"92","author":"L Kronecker","year":"1882","unstructured":"Kronecker, L.: Grundz\u00fcge einer arithmetischen theorie der algebraischen Gr\u00f6ssen. J. f\u00fcr die Reine und angewandte Math. 92, 1\u2013122 (1882)","journal-title":"J. f\u00fcr die Reine und angewandte Math."},{"key":"396_CR25","series-title":"Optimization Series","volume-title":"Moments, Positive Polynomials and Their Applications","author":"J-B Lasserre","year":"2010","unstructured":"Lasserre, J.-B.: Moments, Positive Polynomials and Their Applications. Optimization Series, vol. 1. Imperial College Press, London (2010)"},{"key":"396_CR26","doi-asserted-by":"crossref","unstructured":"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 \u201900, pp. 209\u2013216, New York. ACM (2000)","DOI":"10.1145\/345542.345633"},{"key":"396_CR27","doi-asserted-by":"crossref","DOI":"10.3792\/chmm\/1263317740","volume-title":"The Algebraic Theory of Modular Systems","author":"FS Macaulay","year":"1916","unstructured":"Macaulay, F.S.: The Algebraic Theory of Modular Systems. Cambridge University Press, Cambridge (1916)"},{"issue":"4","key":"396_CR28","doi-asserted-by":"publisher","first-page":"1521","DOI":"10.1137\/13094520X","volume":"35","author":"G Ottaviani","year":"2014","unstructured":"Ottaviani, G., Spaenlehauer, P.-J., Sturmfels, B.: Exact solutions in structured low-rank approximation. SIAM J. Matrix Anal. Appl. 35(4), 1521\u20131542 (2014)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"396_CR29","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.jsc.2012.05.008","volume":"50","author":"A Poteaux","year":"2013","unstructured":"Poteaux, A., Schost, \u00c9.: On the complexity of computing with zero-dimensional triangular sets. J. Symb. Comput. 50, 110\u2013138 (2013)","journal-title":"J. Symb. Comput."},{"key":"396_CR30","first-page":"61","volume-title":"Handbook on Semidefinite, Conic and Polynomial Optimization","author":"Kristian Ranestad","year":"2011","unstructured":"Ranestad, K.: Algebraic degree in semidefinite and polynomial optimization. In: Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 61\u201375. Springer, Berlin (2012)"},{"issue":"5","key":"396_CR31","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s002000050114","volume":"9","author":"F Rouillier","year":"1999","unstructured":"Rouillier, F.: Solving zero-dimensional systems through the rational univariate representation. Appl. Algebra Eng. Commun. Comput. 9(5), 433\u2013461 (1999)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"396_CR32","unstructured":"Safey El Din, M.: Raglib (Real Algebraic Geometry library), Maple package (2007)"},{"key":"396_CR33","doi-asserted-by":"crossref","unstructured":"Safey El\u00a0Din, M., Schost, \u00c9.: 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 \u201903, pp. 224\u2013231, New York, NY. ACM (2003)","DOI":"10.1145\/860854.860901"},{"key":"396_CR34","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1145\/2996450"},{"key":"396_CR35","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.jsc.2017.08.001","volume":"87","author":"M Safey El Din","year":"2018","unstructured":"Safey El Din, M., Schost, \u00c9.: Bit complexity for multi-homogeneous polynomial system solving: application to polynomial minimization. J. Symb. Comput. 87, 176\u2013206 (2018)","journal-title":"J. Symb. Comput."},{"key":"396_CR36","volume-title":"Basic Algebraic Geometry 1","author":"I Shafarevich","year":"1977","unstructured":"Shafarevich, I.: Basic Algebraic Geometry 1. Springer, Berlin (1977)"},{"key":"396_CR37","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"A Tarski","year":"1951","unstructured":"Tarski, A.: A Decision Method for Elementary Algebra and Geometry. University of California Press, California (1951)"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-019-00396-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00200-019-00396-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-019-00396-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T14:48:13Z","timestamp":1664030893000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00200-019-00396-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,25]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["396"],"URL":"https:\/\/doi.org\/10.1007\/s00200-019-00396-w","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,25]]},"assertion":[{"value":"31 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}