×

Modified SMS method for computing outer inverses of Toeplitz matrices. (English) Zbl 1262.65052

This paper introduces an algorithm based on the successive matrix squaring (SMS) method. The algorithm uses the strategy of \(\epsilon\)-displacement rank in order to find various outer inverses \(A^{(2)}\), \(A^{(2)}\in\{X|XAX=X\}\), with prescribed ranges and null spaces of a given square Toeplitz matrix \(A\). Such outer inverse is of special interest in matrix theory because the most common generalized inverses (the Moore-Penrose pseudoinverse, the weighted Moore-Penrose pseudoinverse, the Drazin inverse, the group inverse, the Bott-Duffin inverse, and the generalized Bott-Duffin inverse) are outer inverses with prescribed range and null space. Using the idea of displacement theory which decreases the memory space requirements as well as the computational cost, the authors’ method tends to be very effective for Toeplitz matrices. The paper also gives several illustrative examples.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
15B05 Toeplitz, Cauchy, and related matrices
65F05 Direct numerical methods for linear systems and matrix inversion
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben-Israel, A.; Greville, T. N.E., Generalized Inverses: Theory and Applications (2003), Springer · Zbl 1026.15004
[2] Bini, D.; Meini, B., Approximate Displacement Rank and Applications, (Olshevsky, V., Structured Matrices in Mathematics, Computer Science and Engineering II, Contemporary Mathematics, 281 (2001), American Mathematical Society: American Mathematical Society Rhode Island), 215-232 · Zbl 1004.65054
[3] Bini, D.; Codevico, G.; Van Barel, M., Solving Toeplitz least squares problems by means of Newton’s iteration, Numer. Algorithms, 33, 93-103 (2003) · Zbl 1031.65059
[4] Cai, J. F.; Ng, M. K.; Wei, Y., Modified Newton’s algorithm for computing the group inverses of singular Toeplitz matrices, J. Comput. Math., 24, 647-656 (2006) · Zbl 1113.65035
[5] Chan, R.; Ng, M., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 427-482 (1996) · Zbl 0863.65013
[6] Chen, L.; Krishnamurthy, E. V.; Macleod, I., Generalized matrix inversion and rank computation by successive matrix powering, Parallel Comput., 20, 297-311 (1994) · Zbl 0796.65055
[7] G. Codevico, V.Y. Pan, M. Van Barel, X. Wang, A. Zheng, The least squares compression policy for Newton-like iteration of structured matrices (P. Mitic, J. Carne, Eds.), IMS2004 Proceedings, 2004, pp. 1-22.; G. Codevico, V.Y. Pan, M. Van Barel, X. Wang, A. Zheng, The least squares compression policy for Newton-like iteration of structured matrices (P. Mitic, J. Carne, Eds.), IMS2004 Proceedings, 2004, pp. 1-22.
[8] Codevico, G.; Pan, V. Y.; Van Barel, M., Newton-like iteration based on a cubic polynomial for structured matrices, Numer. Algorithms, 36, 4, 365-380 (2004) · Zbl 1068.65050
[9] Diao, H.; Wei, Y.; Qiao, S., Displacement rank of the Drazin inverse, J. Comput. Appl. Math., 167, 147-161 (2004) · Zbl 1055.15001
[10] Grenander, U.; Rosenblatt, M., Statistical Analysis of Stationary Time Series (1966), Wiley and Sons: Wiley and Sons NY
[11] Getson, A. J.; Hsuan, F. C., {2}-Inverses and their Statistical Applications, Lecture Notes in Statistics, 47 (1988), Springer: Springer Berlin · Zbl 0671.62003
[12] Hackbush, W.; Khoromskij, B. N.; Tyrtyshnikov, E. E., Approximate iterations for structured matrices, Numer. Math., 109, 365-383 (2008) · Zbl 1144.65029
[13] Heinig, G.; Rost, K., Algebraic Method for Toeplitz-like Matrices and Operators (1984), Akademie-Verlag: Akademie-Verlag Berlin and Birkhauser · Zbl 0549.15013
[14] Heinig, G.; Hellinger, F., Displacement structure of pseudoinverses, Linear Algebra Appl., 197/198, 623-649 (1994) · Zbl 0796.15007
[15] Horn, R. A.; Johnson, C. R., Matrix Analysis (1986), Cambridge University Press: Cambridge University Press Cambridge, New York, New Rochelle, Melbourne, Sydney
[16] Husen, F.; Langenberg, P.; Getson, A., The {2}-inverse with applications to satistics, Linear Algebra Appl., 70, 241-248 (1985)
[17] Kailath, T.; Kung, S. Y.; Morf, M., Displacement rank of matrices and linear equations, J. Math. Anal. Appl., 68, 395-407 (1979) · Zbl 0433.15001
[18] T. Kailath, A.H. Sayed, Fast algorithms for generalized displacement structures, in recent advances in mathematical theory of systems, control, networks and signal processing II, Proceedings of the MTNS-91 (H.Kimura, S.Kodama, Eds.) Mita Press, Japan, 1992, pp. 27-32.; T. Kailath, A.H. Sayed, Fast algorithms for generalized displacement structures, in recent advances in mathematical theory of systems, control, networks and signal processing II, Proceedings of the MTNS-91 (H.Kimura, S.Kodama, Eds.) Mita Press, Japan, 1992, pp. 27-32.
[19] Kailath, T.; Sayed, A. H., Displacement structure: theory and applications, SIAM Rev., 37, 297-386 (1995) · Zbl 0839.65028
[20] Kailath, T.; Kung, S. Y.; Morf, M., Displacement rank of a matrix, Bull. Amer. Math. Soc., 1, 769-773 (1979) · Zbl 0417.65015
[21] Li, S., Displacement structure of the generalized inverse \(A_{T, S}^{(2)}\), Appl. Math. Comput., 156, 33-40 (2004) · Zbl 1057.15005
[22] Liu, X.; Hu, C.; Yu, Y., Further results on iterative methods for computing generalized inverses, J. Comput. Appl. Math., 234, 684-694 (2010) · Zbl 1190.65088
[23] Nashed, M. Z., Generalized Inverse and Applications (1976), Academic Press: Academic Press New York · Zbl 0327.45022
[24] Nashed, M. Z.; Chen, X., Convergence of Newton-like methods for singular operator equations using outer inverses, Numer. Math., 66, 235-257 (1993) · Zbl 0797.65047
[25] Pan, V. Y., Structured Matrices and Polynomials. Unifed Superfast Algorithms (2001), Birkhauser Springer · Zbl 0996.65028
[26] Pan, V. Y.; Schreiber, R., An improved Newton iteration for generalized inverse of a matrix with applications, SIAM J. Sci. Stat. Comput., 12, 1109-1131 (1991) · Zbl 0733.65023
[27] Pan, V. Y.; Rami, Y.; Wang, X., Structured matrices and Newton’s iteration: unified approach, Linear Algebra Appl., 343-344, 233-265 (2002) · Zbl 0998.65039
[28] Pan, V. Y.; Van Barel, M.; Wang, X. M.; Codevico, G., Iterative inversion of structured matrices, Theor. Comput. Sci., 315, 581-592 (2004) · Zbl 1059.65032
[29] Schulz, G., Iterative Berechnung der reziproken Matrix, ZAMM Z. Angew. Math. Mech., 13, 57-59 (1933) · JFM 59.0535.04
[30] Stanimirović, P.; Cvetkovic-Ilić, D., Successive matrix squaring algorithm for computing outer inverses, Appl. Math. Comput., 203, 19-29 (2008) · Zbl 1158.65028
[31] Trench, W. R., An algorithm for the inversion of finite Toeplitz matrices, SIAM J. Appl. Math., 12, 515-522 (1964) · Zbl 0131.36002
[32] Wei, Y.; Cai, J.; Ng, M. K., Computing Moore-Penrose inverses of Toeplitz matrices by Newton’s iteration, Math. Comput. Model., 40, 181-191 (2004) · Zbl 1069.65045
[33] Wei, Y., Successive matrix squaring algorithm for computing Drazin inverse, Appl. Math. Comput., 108, 67-75 (2000) · Zbl 1022.65043
[34] Wei, Y.; Wu, H.; Wei, J., Successive matrix squaring algorithm for parallel computing the weighted generalized inverse \(A_{MN}^\dagger \), Appl. Math. Comput., 116, 289-296 (2000) · Zbl 1023.65031
[35] Wei, Y.; Ng, M. K., Displacement structure of group inverses, Numer. Linear Algebra Appl., 12, 103-110 (2005) · Zbl 1164.15305
[36] Yu, Y.; Wei, Y., Determinantal representation of the generalized inverse \(A_{T, S}^{(2)}\) over integral domains and its applications, Linear Multilinear Algebra, 57, 547-559 (2009) · Zbl 1182.15007
[37] Yu, Y.; Wei, Y., The representation and computational procedures for the generalized inverse \(A_{T, S}^{(2)}\) of an operator A in Hilbert spaces, Numer. Funct. Anal. Optim., 30, 168-182 (2009) · Zbl 1165.47004
[38] Zheng, B.; Bapat, R. B., Generalized inverse \(A_{T, S}^{(2)}\) and a rank equation, Appl. Math. Comput., 155, 407-415 (2004) · Zbl 1057.15008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.