×

Successive matrix squaring algorithm for parallel computing the weighted generalized inverse \(A^+_{MN}\). (English) Zbl 1023.65031

Summary: We derive a successive matrix squaring algorithm to approximate the weighted generalized inverse, which can be expressed in the form of successive squaring of a composite matrix \(T\). Given an \(m\) by \(n\) matrix \(A\) with \(m\approx n\), we show that the weighted generalized 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)\).

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Ben-Israel, T.N.E. Greville, Generalized Inverse: Theory and Applications, Wiley, New York, 1974; A. Ben-Israel, T.N.E. Greville, Generalized Inverse: Theory and Applications, Wiley, New York, 1974 · Zbl 0305.15001
[2] A. Bjorck, Least squares methods in handbook of numerical analysis, in: P.G. Ciarlet, J.L. Lions (Eds.), Finite Difference Methods Solutions of Equations in \(R^n\), vol. 1, North-Holland, Amsterdam, 1990; A. Bjorck, Least squares methods in handbook of numerical analysis, in: P.G. Ciarlet, J.L. Lions (Eds.), Finite Difference Methods Solutions of Equations in \(R^n\), vol. 1, North-Holland, Amsterdam, 1990 · Zbl 0875.65055
[3] Chen, L.; Krishnamurthy, E. V.; Madeod, I., Generalized matrix inversion and rank computation by successive matrix powering, Parallel Computing, 20, 297-311 (1994) · Zbl 0796.65055
[4] Van Loan, C. F., Generalizing the singular value decomposition, SIAM J. Numer. Anal., 13, 76-83 (1976) · Zbl 0338.65022
[5] Wang, G., A finite algorithm for computing the weighted Moore-Penrose inverse \(A_{ MN }^+\), Appl. Math. Comput., 23, 277-289 (1987) · Zbl 0635.65039
[6] Wang, G.; Lu, S., Fast parallel algorithm for computing the generalized inverse \(A^+\) and \(A_{ MN }^+\), J. Comput. Math., 6, 348-354 (1988) · Zbl 0665.65037
[7] G. Wang, Y. Wei, PCR algorithm for parallel computing the minimum \(T\)-norm \(S\)-least squares solution of inconsistent linear equations, in: Proceedings of the Fourth National Parallel Computing Conference, Aviation Industry Press, Nanjing, China, 1993, pp. 87-92; G. Wang, Y. Wei, PCR algorithm for parallel computing the minimum \(T\)-norm \(S\)-least squares solution of inconsistent linear equations, in: Proceedings of the Fourth National Parallel Computing Conference, Aviation Industry Press, Nanjing, China, 1993, pp. 87-92
[8] Wang, G.; Wei, Y., The iterative methods for computing the generalized inverse \(A_{ MN }^+\) and \(A_{d,w} \), Numer. Math. J. Chinese Universities, 16, 366-372 (1994) · Zbl 0821.65022
[9] G. Wang, Y. Wei, Parallel \((M-N)\) SVD algorithms on the SIMD computers, in: Proceedings of the International Parallel Computing Conference, Wuhan University, J. Natural Sci. 1 (1996) 541-546; G. Wang, Y. Wei, Parallel \((M-N)\) SVD algorithms on the SIMD computers, in: Proceedings of the International Parallel Computing Conference, Wuhan University, J. Natural Sci. 1 (1996) 541-546 · Zbl 0919.68068
[10] Sun, W.; Wei, Y., Inverse order rule for weighted generalized inverse, SIAM J. Matrix Anal. Appl., 19, 772-775 (1998) · Zbl 0911.15004
[11] Y. Wei, Perturbation and computation of generalized inverse \(A^{(2)}_{T,S}\), Master thesis, Department of Mathematics, Shanghai Normal University, Shanghai, China, 1994; Y. Wei, Perturbation and computation of generalized inverse \(A^{(2)}_{T,S}\), Master thesis, Department of Mathematics, Shanghai Normal University, Shanghai, China, 1994
[12] Y. Wei, Solving singular linear systems and generalized inverses, PhD thesis, Institute of Mathematics, Fudan University, Shanghai, China, 1997; Y. Wei, Solving singular linear systems and generalized inverses, PhD thesis, Institute of Mathematics, Fudan University, Shanghai, China, 1997
[13] Wei, Y., Recurrent neural networks for computing weighted Moore-Penrose inverse, Appl. Math. Comput., 116, 279-287 (2000), this issue · Zbl 1023.65030
[14] Wei, Y., Perturbation bound of singular linear system, Appl. Math. Comput., 105, 211-220 (1999) · Zbl 1022.65042
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.