Qq in handling matrix

[Observer]

Situation:

Language: Pascal
　　Given: A is a matrix of dimensions of n * n, where 1<=n<=100
　　　　　 and the values of every cells are either 0 or 1.
　　Task: Find A + A^2 + A^3 +...+ A^n
　　　　　(A^n = A dot A dot A ...... for n times)
　　Time: <=1 second

e.g. If A =
　　　　　0 1 0 0
　　　　　0 0 1 0
　　　　　0 0 0 0
　　　　　1 1 0 0

Then the output is
0 1 1 0
0 0 1 0
0 0 0 0
1 2 2 0

If we do direct matrix multiplication for this task, the time complexity is O(n^4). Am I correct?

Are there any quicker method?

[Dominik Michniewski]

Yeah ....
But you could observe that:
A^n = A^(a0*1+a1*2+a2*4+.....)
such that
n = a0*1+a1*2+a2*4+.....
so you must calculate only apropriate powers of A, so I think that time complexity is lowered to (N^3)log(N) ....

Regards
DM

[Observer]

I'm sorry I don't quite understand.

Can you explain more clearly, please?

[Dominik Michniewski]

you have to compute Sigma(A^n) for i=1..n for some n, yes ?
so we should compute only A^n (rest of this you have computed in this process). but
A^n you should compute in less than n steps (in fact in log(n) steps)

i.e.
you want to compute A^90 nice value
so A^90 = A^(0*1 + 1*2 + 0*4 + 1*8 + 1*16 + 0*32 + 1*64)
so you must compute only A^2,A^8,A^16,A^64 ...
and A^8 = ((A^2)^2)^2, A^16 = (A^8)^2 ....
in other words calculate A^(2^i) for such i that 2^i <= n
and from it you have all results faster....

Maybe I said it now clearly

Regards
DM

[Observer]

Ah... Thanks very much.

Here is my interpretation of what you mean:
.......1....2....4....8....16
01 ...1....0....0....0....0 => 1
02 ...0....1....0....0....0 => 1
03 ...1....1....0....0....0 => 2
04 ...0....0....1....0....0 => 1
05 ...1....0....1....0....0 => 2
06 ...0....1....1....0....0 => 2
07 ...1....1....1....0....0 => 3
08 ...0....0....0....1....0 => 1
09 ...1....0....0....1....0 => 2
10 ...0....1....0....1....0 => 2
---------------------------
Sum:5....5....4....3....0 => 17

This may lead to quicker calculation.

[Observer]

However ......

I know this method makes calculating A^n faster.
But how about Sigma(A^i) for i := 1 to n ??
(As A^i = A^(i-1) * A, only n such multiplication is req. for Sigma(A^i) for i := 1 to n if we do it sequentially)

Please help!!!!!!!!

P.S. As you may know, the time complexity of common matrix multiplication algorithm is O(n^3). How can this be improved?

[Dominik Michniewski]

It's almost it, but:
......1....2....4....8....16
01 ...1....0....0....0....0 => 1
02 ...0....1....0....0....0 => 1
03 ...1....1....0....0....0 => 2 <=> 1 because A and A^2 you have now
04 ...0....0....1....0....0 => 1
05 ...1....0....1....0....0 => 2 <=> 1
06 ...0....1....1....0....0 => 2 <=> 1
07 ...1....1....1....0....0 => 3 <=> 2
08 ...0....0....0....1....0 => 1
09 ...1....0....0....1....0 => 2 <=> 1
10 ...0....1....0....1....0 => 2 <=> 1
---------------------------
Sum:5....5....4....3....0 => 17 <=> 11

So you need fewer operations .... you must momoraize A^(2^i) in memory and used it if necessary ... you use more momory, but got better time

DM

[Observer]

you must memorize A^(2^i) in memory and used it if necessary ... you use more memory, but got better time

Excuse me. Can you explain what you mean by "store it in memory"?
Do you mean storing it in an array?

And what will the new time complexity approximately be?

(Sorry for all that fuss because I'm just a beginner :p )

P.S. As you may know, the time complexity of common matrix multiplication algorithm (e.g. a single A * A operation) is O(n^3). How can this be improved? Are there any faster method?

[Observer]

Finally......

I've figure out that due to the nature of my qq, I can solve it using another algorithm which is more efficient......




Anyway, thanks for your help!!!

[Dominik Michniewski]

That's nice ))

DM