Regularity radius: Properties, approximation and a not a priori exponential algorithm

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385603" target="_blank" >RIV/00216208:11320/18:10385603 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/67985807:_____/18:00497748

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=skMiahwYZS" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=skMiahwYZS</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.13001/1081-3810.3749" target="_blank" >10.13001/1081-3810.3749</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Regularity radius: Properties, approximation and a not a priori exponential algorithm

Popis výsledku v původním jazyce

The radius of regularity, sometimes spelled as the radius of nonsingularity, is a measure providing the distance of a given matrix to the nearest singular one. Despite its possible application strength this measure is still far from being handled in an efficient way also due to findings of Poljak and Rohn providing proof that checking this property is NP-hard for a general matrix. There are basically two approaches to handle this situation. Firstly, approximation algorithms are applied and secondly, tighter bounds for radius of regularity are considered. Improvements of both approaches have been recently shown by Hartman and Hlad&apos;ik (doi:10.1007/978-3-319-31769-4_9) utilizing relaxation of the radius computation to semidefinite programming. An estimation of the regularity radius using any of the above mentioned approaches is usually applied to general matrices considering none or just weak assumptions about the original matrix. Surprisingly less explored area is represented by utilization of properties of special classes of matrices as well as utilization of classical algorithms extended to be used to compute the considered radius. This work explores a process of regularity radius analysis and identifies useful properties enabling easier estimation of the corresponding radius values. At first, checking finiteness of this characteristic is shown to be a polynomial problem along with determining a sharp upper bound on the number of nonzero elements of the matrix to obtain infinite radius. Further, relationship between maximum (Chebyshev) norm and spectral norm is used to construct new bounds for the radius of regularity. Considering situations where the known bounds are not tight enough, a new method based on Jansson-Rohn algorithm for testing regularity of an interval matrix is presented which is not a priory exponential along with numerical experiments. For a situation where an input matrix has a special form, several corresponding results are provided such as exact formulas for several special classes of matrices, e.g., for totally positive and inverse non-negative, or approximation algorithms, e.g., rank-one radius matrices. For tridiagonal matrices, an algorithm by Bar-On, Codenotti and Leoncini is utilized to design a polynomial algorithm to compute the radius of regularity.

Název v anglickém jazyce

Regularity radius: Properties, approximation and a not a priori exponential algorithm

Popis výsledku anglicky

The radius of regularity, sometimes spelled as the radius of nonsingularity, is a measure providing the distance of a given matrix to the nearest singular one. Despite its possible application strength this measure is still far from being handled in an efficient way also due to findings of Poljak and Rohn providing proof that checking this property is NP-hard for a general matrix. There are basically two approaches to handle this situation. Firstly, approximation algorithms are applied and secondly, tighter bounds for radius of regularity are considered. Improvements of both approaches have been recently shown by Hartman and Hlad&apos;ik (doi:10.1007/978-3-319-31769-4_9) utilizing relaxation of the radius computation to semidefinite programming. An estimation of the regularity radius using any of the above mentioned approaches is usually applied to general matrices considering none or just weak assumptions about the original matrix. Surprisingly less explored area is represented by utilization of properties of special classes of matrices as well as utilization of classical algorithms extended to be used to compute the considered radius. This work explores a process of regularity radius analysis and identifies useful properties enabling easier estimation of the corresponding radius values. At first, checking finiteness of this characteristic is shown to be a polynomial problem along with determining a sharp upper bound on the number of nonzero elements of the matrix to obtain infinite radius. Further, relationship between maximum (Chebyshev) norm and spectral norm is used to construct new bounds for the radius of regularity. Considering situations where the known bounds are not tight enough, a new method based on Jansson-Rohn algorithm for testing regularity of an interval matrix is presented which is not a priory exponential along with numerical experiments. For a situation where an input matrix has a special form, several corresponding results are provided such as exact formulas for several special classes of matrices, e.g., for totally positive and inverse non-negative, or approximation algorithms, e.g., rank-one radius matrices. For tridiagonal matrices, an algorithm by Bar-On, Codenotti and Leoncini is utilized to design a polynomial algorithm to compute the radius of regularity.

Druh

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

CEP obor

—

OECD FORD obor

50201 - Economic Theory

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

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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

Electronic Journal Of Linear Algebra

ISSN

1537-9582

e-ISSN

—

Svazek periodika

33

Číslo periodika v rámci svazku

December

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

15

Strana od-do

122-136

Kód UT WoS článku

000485374300012

EID výsledku v databázi Scopus

2-s2.0-85067679884