High-Performance Algorithms for Tridiagonal Symmetric Matrices Diagonalization Based on Elementary Planar Rotations
Abstract
This paper discusses two algorithms for diagonal-ization of real symmetric tridiagonal matrices. The proposed algorithms preserve the invariant (unchanged) tridiagonal form and provide high performance comparable with the most high-performance QR-algorithms and similar techniques. Contrary to the transformations of reflections, the presented algorithms of matrices di-agonalization using elementary planar rotations have absolute stability of calculations (Wilkinson stability). In this paper, the absolutely stable convergence of the proposed algorithms is proved. Convergence criteria are defined inherently by “integral” properties in contrast with “differential” properties of neighborhood convergence of QR-algorithms (in practice, QR-algorithms are prone to instability and loss of accuracy for eigenvalues computation under certain conditions). A priori estimates of maximum values of diagonalization error for proposed algorithms are provided. Also, the paper discusses the results of numerical experiments for a wide class of symmetric matrices conducnted to elaborate matrices di-agonalization time dependencies for QR-techniques and proposed algorithms.Downloads
Metrics
References
Уилкинсон Дж.Х., Райнш К. Справочник алгоритмов на языке Алгол. Линейная алгебра. - М., 1976.
Парлетт Б. Симметрическая проблема собственных значений. Численные методы / пер. с англ. Х.Д. Икрамова и Ю.А. Кузнецова. - М., 1983.
Watkins D.S. The Matrix Eigenvalue Problem: GR and Krylov Methods // D.S. Watkins. - SIAM. - 2007.
Prodi G. Eigenvalues of non-linear problems // G. Prodi (ed.). - Berlin Heidelberg, 2010.
Новиков М.А. Одновременная диагонализация трех вещественных симметричных матриц // Известия ВУЗов. Математика. - 2014. - № 12.
Кочура А.Е., Подкользина Л.В., Ивакин Я.А., Нидзиев И.И. Сингулярные матричные пучки в обобщенной симметричной проблеме собственных значений // Труды СПИИРАН. - 2013. - Вып. 3(26).
Кузнецов Ю.И. Проблема собственных значений симметричной теплициевой матрицы // Сибирский журнал вычислительной математики. - 2009. - Т. 12, № 4.
Иордан В.И. Эффективные методы определения энергетического спектра матриц большой размерности в задачах экспериментальной физики : дисс.. канд. физ.-мат. наук: 01.04.01. - Барнаул, 2003.
Izvestiya of Altai State University is a golden publisher, as we allow self-archiving, but most importantly we are fully transparent about your rights.
Authors may present and discuss their findings ahead of publication: at biological or scientific conferences, on preprint servers, in public databases, and in blogs, wikis, tweets, and other informal communication channels.
Izvestiya of Altai State University allows authors to deposit manuscripts (currently under review or those for intended submission to Izvestiya of Altai State University) in non-commercial, pre-print servers such as ArXiv.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY 4.0) that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
