×

Successive matrix squaring algorithm for computing the Drazin inverse. (English) Zbl 1022.65043

Summary: This paper derives a successive matrix squaring (SMS) algorithm to approximate the Drazin inverse which can be expressed in the form of successive squaring of a composite matrix \(T\). Given an \(n\) by \(n\) matrix \(A\), the study shows that the Drazin inverse of \(A\) can be computed in parallel time ranging from \(O(\log n)\) to \(O(\log^2n)\) provided that there are enough processors to support matrix multiplication in time \(O(\log n)\).
The SMS algorithm is generalized to higher-order schemes, where the composite matrix is repeatedly raised to an integer power \(l\geq 2\). This form of expression leads to a simplified notation compared to that of earlier methods, we argue that there is no obvious advantage in choosing \(l\) other than 2. Our derived error bound for the approximation of \(A^D\) is new.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F30 Other matrix algorithms (MSC2010)
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S.L. Campbell, C.D. Meyer Jr., Generalized Inverse of Linear Transformations, Pitman, London, 1979; Dover, New York, 1991; S.L. Campbell, C.D. Meyer Jr., Generalized Inverse of Linear Transformations, Pitman, London, 1979; Dover, New York, 1991
[2] Hartwig, R. E.; Hall, F., Applications of the Drazin inverse to Cesaro-Neumann iterations, in: S.L. Campbell (Ed.), Recent Applications of Generalized Inverses, Pitman, London, Program, No., 66, 145-195 (1982)
[3] Hartwig, R. E.; Levine, J., Applications of the Drazin inverse to the hill cryptographic system, Part III, Cryptologia, 5, 67-77 (1981) · Zbl 0491.94015
[4] Eiermann, M.; Marek, I.; Niethammer, W., On the solution of singular linear systems of algebraic equations by semiiterative methods, Numer. Math., 53, 265-283 (1988) · Zbl 0655.65049
[5] Freund, R. W.; Hochbruck, M., On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling, Numerical Linear Algebra Appl., 1, 403-420 (1994) · Zbl 0840.65021
[6] Hanke, M.; Neumann, M., Preconditioning and splittings for rectangular systems, Numer. Math., 57, 85-95 (1990) · Zbl 0704.65018
[7] Higham, N. J.; Knight, P. A., Finite precision behavior of stationary iteration for solving singular systems, Linear Algebra Appl., 192, 165-186 (1993) · Zbl 0787.65021
[8] Meyer, C. D.; Plemmons, R. J., Convergent powers of a matrix with applications to iterative methods for singular linear systems, SIAM J. Numer. Anal., 14, 699-705 (1977) · Zbl 0366.65017
[9] Miller, V. A.; Neumann, M., Successive overrelaxation methods for solving the rank deficient linear least squares problem, Linear Algebra Appl., 88/89, 533-557 (1987) · Zbl 0624.65033
[10] Wang, G., A Cramer rule for finding the solution of a class of singular equations, Linear Algebra Appl., 116, 27-34 (1989) · Zbl 0671.15006
[11] Wei, Y., A characterization and representation of the Drazin inverse, SIAM J. Matrix Anal. Appl., 17, 4, 744-747 (1996) · Zbl 0872.15006
[12] Wei, Y.; Wang, G., The perturbation theory for the Drazin inverse and its applications, Linear Algebra Appl., 258, 179-186 (1997) · Zbl 0882.15003
[13] Wei, Y., On the perturbation of the group inverse and oblique projection, Appl. Math. Comput., 98, 29-42 (1998) · Zbl 0927.15004
[14] Simeon, B.; Führer, C.; Rentrop, P., The Drazin inverse in multibody system dynamics, Numer. Math., 64, 521-539 (1993) · Zbl 0797.65054
[15] Chen, X.; Hartwig, R. E., The hyperpower iteration revisited, Linear Algebra Appl., 233, 207-229 (1996) · Zbl 0848.65021
[16] Greville, T. N.E., The Souriau-Frame algorithm and the Drazin pseudoinverse, Linear Algebra Appl., 6, 205-208 (1973) · Zbl 0247.15004
[17] Hartwig, R. E., More on the Souriau-Frame algorithm and the Drazin inverse, SIAM J. Appl. Math., 31, 42-46 (1976) · Zbl 0335.15008
[18] Hartwig, R. E., A method for calculating \(A^D\), Math. Japonica, 26, 37-43 (1981) · Zbl 0458.15002
[19] Kuang, J., Several approximate methods for Drazin inverse of bounded linear operators in Banach spaces, Journal of Shanghai Teachers University, 3, 1-8 (1982) · Zbl 0602.65039
[20] G. Wang, Fast parallel algorithm for computing Drazin inverse \(A^D\), Proceedings of the National First Parallel Algorithm Conference, China, 1989, pp. 341-350; G. Wang, Fast parallel algorithm for computing Drazin inverse \(A^D\), Proceedings of the National First Parallel Algorithm Conference, China, 1989, pp. 341-350
[21] Decell, H. P., An Application of the Cayley-Hamilton theorem to generalized inverse, SIAM Rev., 7, 526-528 (1965) · Zbl 0178.35504
[22] Csanky, L., Fast parallel matrix inversion algorithm, SIAM J. Comput., 5, 618-623 (1976) · Zbl 0353.68063
[23] Codenotti, B., Parallel solution of linear systems by repeated squaring, Applied Math. letters, 3, 19-20 (1990) · Zbl 0705.65024
[24] B. Codenotti, M. Leoncini, G. Resta, Repeated matrix squaring for the parallel solution of linear systems, Lecture Notes in Computer Science 605, Springer, New York, 1992, pp. 725-732; B. Codenotti, M. Leoncini, G. Resta, Repeated matrix squaring for the parallel solution of linear systems, Lecture Notes in Computer Science 605, Springer, New York, 1992, pp. 725-732
[25] Chen, L.; Krishnamurthy, E. V.; Macleod, I., Generalized matrix inversion and rank computation by successive matrix powering, Parallel Computing, 20, 297-311 (1994) · Zbl 0796.65055
[26] A. Ben-Israel, T.N.E. Greville, Generalized Inverses: Theory and Applications, Wiley, New York, 1974; A. Ben-Israel, T.N.E. Greville, Generalized Inverses: Theory and Applications, Wiley, New York, 1974 · Zbl 0305.15001
[27] A.S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, New York, 1964; A.S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, New York, 1964 · Zbl 0161.12101
[28] Pan, V., Complexity of parallel matrix computations, Theor. Comput. Sci., 54, 65-85 (1987) · Zbl 0641.68058
[29] Pan, V.; Reif, J., Fast and efficient parallel solution of dense linear systems, Comput. and Math. with Appl., 17, 1481-1491 (1989) · Zbl 0684.65024
[30] D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progression. Proceedings of the 19th Annual ACM Sympposium on Theory of Computing, Springer, New York, 1987, pp. 1-6; D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progression. Proceedings of the 19th Annual ACM Sympposium on Theory of Computing, Springer, New York, 1987, pp. 1-6
[31] Wei, Y., Index splitting for the Drazin inverse and singular system, Appl. Math. Comput., 95, 115-124 (1998) · Zbl 0942.15003
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.