Jaroslav Horáček, Milan Hladík, and Michal Černý. Interval linear algebra and computational complexity. In Natália Bebiano, editor, Applied and Computational Matrix Analysis, Springer Proceedings in Mathematics & Statistics, pp. 37–66, Springer, 2017.
[PDF] [gzipped postscript] [postscript] [HTML]
This work connects two mathematical fields - computational complexity and interval linear algebra. It introduces the basic topics of interval linear algebra - regularity and singularity, full column rank, solving a linear system, deciding solvability of a linear system, computing inverse matrix, eigenvalues, checking positive (semi)definiteness or stability. We discuss these problems and relations between them from the view of computational complexity. Many problems in interval linear algebra are intractable, hence we emphasize subclasses of these problems that are easily solvable or decidable. The aim of this work is to provide a basic insight into this field and to provide materials for further reading and research.
@inCollection{HorHla2017a,
author = "Jaroslav Hor\'{a}{\v{c}}ek and Milan Hlad\'{\i}k and Michal {\v{C}}ern\'{y}",
title = "Interval linear algebra and computational complexity",
editor = "Bebiano, Nat{\'a}lia",
booktitle = "Applied and Computational Matrix Analysis",
fbooktitle = "Applied and Computational Matrix Analysis. MAT-TRIAD, Coimbra, Portugal, September 2015 Selected, Revised Contributions",
publisher = "Springer",
series = "Springer Proceedings in Mathematics \& Statistics",
volume = "192",
pages = "37-66",
year = "2017",
doi = "10.1007/978-3-319-49984-0_3",
isbn = "978-3-319-49984-0",
issn = "2194-1009",
url = "http://link.springer.com/chapter/10.1007/978-3-319-49984-0_3",
bib2html_dl_html = "http://dx.doi.org/10.1007/978-3-319-49984-0_3",
abstract = "This work connects two mathematical fields - computational complexity and interval linear algebra. It introduces the basic topics of interval linear algebra - regularity and singularity, full column rank, solving a linear system, deciding solvability of a linear system, computing inverse matrix, eigenvalues, checking positive (semi)definiteness or stability. We discuss these problems and relations between them from the view of computational complexity. Many problems in interval linear algebra are intractable, hence we emphasize subclasses of these problems that are easily solvable or decidable. The aim of this work is to provide a basic insight into this field and to provide materials for further reading and research.",
keywords = "Computational complexity; Interval linear algebra; Functional problems; Decision problems; NP-hardness; co-NP-hardness",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44