Real root finding for determinants of linear matrices

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Real root finding for determinants of linear matrices

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Real root finding for determinants of linear matrices

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název periodika

Journal of Symbolic Computation

ISSN

0747-7171

e-ISSN

—

Svazek periodika

74

Číslo periodika v rámci svazku

May-June

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

34

Strana od-do

205-238

Kód UT WoS článku

000366794100011

EID výsledku v databázi Scopus

2-s2.0-84948720100