Number of the records: 1
Tight Bounds on the Radius of Nonsingularity
- 1.
SYSNO ASEP 0459146 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Tight Bounds on the Radius of Nonsingularity Author(s) Hartman, David (UIVT-O) RID, SAI, ORCID
Hladík, M. (CZ)Source Title Scientific Computing, Computer Arithmetic, and Validated Numerics. Revised Selected Papers. - Cham : Springer, 2016 / Nehmeier M. ; Wolff von Gudenberg J. ; Tucker W. - ISSN 0302-9743 - ISBN 978-3-319-31768-7 Pages s. 109-115 Number of pages 7 s. Publication form Print - P Action SCAN 2014. International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics /16./ Event date 21.09.2014 - 26.09.2014 VEvent location Würzburg Country DE - Germany Event type WRD Language eng - English Country CH - Switzerland Keywords radius of nonsingularity ; bounds ; semidefinite programming Subject RIV IN - Informatics, Computer Science R&D Projects GA13-17187S GA ČR - Czech Science Foundation (CSF) Institutional support UIVT-O - RVO:67985807 UT WOS 000440867900009 EID SCOPUS 84963864062 DOI 10.1007/978-3-319-31769-4_9 Annotation Radius of nonsingularity of a square matrix is the minimal distance to a singular matrix in the maximum norm. Computing the radius of nonsingularity is an NP-hard problem. The known estimations are not very tight; one of the best one has the relative error 6n. We propose a randomized approximation method with a constant relative error 0.7834. It is based on a semidefinite relaxation. Semidefinite relaxation gives the best known approximation algorithm for MaxCut problem, and we utilize similar principle to derive tight bounds on the radius of nonsingularity. This gives us rigorous upper and lower bounds despite randomized character of the algorithm. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2017
Number of the records: 1