Fast Computation for Square Matrix Factorization

In this work, we discuss the method of the QR-factorization which is based of the transformations which is called the discrete signal induced heap transformations (DsiHT). These transformations are generated by given signals and can be composed by elementary rotations. The order of processing data, or the path of the transformation, is an important characteristic of it, and the correct choice of such paths can lead to a significant reduction in the operation when calculating the factorization for large matrices. Such paths are called fast paths of the DsiHTs, and they define sparse matrices with more zero coefficients than when calculating QR-factorization in the traditional path, that is, when processing data in the natural order x0,x1,x3,… . For example, in the first stage of the factorization of a 512×512 matrix, a matrix is used with 257,024 zero coefficients of total 262,144 coefficients, when using the fast paths. For comparison, the calculations in the natural order requires a 512×512 matrix with only 130,305 zero coefficients it this stage. The effectiveness of the proposed method is illustrated in comparison with the QR-factorization based on the sequence of Householder reflections (or transformations). Examples with the 4×4, 5×5, and 8×8 matrices are described in detail. The example of the QR-factorization of 256×256 complex matrix is also described and compared with the method of Housholder reflections which is used in programming language MATLAB.