It seems that the main problem is precision.
If it is so, how could we compute the answer more accurately?
e.g., set what Epsilon threshold for determining a value being 0 ?

There are some methods to solve problem.
1. Gauss. It really has troubles with precision.
2. Method of iterations. It works good, but your implementation should be fast enough and do about 2^50 iterations :)

Thanks for your reply. :)

I used Gaussian Elimination. Seems it's very difficult to handle the precision...

We tried both methods but failed...
It seems that using iterations could lead to precision problem too..we calc something like mat[64][64],and do mat^(2^60),but it turns out that the value in mat overflows...
Sorry for my poor english-_-

Just add something like that after each multiplication.

void normalize(double a[][64])
{
    for(int i = 0; i < 64; i++)
    {
        double sum = 0;
        for(int j = 0; j < 64; j++)
            sum += a[i][j];
        for(int j = 0; j < 64; j++)
            a[i][j] /= sum;
    }
}

I used Gauss. But with BigDecimal.

Thanks, it helped me =).

Can you explain why iterations more precize than gauss?
Why you think that it is necessary about 2^50 iterations?

I think that there exists a good alternative to Gaussian elimination - QR - decomposition of the matrix. It's precision, I think, would be good enough because it doesn't change the condition number of the matrix.

I tried to solve it as you said. TL #3 ...

QR - decomposition is only a bit slower than Gaussian elimination, and it's also O(n^3)

Could you expalin what is the QR-decomposition? Maybe, I didn't understand you very well.

Thanks a lot! But I don't understand how could it be useful to avoid big precision troubles with Gauss algorithm.

I don't understand too. :-[

These methods have less calculation errors than Gauss method.
But there is modification of Gauss method which more precise than QR-decomposition methods. In this modification we choose main element from all remaining elements in matrix.

You can read about methods for solving systems of linear algebraic equations in the book: А.А.Амосов "Вычислительные методы для инженеров".
Of course, there are a lot of other sources.

Thanks a lot, Nikita! This normailze function really helps!

My program needs only 2^26 iterations using it, and without this function i received WA #1 all the time.

Edited by author 17.06.2010 14:28

Just want to mention that I kept getting WA and after changing double to long double immediately got AC. Maybe it helps