The Modified Givens Method for Accelerated Reduction of a Real Matrix to the Hessenberg Form
The paper considers the problem of speeding up the widely known Givens method based on the elementary plane rotations. The Givens method reduces an initial asymmetric matrix to the Hessenberg (almost triangular) form, and an initial symmetric matrix — to the tridiagonal symmetric form. The proposed modification of the Givens method utilizes features of recurrent recalculation of certain elements of a matrix, and, thereby, the standard Givens algorithm speeds up to 1.4 times approximately. The standard and modified Givens algorithms provide guaranteed stability and accuracy of an initial matrix reduction to the Hessenberg form with cumulative round-off errors of the same order. Numerical experiments demonstrate the modified Givens method performance to be almost equal to the high-speed Householder method. However, the Householder method does not provide guaranteed stability and accuracy in all cases of large matrices reduction to the Hessenberg form.
Key words: Givens method, symmetric matrix, orthogonal transformations, plane rotations, performance, modified algorithm, Hessenberg form
Full text at PDF
, 773Kb. Language: Russian.