Complexity of Computing Interval Matrix Powers for Special Classes of Matrices

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F20%3A00532104" target="_blank" >RIV/67985807:_____/20:00532104 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/20:10419270

Výsledek na webu

<a href="http://hdl.handle.net/11104/0310705" target="_blank" >http://hdl.handle.net/11104/0310705</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.21136/AM.2020.0379-19" target="_blank" >10.21136/AM.2020.0379-19</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity of Computing Interval Matrix Powers for Special Classes of Matrices

Popis výsledku v původním jazyce

Computing powers of interval matrices is a computationally hard problem. Indeed, it is NP-hard even when the exponent is 3 and the matrices only have interval components in one row and one column. Motivated by this result, we consider special types of interval matrices where the interval components occupy specific positions. We show that computing the third power of matrices with only one column occupied by interval components can be solved in cubic time. So the asymptotic time complexity is the same as for the real case (considering the textbook matrix product method). We further show that for a fixed exponent $k$ and for each interval matrix (of an arbitrary size) whose $k$th power has components that can be expressed as polynomials in a fixed number of interval variables, the computation of the $k$th power is polynomial up to a given accuracy. Polynomiality is shown by using the Tarski method of quantifier elimination. This result is used to show the polynomiality of computing the cube of interval band matrices, among others. Additionally, we study parametric matrices and prove NP-hardness already for their squares. We also describe one specific class of interval parametric matrices that can be squared by a polynomial algorithm.

Název v anglickém jazyce

Complexity of Computing Interval Matrix Powers for Special Classes of Matrices

Popis výsledku anglicky

Computing powers of interval matrices is a computationally hard problem. Indeed, it is NP-hard even when the exponent is 3 and the matrices only have interval components in one row and one column. Motivated by this result, we consider special types of interval matrices where the interval components occupy specific positions. We show that computing the third power of matrices with only one column occupied by interval components can be solved in cubic time. So the asymptotic time complexity is the same as for the real case (considering the textbook matrix product method). We further show that for a fixed exponent $k$ and for each interval matrix (of an arbitrary size) whose $k$th power has components that can be expressed as polynomials in a fixed number of interval variables, the computation of the $k$th power is polynomial up to a given accuracy. Polynomiality is shown by using the Tarski method of quantifier elimination. This result is used to show the polynomiality of computing the cube of interval band matrices, among others. Additionally, we study parametric matrices and prove NP-hardness already for their squares. We also describe one specific class of interval parametric matrices that can be squared by a polynomial algorithm.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA18-04735S" target="_blank" >GA18-04735S: Nové přístupy pro relaxační a aproximační techniky v deterministické globální optimalizaci</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

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

Applications of Mathematics

ISSN

0862-7940

e-ISSN

—

Svazek periodika

65

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

CZ - Česká republika

Počet stran výsledku

19

Strana od-do

645-663

Kód UT WoS článku

000576794600007

EID výsledku v databázi Scopus

2-s2.0-85092282996