%0 Journal Article %T New Method of Givens Rotations for Triangularization of Square Matrices %A Artyom M. Grigoryan %J Advances in Linear Algebra & Matrix Theory %P 65-78 %@ 2165-3348 %D 2014 %I Scientific Research Publishing %R 10.4236/alamt.2014.42004 %X
This paper describes a new method of QR-decomposition of square nonsingular matrices (real or complex) by the Givens rotations through the unitary discrete heap transforms. This transforms can be defined by a different path, or the order of processing components of input data, which leads to different realizations of the QR-decomposition. The heap transforms are fast, because of a simple form of decomposition of their matrices. The direct calculation of the N-point discrete heap transform requires no more than 5(N-1) multiplications, 2(N-1) additions, plus 3(N-1) trigonometric operations. The QR-decomposition of the square matrix N ¡Á N uses about 4/3N3 multiplications and N(N-1)/2 square roots. This number varies depending on the path of the heap transform, and it is shown that ¡°the optimal path¡± allows for significant reduction of number of operations in QR-decomposition. The heap transform and its matrix can be described analytically, and therefore, this transform can also be applied to the QR-decomposition of complex matrices.
%K QR-Factorization %K Givens Rotations %K Householder Reflections %K Heap Transform %U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=45910