EXACT ALGORITHMS FOR LINEAR MATRIX INEQUALITIES
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00304330" target="_blank" >RIV/68407700:21230/16:00304330 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1137/15M1036543" target="_blank" >http://dx.doi.org/10.1137/15M1036543</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/15M1036543" target="_blank" >10.1137/15M1036543</a>
Alternative languages
Result language
angličtina
Original language name
EXACT ALGORITHMS FOR LINEAR MATRIX INEQUALITIES
Original language description
Let A(x) = A0 +x1A1+xnAn be a linear matrix, or pencil, generated by given symmetric matrices A0;A1;An of size m with rational entries. The set of real vectors x such that the pencil is positive semidefinite is a convex semialgebraic set called spectrahedron, described by a linear matrix inequality. We design an exact algorithm that, up to genericity assumptions on the input matrices, computes an exact algebraic representation of at least one point in the spectrahedron, or decides that it is empty. The algorithm does not assume the existence of an interior point, and the computed point minimizes the rank of the pencil on the spectrahedron. The degree d of the algebraic representation of the point coincides experimentally with the algebraic degree of a generic semide finite program associated to the pencil. We provide explicit bounds for the complexity of our algorithm, proving that the maximum number of arithmetic operations that are performed is essentially quadratic in a multilinear Bezout bound of d. When m (resp., n) is fixed, such a bound, and hence the complexity, is polynomial in n (resp., m). We conclude by providing results of experiments showing practical improvements with respect to state-of-The-Art computer algebra algorithms.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
SIAM JOURNAL ON OPTIMIZATION
ISSN
1052-6234
e-ISSN
—
Volume of the periodical
26
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
28
Pages from-to
2512-2539
UT code for WoS article
000391853600021
EID of the result in the Scopus database
2-s2.0-85007170438