This page lists the computational complexity of three different matrix inversion algorithms:

http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra

I have not yet found which of the three algorithms MATLAB uses for inv() [if, indeed, it uses any of them], but maybe this will help you get one step closer. Also, as Walter pointed out, MATLAB may use a different algorithm depending on the matrix size (or other properties)

Regards!!!

The complexity for the computation of the Moore Penrose inverse of a matrix that can act as a partial replacement for the matrix inverse in cases where it does not exist. This matrix is frequently used to solve a system of linear equations when the system does not have a unique solution or has many solutions.

For any matrix A, the pseudoinverse B exists, is unique, and has the same dimensions as A'. If A is square and not singular, then pinv(A) is simply an expensive way to compute inv(A). However, if A is not square, or is square and singular, then inv(A) does not exist. In these cases, pinv(A) has some (but not all) of the properties of inv(A):

1. ABA=A

2. BAB=B

3. (AB)∗=AB (AB Hermitian)

4. (BA)∗=BA (BA Hermitian)

The pseudoinverse computation is based on svd(A). The calculation treats singular values less than tol as zero.

Hopefully you might have got some clue from this discussion....

The main task for evaluation singular value decomposition (SVD) is the evaluation of the eigenvalues of AA'. QR factorization is implicit in the main algorithm for SVD for evaluation of these eigenvalues. Basically QR factorization depends on using a Gram–Schmidt type of orthogonalization [1] or using Householder transformations or other rotations [2].

1.J. Rice, Experiments on Gram–Schmidt orthogonalization, Math. Comp. 20 (1966), 325–328.

2. J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, London, 1965.

Hopefully this information helps you.

The Moore-Penrose inverse has many applications. However, solving the generalized inverse requires ample computational resources, especially for large-sized matrices. When the involved problem is symmetric, the original matrix can be neatly block-diagonalized into many small-sized matrices. We have presented an efficient method based on group theory for the Moore-Penrose inverse problems, which can deal with not only well-conditioned but also rank deficient matrices. (Chen, Y. and Feng J. (2014). "Efficient method for Moore-Penrose inverse problems involving symmetric structures based on group theory." Journal of Computing in Civil Engineering, ASCE, 28 (2): 182-190.

Article Efficient Method for Moore-Penrose Inverse Problems Involvin...

Computational complexity for obtaining the M-P inverse is also discussed.

Hopefully this information helps you.

Kind regards,

Yao

create some random matrices of different sizes, A_{n1xm1}, ..., A_{n10xm10}, then: tic; Bi=pinv(Ai); toc. then fit a curve to the elapsed time.

When general matrices are considered of arbitrary properties use Householder QR or Givens QR to solve the least squares system, which are both in O(n^3)[1].

As shape and other properties are exploitable the upper bound for computing the Pseudo-inverse is O(n^3), while the lower bound is the case for triangular matrices which are solvable in O(n^2)[2]

Thus with a, b, c, d constants generally:

b * (n^2) + d