Complexity issues for the symmetric interval eigenvalue problem

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>

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.

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

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

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ů

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