Solving system of equations O(n =?) complexity doubt.

[cnoe]

Hi,
'C' Programmer

this query may be not related to C language

but I want to hear your comments,

so I'm asking here.

Every now and then while programming we have to have

deal with Matrices,and one of the

time consuming and involving heavy computation complexity

is Matrix_multiplication & solving system of equations(LU)

For_Multiplication :-

a) General_Algo: Complexity is O(n^3)
i.e cubic, means sky rocketing for big matrices


b) Volker Strassen's_Algo: complexity is O(n^2.81)
i.e for a 2x2 matrix only 7 multiplications
instead of 8 and useful for matrices
of order 5000x5000

c) Bini,Capovani,Lotti and Romani's_Algo:
Complexity is O(n^2.7799)

d) Schonhage's_Algo: complexity is O(n^2.695)

e) Victor Pan's_Algo: complexity is O(n^2.52)

f) Coppersmith and Winograd's_Algo: O(n^2.367)


if you observe the last one, it's the best known
algorithm for matrix_multiplication.

My_doubt is :-

On a normal home PC, consider a matrix of
order billion x billion

if we implement "Gauss Jordan" elimination
how much time it will take.?

just your rough guess is enough.
if you want to tell more,please do share it.


Thanks for sharing

 

[Keith Thompson]

'C' Programmer

this query may be not related to C language

It isn't.

but I want to hear your comments,

so I'm asking here. [snip]
On a normal home PC, consider a matrix of
order billion x billion

if we implement "Gauss Jordan" elimination
how much time it will take.?

Try asking in comp.programming.

 

[Antoninus Twink]

Try asking in comp.programming.

Come on Keith, you know perfectly well that this is a C question with a
C answer. He's asking about implementing an algorithm with known runtime
complexity in C on his system. Here's a simple program to give him a
lower bound (in reality, of course, it will take a sizeable multiple of
this time, but even this bound will probably make him think twice about
trying):


#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>

#define SEC_PER_YEAR 31536000ULL
#define N 1000000000ULL

volatile unsigned long long c;

void end(int signal)
{
if(signal == SIGALRM) {
printf("An O(n^3) algorithm with n=1 billion will take "
"at least %llu years to run.\n",
N * N * N / (c * SEC_PER_YEAR));
}
exit(0);
}

int main(void)
{
signal(SIGALRM, end);
alarm(1);
for(;
c++;
}

 

[cnoe]

'C' Programmer

this query may be not related to C language

It isn't.

but I want to hear your comments,

so I'm asking here. [snip]
On a normal home PC, consider a matrix of
order billion x billion

if we implement "Gauss Jordan" elimination
how much time it will take.?

Try asking in comp.programming.

yeah I know about it, I can go and post in comp.programming
that's not a problem for me, but I want to see what'C' programmers
think about it, I want to know it's time complexity.

 

[cnoe]

Come on Keith, you know perfectly well that this is a C question with a
C answer. He's asking about implementing an algorithm with known runtime
complexity in C on his system. Here's a simple program to give him a
lower bound (in reality, of course, it will take a sizeable multiple of
this time, but even this bound will probably make him think twice about
trying):

#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>

#define SEC_PER_YEAR 31536000ULL
#define N 1000000000ULL

volatile unsigned long long c;

void end(int signal)
{
  if(signal == SIGALRM) {
    printf("An O(n^3) algorithm with n=1 billion will take "
        "at least %llu years to run.\n",
        N * N * N / (c * SEC_PER_YEAR));
  }
  exit(0);

}

int main(void)
{
  signal(SIGALRM, end);
  alarm(1);
  for(;
    c++;

}

Will it take 'years' to complete?
are you so sure about it,
that means your saying that, it is cubic.

O(n^3) = [10^9]^3 calculations___(assume)

so, how many calculations a normal desktop PC
would do in a second ?

Honestly I don't know the exact answer,

can you people please help in this question?

http://en.wikipedia.org/wiki/Gaussian_elimination
here in the sub-category "Analysis" the wiki describes that
for millions of equations there exists ''Iterative methods'
to handle.
Is there any libraries for that ? OR
Do you know any other about it.


Thank You for suggestions

 

[Bart]

It isn't.

but I want to hear your comments,
so I'm asking here. [snip]
On a normal home PC, consider a matrix of
order billion x billion
if we implement "Gauss Jordan" elimination
how much time it will take.?

Try asking in comp.programming.

yeah I know about it, I can go and post in comp.programming
that's not a problem for me, but I want to see what'C' programmers
think about it, I want to know it's time complexity.

Using C might make the program run up to, say, 50 times faster if the
other language is pure Python. This means a program might only take a
billion years instead of fifty billion.

In practice, a much faster machine would be available long before
then, so it's not even worth attempting anything now; just restart the
program on the faster machine later on and it will still finish first.

 

[Antoninus Twink]

Will it take 'years' to complete? [snip]
so, how many calculations a normal desktop PC would do in a second ?

The program I gave works out exactly that!

When I ran a (slightly modified version that also outputs the final
value of c) on my "normal desktop PC", I got:

$ ./foo
An O(n^3) algorithm with n=1 billion will take at least 806 years to run
(adds per sec=452601759).

YMMV.

(Of course, I am using O(n^3) in its colloquial meaning of Theta(n^3).)

 

[cnoe]

Will it take 'years' to complete? [snip]
so, how many calculations a normal desktop PC would do in a second ?

The program I gave works out exactly that!

When I ran a (slightly modified version that also outputs the final
value of c) on my "normal desktop PC", I got:

$ ./foo
An O(n^3) algorithm with n=1 billion will take at least 806 years to run
(adds per sec=452601759).

YMMV.

(Of course, I am using O(n^3) in its colloquial meaning of Theta(n^3).)

if the matrices are sparse,
symmetric & positive definite then
what is the case.

Thank_you

 

[user923005]

Will it take 'years' to complete? [snip]
so, how many calculations a normal desktop PC would do in a second ?

The program I gave works out exactly that!

When I ran a (slightly modified version that also outputs the final
value of c) on my "normal desktop PC", I got:

$ ./foo
An O(n^3) algorithm with n=1 billion will take at least 806 years to run
(adds per sec=452601759).

YMMV.

(Of course, I am using O(n^3) in its colloquial meaning of Theta(n^3).)

Which desktop PC holds 8 million terrabytes of RAM (hint: 64 bits is
NOT enough to address this memory)?
If you find one, I guess that once you put 8 million terrabytes of RAM
in there, the cost of $10/GB for really cheap RAM will leave this
machine no longer classified as a "desktop system."
I guess it will also consume some thousands of kilowatts/hour. The
electricity will cost orders of magnitude more than the computer to
process this problem.
Now, we have to find components with an MBTF of 806 years. I guess
that such components do not exist can cannot be built.

I guess that even in ten years there will not exist any supercomputer
on the planet with 8 million TB of RAM, let alone a desktop system.
So the actual answer to the question is:
"You can't get there from here."

 

[user923005]

On  3 Feb 2009 at 14:00, cnoe wrote:

Will it take 'years' to complete? [snip]
so, how many calculations a normal desktop PC would do in a second ?

The program I gave works out exactly that!

When I ran a (slightly modified version that also outputs the final
value of c) on my "normal desktop PC", I got:

$ ./foo
An O(n^3) algorithm with n=1 billion will take at least 806 years to run
(adds per sec=452601759).

(Of course, I am using O(n^3) in its colloquial meaning of Theta(n^3).)

if the matrices are sparse,
symmetric & positive definite then
what is the case.

If the matrix is upper triangular, so that we need only 1/2 storage
and can proceed directly, then we could address the RAM with only 64
bits (but just barely, we may have some trouble fitting in the
operating system on a 64 bit system).
The cost of the ram will be 4e18 / 1e9 = 4e9 GB ==> 4e9 GB RAM
required. At $10 per GB for really cheap RAM, this will cost only 40
billion dollars for memory (assuming all zero elements below the
diagonal). However with a matrix this large, I guess that only a
boolean matrix can survive the number of operations and return a
sensible answer (e.g. 8 byte float will have such large accumulated
rounding errors that our answer will contain random numbers).
Now, figure in the cost of electricity. Is the answer to this problem
really worth a trillion dollars to you?

 

[Antoninus Twink]

On 3 Feb 2009 at 19:45, user923005 wrote:
[snip]

I don't think we are in disagreement here - there are many different
ways of seeing that the OP's problem is infeasible.