Recent developments in applied mathematics and mechanics: theory, experiment and practice. Devoted to the 80th anniversary of academician N.N.Yanenko

Akademgorodok, Novosibirsk, Russia, June 24 - 29, 2001

Abstracts

Novosibirsk participants

Solution of the three-diagonal symmetric eigenvalue problem with guaranteed accuracy in O(n^2) operations.

Matsekh A.M., Shurina E.P.

ICT SBRAS,
NSTU

In 1985 S.K. Godunov, B.I.Kostin and A.D.Mitchenko proposed a new O(n²) method that allows to determine all eigenvectors of tridiagonal symmetric matrices with guaranteed accuracy. The algorithm was designed for architectures with directed rounding, which limits it's use. We study the possibility of implementation of the Godunov's algorithm on architectures that do not have directed rounding mechanism. Instead we consider architectures with software-implemented extended precision. In the absence of directed rounding we had to modify a number of machine-dependent parameters in the algorithm. We also had to implement block version of the method for matrices that are not unreduced, e.g. have co-diagonal elements close to machine zero, thus avoiding the need for introducing disturbances in the small elements to avoid overflow in the eigenvector computations. We finally compare the method with the Inverse Iteration with modified Gram-Schmidt orthogonalization method, that requires O(n³) floating point operations in the worst case, and is used in such packages as LAPACK and EISPACK for the solution of tridiagonal eigen-problems.

Full Text in Russian: PDF (424 kb)
Note. Abstracts are published in author's edition

Comments

[Home]
[Conference]