0

I'm completely lost on this question, any help would be appreciated.

Suppose the application of the Gaussian Elimination algorithm on a 50 by 50 matrix is timed at 500 μ seconds. How much time do you estimate would be required to apply the algorithm to a 2000 by 2000 matrix? (Ignore any issues with respect to the requirement for additional memory.)

Memming
  • 2,028
  • 15
  • 25
oremor94
  • 1

2 Answers2

2

This isn't as much a mathematical question as much it is algorithmic.

Algorithms are usually associated with a rough running time estimate called Order of Growth classification.

You can read more about it on Wikipedia.

It turns out that Gaussian Elimination is $\mathcal{O}(N^3)$. So, if the size doubles, the effect on running time is roughly multiplied by $8$.

In your case, the size of the matrix is multiplied by $40$. Thus, the running time will be multiplied by $(40)^3$. Which gives you an estimate of $\approx 32$ seconds.

Inquest
  • 6,635
  • I agree with your analysis, but I just did a Matlab experiment to see how accurate this is. I ran the following code: mtrx = randn(50);tic;out=lu(mtrx);time1=toc;mtrx=randn(2000);tic;out=lu(mtrx);time2=toc;disp(num2str(time1));disp(num2str(time2)); On my computer, time1 is $\approx$ .005 seconds, time2 is $\approx$ .24 seconds. The second LU factorization took only about 45 times longer. – littleO Feb 20 '14 at 06:51
  • 1
    Exactly why I emphasized the word rough. When doing Order of Growth analysis, you MUST disregard any compiler optimizations, smart caching, parallelism or any kind of such "smart tricks". You cannot compare the theory with empirical evidence so simply. MATLAB does a lot of smart overhead to solve your matrix efficiently, and thus, will not give you the true picture. If you do want to verify it, consider writing your own Gaussian Elimination code in a low-level language and run a similar experiment. The results will still not match theory perfectly but that's the closest you get :) – Inquest Feb 20 '14 at 07:00
  • @Inquest Probably the best thing to do in order to get well-fitting experimental results would be indeed to implement the elimination manually and adding a fixed delay to each floating point operation :) – Algebraic Pavel Feb 20 '14 at 18:19
  • @littleO You can run a little experiment in Matlab. Generate a set of matrices of growing dimension (say, from 100 to 10000), fit it with a cubic polynomial, and then plot the results (both model and real data). The cubic model fits indeed very well. However, all the optimisation, parallelism, memory issues etc. result in the polynomial having a relatively small leading coefficient. This somewhat contradicts the standard analysis based on the number of floating point operations and indicates that the O(N3) complexity is really only asymptotical and is recognisable only for very large $N$. – Algebraic Pavel Feb 21 '14 at 12:51
  • @littleO E.g., on my laptop, I got the dependency of the elapsed time on $N$ something like this: $p(N)=1.0816\cdot 10^{-11}\times N^3+4.5666\cdot 10^{-9}\times N^2+3.4788\cdot 10^{-6}\times N+0.0026$. You can see how tiny the real $N^3$-coefficient is relatively to the constant one. It is clear that $N$ must be very large to observe the expected behaviour $\frac{p(\alpha N)}{p(N)}\approx\alpha^3$. – Algebraic Pavel Feb 21 '14 at 12:55
0

If you have the Big-O equation of this algorithm, $T(n)=O(n^3)$ (from Wiki), you will estimated the time:

$n_1 = 50, t_1=500=k\cdot n_1^3$

$n_2=2000=40 \cdot n_1 \Rightarrow t_2=k\cdot n_2^3=k \cdot (40n_1)^3=40^3\cdot t_1$

scozv
  • 101