Generalized matrix inversion is not harder than matrix multiplication (Q1026453)

The paper introduces a completely block recursive algorithm for generalized Cholesky factorization of a given symmetric, positive semi-definite matrix \(A\in\mathbb R^{n\times n},\) starting from the Strassen method for rapid matrix multiplication and inversion as well as from recursive Cholesky factorization algorithm. The first section is an introduction in nature. The second section states a recursive algorithm for rapid matrix inversion, not harder than the matrix multiplication. In the third section the authors introduce a new Strassen-type full recursive algorithm for simultaneous fast computation of the Cholesky factorization matrix \(U\) satisfying \(A=U^TU,\) and its inverse \(Y.\) The algorithm is applicable to symmetric positive-definite matrices. In the fourth section the authors use the results obtained in the previous sections in order to develop algorithms to compute Moore-Penrose and various classes of \(\{2,\,3\}\) and \(\{2,\,4\}\) generalized inverses. These algorithms are not harder than the matrix multiplication. The authors present the implementation of the proposed algorithms in the symbolic programming package MATHEMATICA. Numerical examples are within the fifth section. The algorithms are tested on randomly generated test set matrices. Testing results show the efficiency of the proposed algorithms. The main conclusions are presented in the last section.