Complexity issues for the symmetric interval eigenvalue problem
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10313041" target="_blank" >RIV/00216208:11320/15:10313041 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1515/math-2015-0015" target="_blank" >http://dx.doi.org/10.1515/math-2015-0015</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1515/math-2015-0015" target="_blank" >10.1515/math-2015-0015</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Complexity issues for the symmetric interval eigenvalue problem
Popis výsledku v původním jazyce
We study the problem of computing the maximal and minimal possible eigenvalues of a symmetric matrix when the matrix entries vary within compact intervals. In particular, we focus on computational complexity of determining these extremal eigenvalues withsome approximation error. Besides the classical absolute and relative approximation errors, which turn out not to be suitable for this problem, we adapt a less known one related to the relative error, and also propose a novel approximation error. We show in which error factors the problem is polynomially solvable and in which factors it becomes NP-hard.
Název v anglickém jazyce
Complexity issues for the symmetric interval eigenvalue problem
Popis výsledku anglicky
We study the problem of computing the maximal and minimal possible eigenvalues of a symmetric matrix when the matrix entries vary within compact intervals. In particular, we focus on computational complexity of determining these extremal eigenvalues withsome approximation error. Besides the classical absolute and relative approximation errors, which turn out not to be suitable for this problem, we adapt a less known one related to the relative error, and also propose a novel approximation error. We show in which error factors the problem is polynomially solvable and in which factors it becomes NP-hard.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2015
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ů
Údaje specifické pro druh výsledku
Název periodika
Open Mathematics [online]
ISSN
2391-5455
e-ISSN
—
Svazek periodika
13
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
8
Strana od-do
157-164
Kód UT WoS článku
000349284200015
EID výsledku v databázi Scopus
2-s2.0-84959539782