{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T19:50:24Z","timestamp":1790365824427,"version":"4.1.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T00:00:00Z","timestamp":1472688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"PGMO programme of EDF and FMJH"},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-12-INSE-0007, ANR-13-INSE-0003"],"award-info":[{"award-number":["ANR-12-INSE-0007, ANR-13-INSE-0003"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ICODE"},{"name":"Complex Systems Engineering Research Chair of Ecole polytechnique, THALES, FX, DGA, DASSAULT AVIATION, DCNS Research, ENSTA ParisTech, T\u00e9l\u00e9com ParisTech, Fondation ParisTech, FDO ENSTA"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>\n            We present a new numerical abstract domain based on ellipsoids designed for the formal verification of switched linear systems. Unlike the existing approaches, this domain does not rely on a user-given template. We overcome the difficulty that ellipsoids do not have a lattice structure by exhibiting a canonical operator overapproximating the union. This operator is the only one that permits the performance of analyses that are invariant with respect to a linear transformation of state variables. It provides the minimum volume ellipsoid enclosing two given ellipsoids. We show that it can be computed in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) elementary algebraic operations. We finally develop a fast nonlinear power-type algorithm, which allows one to determine sound quadratic invariants on switched systems in a tractable way, by solving fixed-point problems over the space of ellipsoids. We test our approach on several benchmarks, and compare it with the standard techniques based on linear matrix inequalities, showing an important speedup on typical instances.\n          <\/jats:p>","DOI":"10.1145\/2932187","type":"journal-article","created":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T18:24:38Z","timestamp":1472754278000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A Scalable Algebraic Method to Infer Quadratic Invariants of Switched Systems"],"prefix":"10.1145","volume":"15","author":[{"given":"Xavier","family":"Allamigeon","sequence":"first","affiliation":[{"name":"INRIA and CMAP, \u00c9cole polytechnique, CNRS, Palaiseau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phane","family":"Gaubert","sequence":"additional","affiliation":[{"name":"INRIA and CMAP, \u00c9cole polytechnique, CNRS, Palaiseau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikolas","family":"Stott","sequence":"additional","affiliation":[{"name":"INRIA and CMAP, \u00c9cole polytechnique, CNRS, Palaiseau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00c9ric","family":"Goubault","sequence":"additional","affiliation":[{"name":"LIX, \u00c9cole polytechnique, CNRS, Palaiseau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sylvie","family":"Putot","sequence":"additional","affiliation":[{"name":"LIX, \u00c9cole polytechnique, CNRS, Palaiseau"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46081-8_6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(1:1)2012"},{"key":"e_1_2_1_3_1","volume-title":"Matrix Information Geometry","author":"Angulo J.","unstructured":"J. Angulo . 2013. Supremum\/infimum and nonlinear averaging of positive definite symmetric matrices. In Matrix Information Geometry . Springer , New York, NY , 3--24. J. Angulo. 2013. Supremum\/infimum and nonlinear averaging of positive definite symmetric matrices. In Matrix Information Geometry. Springer, New York, NY, 3--24."},{"key":"e_1_2_1_4_1","first-page":"7","article-title":"Stability of dynamical polysystems via families of Liapunov functions","volume":"67","author":"Bacciotti A.","year":"2007","unstructured":"A. Bacciotti and L. Mazzi . 2007 . Stability of dynamical polysystems via families of Liapunov functions . Journal of Nonlinear Analysis and Application 67 , 7 (Oct. 2007), 2167--2179. A. Bacciotti and L. Mazzi. 2007. Stability of dynamical polysystems via families of Liapunov functions. Journal of Nonlinear Analysis and Application 67, 7 (Oct. 2007), 2167--2179.","journal-title":"Journal of Nonlinear Analysis and Application"},{"key":"e_1_2_1_5_1","volume-title":"Flavors of Geometry","author":"Ball K.","unstructured":"K. Ball . 1997. An elementary introduction to modern convex geometry . In Flavors of Geometry . Mathematical Sciences Research Institute Publications, Vol . 31. Cambridge University Press , New York, NY, 1--58. DOI:http:\/\/dx.doi.org\/10.2977\/prims\/1195164788 10.2977\/prims K. Ball. 1997. An elementary introduction to modern convex geometry. In Flavors of Geometry. Mathematical Sciences Research Institute Publications, Vol. 31. Cambridge University Press, New York, NY, 1--58. DOI:http:\/\/dx.doi.org\/10.2977\/prims\/1195164788"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"R. Bhatia. 2003. On the exponential metric increasing property. Linear Algebra and its Applications 375 211--220.  R. Bhatia. 2003. On the exponential metric increasing property. Linear Algebra and its Applications 375 211--220.","DOI":"10.1016\/S0024-3795(03)00647-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781153"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.664150"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2005.12.012"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30579-8_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31987-0_3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/512760.512770"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24725-8_4"},{"key":"e_1_2_1_15_1","unstructured":"E. Feron and F. Alegre. 2008a. Control software analysis Part I: Open-loop properties. CoRR abs\/0809.4812.  E. Feron and F. Alegre. 2008a. Control software analysis Part I: Open-loop properties. CoRR abs\/0809.4812."},{"key":"e_1_2_1_16_1","volume-title":"Part II: Closed-loop analysis. CoRR abs\/0812.1986.","author":"Feron E.","year":"2008","unstructured":"E. Feron and F. Alegre . 2008 b. Control software analysis, Part II: Closed-loop analysis. CoRR abs\/0812.1986. E. Feron and F. Alegre. 2008b. Control software analysis, Part II: Closed-loop analysis. CoRR abs\/0812.1986."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"G.\n      Gange J. A.\n      Navas P.\n      Schachte H.\n      S\u00f8ndergaard and \n      P. J.\n      Stuckey\n  . \n  2013\n  . Abstract interpretation over non-lattice abstract domains. In Static Analysis Lecture Notes in Computer Science Vol. \n  7935\n  . \n  Springer Berlin 6--24.  G. Gange J. A. Navas P. Schachte H. S\u00f8ndergaard and P. J. Stuckey. 2013. Abstract interpretation over non-lattice abstract domains. In Static Analysis Lecture Notes in Computer Science Vol. 7935. Springer Berlin 6--24.","DOI":"10.1007\/978-3-642-38856-9_3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004111000673"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_47"},{"key":"e_1_2_1_20_1","volume-title":"Matrix Computations","author":"Golub G. H.","unstructured":"G. H. Golub and C. F. Van Loan . 2013. Matrix Computations . Johns Hopkins University Press , Baltimore, MD . G. H. Golub and C. F. Van Loan. 2013. Matrix Computations. Johns Hopkins University Press, Baltimore, MD."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38856-9_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.664157"},{"key":"e_1_2_1_23_1","first-page":"143","article-title":"Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete and Continuous Dynamic Systems","volume":"14","author":"Kozyakin V.","year":"2010","unstructured":"V. Kozyakin . 2010 . Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete and Continuous Dynamic Systems , Series B 14 , 1, 143 -- 158 . V. Kozyakin. 2010. Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete and Continuous Dynamic Systems, Series B 14, 1, 143--158.","journal-title":"Series B"},{"key":"e_1_2_1_24_1","unstructured":"M. G. Krein and M. A. Rutman. 1948. Linear operators leaving invariant a cone in a Banach space. Uspehi Matematic&cbreve;eskih Nauk 3 3--95. AMS Translations Number 26.  M. G. Krein and M. A. Rutman. 1948. Linear operators leaving invariant a cone in a Banach space. Uspehi Matematic&cbreve;eskih Nauk 3 3--95. AMS Translations Number 26."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"A. B. Kurzhanski and I. V\u00e1lyi. 1997. Ellipsoidal Calculus for Estimation and Control. International Institute for Applied Systems Analysis Boston MA.  A. B. Kurzhanski and I. V\u00e1lyi. 1997. Ellipsoidal Calculus for Estimation and Control. International Institute for Applied Systems Analysis Boston MA.","DOI":"10.1007\/978-1-4612-0277-6"},{"key":"e_1_2_1_26_1","volume-title":"Switching in Systems and Control","author":"Liberzon D.","unstructured":"D. Liberzon . 2003. Switching in Systems and Control . Springer , New York, NY . D. Liberzon. 2003. Switching in Systems and Control. Springer, New York, NY."},{"key":"e_1_2_1_27_1","volume-title":"Retrieved","author":"MathWorks Inc.","year":"2007","unstructured":"MathWorks Inc. 2007 . Polyspace static analyzer . Retrieved July 14, 2016 from http:\/\/fr.mathworks.com\/ products\/polyspace\/. MathWorks Inc. 2007. Polyspace static analyzer. Retrieved July 14, 2016 from http:\/\/fr.mathworks.com\/ products\/polyspace\/."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/0391"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 27th International Conference on Computer Aided Verification (CAV\u201915)","author":"Oulamara M.","year":"2015","unstructured":"M. Oulamara and A. J. Venet . 2015 . Proceedings of the 27th International Conference on Computer Aided Verification (CAV\u201915) , Part I, San Francisco, CA , July 18-24, 2015 . Springer International Publishing, Cham, Chapter Abstract Interpretation with Higher-Dimensional Ellipsoids and Conic Extrapolation, 415--430. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-319-21690-4_24 10.1007\/978-3-319-21690-4_24 M. Oulamara and A. J. Venet. 2015. Proceedings of the 27th International Conference on Computer Aided Verification (CAV\u201915), Part I, San Francisco, CA, July 18-24, 2015. Springer International Publishing, Cham, Chapter Abstract Interpretation with Higher-Dimensional Ellipsoids and Conic Extrapolation, 415--430. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-319-21690-4_24"},{"key":"e_1_2_1_30_1","volume-title":"Convexity and Nonpositive Curvature","author":"Papadopoulos A.","unstructured":"A. Papadopoulos . 2005. Metric Spaces , Convexity and Nonpositive Curvature . European Mathematical Society . A. Papadopoulos. 2005. Metric Spaces, Convexity and Nonpositive Curvature. European Mathematical Society."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"P. A. Parrilo and A. Jadbabaie. 2008. Approximation of the joint spectral radius using sum of squares. Linear Algebra and its Applications 428 10 2385--2402.  P. A. Parrilo and A. Jadbabaie. 2008. Approximation of the joint spectral radius using sum of squares. Linear Algebra and its Applications 428 10 2385--2402.","DOI":"10.1016\/j.laa.2007.12.027"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of ACC. 1679--1684","author":"Peleties P.","unstructured":"P. Peleties and R. A. DeCarlo . 1991. Asymptotic stability of m-switched systems using Lyapunov-like functions . In Proceedings of ACC. 1679--1684 . P. Peleties and R. A. DeCarlo. 1991. Asymptotic stability of m-switched systems using Lyapunov-like functions. In Proceedings of ACC. 1679--1684."},{"key":"e_1_2_1_33_1","unstructured":"J. Rohn. 2005. A Handbook of Results on Interval Linear Problems. http:\/\/www.nsc.ru\/interval\/Library\/Surveys\/ILinProblems.pdf.  J. Rohn. 2005. A Handbook of Results on Interval Linear Problems. http:\/\/www.nsc.ru\/interval\/Library\/Surveys\/ILinProblems.pdf."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2241472"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185632.2185651"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30579-8_2"},{"key":"e_1_2_1_38_1","volume-title":"American Control Conference (ACC)","author":"Shaker H. R.","unstructured":"H. R. Shaker and J. P. How . 2010. Stability analysis for class of switched nonlinear systems . In American Control Conference (ACC) . Baltimore, MD, 2517--2520. H. R. Shaker and J. P. How. 2010. Stability analysis for class of switched nonlinear systems. In American Control Conference (ACC). Baltimore, MD, 2517--2520."},{"key":"e_1_2_1_39_1","series-title":"Lecture Notes in Mathematics","volume-title":"Matrix Inequalities","author":"Zhan X.","unstructured":"X. Zhan . 2002. Matrix Inequalities . Lecture Notes in Mathematics , Vol. 1790 . Springer , Berlin . viii+116 pages. X. Zhan. 2002. Matrix Inequalities. Lecture Notes in Mathematics, Vol. 1790. Springer, Berlin. viii+116 pages."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2932187","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2932187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:38:51Z","timestamp":1750268331000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2932187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1145\/2932187"],"URL":"https:\/\/doi.org\/10.1145\/2932187","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}