Effective Methods of QR-Decompositions of Square Complex Matrices by Fast Discrete Signal-Induced Heap Transforms
- 1 Department of Electrical and Computer Engineering, The University of Texas at San Antonio, San Antonio, USA
Abstract
The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 2006) is used. This transform is fast, has a unique algorithm for any length of the input vector/signal and can be used with different complex basic 2 × 2 transforms. The DsiHT is zeroing all components of the input signal while moving or heaping the energy of the signal to one component, for instance the first one. We describe three different types of QR-decompositions that use the basic transforms with the T , G , and M -type complex matrices we introduce, as well as without matrices but using analytical formulas. We also present the mixed QR-decomposition, when different type DsiHTs are used in different stages of the algorithm. The number of such decompositions is greater than 3 ( N -1) , for an N × N complex matrix. Examples of the QR-decomposition are described in detail for the 4 × 4 and 6 × 6 complex matrices and compared with the known method of Householder transforms. The precision of the QR-decompositions of N × N matrices, when N are 6, 13, 17, 19, 21, 40, 64, 100, 128, 201, 256, and 400 is also compared. The MATLAB-based scripts of the codes for QR-decompositions by the described DsiHTs are given.
- Morrison, D.D. (1960) Remarks on the Unitary Triangularization of a Nonsymmetric Matrix. Journal ACM, 7, 185-186. https://doi.org/10.1145/321021.321030
- Businger, P. and Golub, G.H. (2017) Linear Least Squares Solutions by Householder Transformations. In: Bauer, F.L., Ed., Linear Algebra, Handbook for Automatic Computation, Vol. 2, Springer, Berlin.
- Horn, R.A. and Charles, R.J. (1985) Matrix Analysis. Cambridge University Press, Cambridge.
- Golub, G.H. and Van Loan, C.F. (1996) Matrix Computations. 3rd Edition, Johns Hopkins, Baltimore.
- Anderson, E., Bai, Z., Bischof, C.H., et al. (1999) LAPACK Users’ Guide. 3rd Edition, SIAM, Philadelphia. https://doi.org/10.1137/1.9780898719604
- Moon, T.K. and Stirling, W.C. (2000) Mathematical Methods and Algorithms for Signal Processing. Prentice Hall, Hoboken.
- Alonso, P., Peña, J.M. and Serrano, M.L. (2017) QR Decomposition of Almost Strictly Sign Regular Matrices. Journal of Computational and Applied Mathematics, 318, 646-657. https://doi.org/10.1016/j.cam.2015.10.030
- Björck, A. (1967) Solving Linear Least Squares Problems by Gram-Schmidt Orthogonalization. BIT Numerical Mathematics, 7, 1-21. https://doi.org/10.1007/BF01934122
- Rutishause, H. (2017) Simultaneous Iteration Method for Symmetric Matrices. In: In: Bauer, F.L., Ed., Linear Algebra, Handbook for Automatic Computation, Vol. 186, Springer, Berlin.
- Householder, A.S. (1958) Unitary Triangulation of a Nonsymmetric Matrix. Journal ACM, 5, 339-342. https://doi.org/10.1145/320941.320947
- Bindel, D., Demmel, J., Kahan, W. and Marques, O. (2001) On Computing Givens Rotations Reliably and Efficiently. LAPACK Working Note 148, University of Tennessee, Knoxville, UT-CS-00-449.
- Demmel, J., Grigori, L., Hoemmen, M. and Langou, J. (2012) Communication-Optimal Parallel and Sequential QR and LU Factorizations. SIAM Journal on Scientific Computing, 34, 206-239. https://doi.org/10.1137/080731992
- Grigoryan, A.M. and Grigoryan, M.M. (2006) Nonlinear Approach of Construction of Fast Unitary Transforms. Proceedings of the 40th Annual Conference on Information Sciences and Systems (CISS 2006), Princeton University, Princeton, 1073-1078. https://doi.org/10.1109/CISS.2006.286625
- Grigoryan, A.M. and Grigoryan, M.M. (2007) Discrete Unitary Transforms Generated by Moving Waves. Proceedings of SPIE, 6701, Article ID: 670125. https://doi.org/10.1117/12.728383