Jaroslav Horáček, Milan Hladík, and Josef Matějka. Determinants of interval matrices. Electron. J. Linear Algebra, 33:99–112, 2018.
[PDF] [gzipped postscript] [postscript] [HTML]
In this paper we shed more light on determinants of real interval matrices. Computing the exact bounds on a determinant of an interval matrix is an NP-hard problem. Therefore, attention is first paid to approximations. NP-hardness of both relative and absolute approximation is proved. Next, methods computing verified enclosures of interval determinants and their possible combination with preconditioning are discussed. A new method based on Cramer's rule was designed. It returns similar results to the state-of-the-art method, however, it is less consuming regarding computational time. Other methods transferable from real matrices (e.g., the Gerschgorin circles, Hadamard's inequality) are discussed. New results about classes of interval matrices with polynomially computable tasks related to determinant are proved (symmetric positive definite matrices, class of matrices with identity midpoint matrix, tridiagonal H-matrices). The mentioned methods were compared for random general and symmetric matrices.
@article{HorHla2018a,
author = "Jaroslav Hor\'{a}{\v{c}}ek and Milan Hlad\'{\i}k and Josef Mat{\v{e}}jka",
title = "Determinants of interval matrices",
journal = "Electron. J. Linear Algebra",
fjournal = "Electronic Journal of Linear Algebra",
volume = "33",
pages = "99-112",
year = "2018",
doi = "10.13001/1081-3810.3719",
issn = "1081-3810",
url = "https://doi.org/10.13001/1081-3810.3719",
bib2html_dl_html = "https://journals.uwyo.edu/index.php/ela/article/view/1831",
abstract = "In this paper we shed more light on determinants of real interval matrices. Computing the exact bounds on a determinant of an interval matrix is an NP-hard problem. Therefore, attention is first paid to approximations. NP-hardness of both relative and absolute approximation is proved. Next, methods computing verified enclosures of interval determinants and their possible combination with preconditioning are discussed. A new method based on Cramer's rule was designed. It returns similar results to the state-of-the-art method, however, it is less consuming regarding computational time. Other methods transferable from real matrices (e.g., the Gerschgorin circles, Hadamard's inequality) are discussed. New results about classes of interval matrices with polynomially computable tasks related to determinant are proved (symmetric positive definite matrices, class of matrices with identity midpoint matrix, tridiagonal H-matrices). The mentioned methods were compared for random general and symmetric matrices.",
keywords = "Interval matrices; Interval determinant; Enclosures of a determinant; Complexity",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44