High-Performance Algorithms for Tridiagonal Symmetric Matrices Diagonalization Based on Elementary Planar Rotations

  • В.И. Иордан Altai State University Email: jordan@phys.asu.ru
Keywords: tridiagonal symmetric matrix, planar rotations, high-performance, algorithms for matrices diagonalization

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

PDF views
332
Jan 2017Jul 2017Jan 2018Jul 2018Jan 2019Jul 2019Jan 2020Jul 2020Jan 2021Jul 2021Jan 2022Jul 2022Jan 2023Jul 2023Jan 2024Jul 2024Jan 2025Jul 2025Jan 202672
|

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.

How to Cite
Иордан В. High-Performance Algorithms for Tridiagonal Symmetric Matrices Diagonalization Based on Elementary Planar Rotations // Izvestiya of Altai State University, 1, № 1(93) DOI: 10.14258/izvasu(2017)1-15. URL: https://izvestiya.asu.ru/article/view/%282017%291-15.