Generalized matrix inversion is not harder than matrix multiplication
type: Item
instance of: scholarly article
title: Generalized matrix inversion is not harder than matrix multiplication
zbMATH Open document ID: 1170.65020
author: Marko D. Petković
author: Predrag S. Stanimirović
published in: Journal of Computational and Applied Mathematics
publication date: 2009-06-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F20
zbMATH DE Number: 5570574
zbMATH Keywords: Cholesky factorization
zbMATH Keywords: complexity analysis
zbMATH Keywords: generalized inverse
zbMATH Keywords: Moore-Penrose inverse
zbMATH Keywords: Strassen method
zbMATH Keywords: recursive algorithm
zbMATH Keywords: rapid matrix multiplication
zbMATH Keywords: rapid matrix inversion
zbMATH Keywords: numerical examples
reviewed by: Romulus Militaru
describes a project that uses: Mathematica
MaRDI profile type: Publication
full work available at URL: j.cam.2008.11.012
OpenAlex ID: W2122385067
cites work: Generalized inverses. Theory and applications.
cites work: Introduction to algorithms
cites work: Gaussian elimination is not optimal
cites work: Matrix multiplication via arithmetic progressions
cites work: Q5769165
cites work: Computing generalized inverses using LU factorization of matrix product
cites work: Exploiting fast matrix multiplication within the level 3 BLAS
cites work: Locality of Reference in LU Decomposition with Partial Pivoting
cites work: Generalized Inverse Formulas Using the Schur Complement
cites work: Q4358153
DOI: 10.1016/J.CAM.2008.11.012
description: scientific article; zbMATH DE number 5570574