How to establish that an iterative method can be applied to large matrices whose size may reach 10^3?

Question

I have an iterative method for computing the Moore-Penrose generalized inverse of matrices, that is

$$X_{k+1} = ((I-\beta X_{k}A)^t) + X_{k}$$

with initial approximation: $$X_{0} = \beta AA^t$$

where:

• $A$ is a given $m \times n$ matrix
• $\beta \in [0,1]$
• $X_{k}$ is the $k$th iterate generated by the algorithm, approximating the Moore-Penrose generalized inverse of matrix $A$.

---

1. Can this method be applied for higher-order matrices?
2. What is the advantage of this method over other algorithms like singular value decomposition and QR factorization?
3. How would I determine if the iterative algorithm runs faster than the other methods mentioned above?

Answer 1

From the phrasing of question 2, I'm assuming that this is a homework question, so I'm going to give vague answers and not feel too bad about it:

1) A 1000 X 1000 matrix isn't that big, so as long as your computer has enough memory (and any computer made in the last ten years probably would), yes you can run this algorithm on such matrices.

2 and 3) These are related questions. Your best bet would be to start with an order of magnitude analysis for each of your algorithms. Basically, using this kind of analysis you can roughly figure out how many computational steps are required for each algorithm as a function of the size of matrix $A$. You can probably assume that if an algorithm takes fewer steps to produce an answer then it will run faster (although in reality this depends on the computational cost of each step. Cost is very implementation dependent, however, so you may not want to get into it). Other possible advantages one algorithm can have over another include requiring less memory or being easier to parallelize.

Also, in terms of running speed alone, you can make a set of test cases and then time how long it takes for each algorithm to finish the set.

Answer 2

Program it in Matlab, say, and test it against SVD for increrasing dimensions and matrices generated by $A=BDC$ with random square B and nonrandom diagonal $D>0$ with increasing ratio of $\max_i D_{ii}/\min_i D_{ii}$ Most likely, your method is much slower for the same accuracy.