Fast Computation for Square Matrix Factorization

In this work, we discuss a method for the QR-factorization of N × N matrices where N ≥ 3 which is based on transformations which are called discrete signal-induced heap transformations (DsiHTs). These transformations are generated by given signals and can be composed by elementary rotations. The data processing order, or the path of the transformations, 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 N-point 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, x2, …. For example, in the first stage of the factorization of a 512 × 512 matrix, a matrix is used with 257,024 zero coefficients out of a total of 262,144 coefficients when using the fast paths. For comparison, the calculations in the natural order require a 512 × 512 matrix with only 130,305 zero coefficients at this stage. The Householder reflection matrix has no zero coefficients. The number of multiplication operations for the QR-factorization by the fast DsiHTs is more than 40 times smaller than when using the Householder reflections and 20 times smaller when using DsiHTs with the natural paths. Examples with the 4 × 4, 5 × 5, and 8 × 8 matrices are described in detail. The concept of complex DsiHT with fast paths is also described and applied in the QR-factorization of complex square matrices. An example of the QR-factorization of a 256 × 256 complex matrix is also described and compared with the method of Householder reflections which is used in programming language MATLAB R2024b.