Filomat 2023 Volume 37, Issue 30, Pages: 10395-10413
https://doi.org/10.2298/FIL2330395M
Full text (
745 KB)
Algorithms for computing the optimal Geršgorin-type localizations
Milićević S. (Department for Applied fundamental disciplines, Faculty of Technical Sciences, University of Novi Sad, Novi Sad, Serbia), srdjan88@uns.ac.rs
Kostić V.R. (Istituto Italiano di Tecnologia, Genova, Italy + Department of Mathematics and Informatics, Faculty of Science, University of Novi Sad, Novi Sad, Serbia), vkostic@dmi.uns.ac.rs; vladimir.kostic@iit.it
In this paper we provide novel algorithms for computing the minimal
Geršgorin set for the localizations of eigenvalues. Two strategies for
curve tracing are considered: predictor-corrector and triangular grid
approximation. We combine these two strategies with two characterizations
(explicit and implicit) of the Minimal Geršgorin set to obtain four new
numerical algorithms. We show that these algorithms significantly decrease
computational complexity, especially for matrices of large size, and compare
them on matrices that arise in practically important eigenvalue problems.
Keywords: eigenvalue localization, minimal Geršgorin set, predictor-corrector method, triangular grid
Show references
E. L. Allgower and K. Georg, Continuation and path following, Acta numerica, 1-64, 1993.
E. L. Allgower and K. Georg, Numerical path following, Colorado State University, 1994.
A. Berman and R. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 2014.
B. Boisvert, R. Pozzo, K. Remington, B. Miller and R. Lipman, Matrix Market repository, http://math.nist.gov/MatrixMarket/.
M. A. Freitag and A. Spence, A Newton-based method for the calculation of the distance to instability, Linear Algebra Appl., 435(12):3189-3205, 2011.
V. Kostić, On general principles of eigenvalue localizations via diagonal dominance, Advances in Computational Mathematics, 41:55-75, 2015.
V. Kostić, A. Miedlar and Lj. Cvetković, An algorithm for computing minimal Geršgorin sets. Numerical linear algebra with applications, 00:1-19, 2015.
J. R. Magnus, On differentiating eigenvalues and eigenvectors, Econometric Theory, 1 : 179-191, 1985.
D. Mehzer and B. Philippe, PAT-a Reliable Path Following Algorithm, Numerical Algorithms, 2002.
S. Milićević, V. Kostić, Lj. Cvetković and A. Miedlar, An implicit algorithm for computing the minimal Geršgorin set, FILOMAT, 13 : 4229-4238, 2019.
R. S. Varga, Geršgorin na His Circles. Springer-Verlag, New York, 2004.
R. S. Varga, Minimal Gershgorin sets, Pac. J. Math., 15:719-729, 1965.
R. S. Varga, Lj. Cvetković and V. Kostić, Approximation of the minimal Geršgorin set of a square complex matrix, ETNA (Electronic Transactions on Numerical Analysis), 40:308-405, 2008.