All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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