Real root finding for determinants of linear matrices

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00234174" target="_blank" >RIV/68407700:21230/16:00234174 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.jsc.2015.06.010" target="_blank" >http://dx.doi.org/10.1016/j.jsc.2015.06.010</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jsc.2015.06.010" target="_blank" >10.1016/j.jsc.2015.06.010</a>

Result language
angličtina
Original language name
Real root finding for determinants of linear matrices
Original language description
Let A0, A1, ..., Anbe given square matrices of size mwith rational coefficients. The paper focuses on the exact computation of one point in each connected component of the real determinantal vari-ety {x elementRn:det(A0+x1A1+...+xnAn) =0}. Such a problem finds applications in many areas such as control theory, computational geometry, optimization, etc. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially polynomial in the bino-mial coefficient n+mn. We also report on experiments with a com-puter implementation of this algorithm. Its practical performance illustrates the complexity estimates. In particular, we emphasize that for subfamilies of this problem where mis fixed, the com-plexity is polynomial inn.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)