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

Result code in 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>

Alternative codes found

RIV/67985807:_____/18:00497748

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

50201 - Economic Theory

Project

<a href="/en/project/GA18-04735S" target="_blank" >GA18-04735S: Novel approaches for relaxation and approximation techniques in deterministic global optimization</a><br>

Continuities

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

Publication year

2018

Confidentiality

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

Name of the periodical

Electronic Journal Of Linear Algebra

ISSN

1537-9582

e-ISSN

—

Volume of the periodical

33

Issue of the periodical within the volume

December

Country of publishing house

US - UNITED STATES

Number of pages

15

Pages from-to

122-136

UT code for WoS article

000485374300012

EID of the result in the Scopus database

2-s2.0-85067679884