Fast matrix exponentiation

general
1

I’m trying, without success, to find a good resource to learn how to do fast exponentiation of a square matrix, one of the requirements for problem COOK50 WW2. Is there anything any of you could reference here? I’m assuming that I really need that promised O(n^3) performance (which I figured out in my frustrated searchs) to have a chance beating the N^9 problem constraint.

EDIT: forget about the implied relation between n^3 and N^9, obviously they don’t relate, and if they did I would be doomed anyway. the n^3 I mentioned was because I saw someone talk about using a formulate to calculate this based on the eigenvalues and eigenvectors of the original matrix, does that makes sense?

2

It’s analogus to when you have to find a^b in O(logn) time.

Here refer this link
and 43rd point of this link

1 Like
3

This link helped a lot! Thank you! I hadn’t thought of using expo by squaring… this problem helped me grasp fast exponentiation a little better.

4

and here we have a CA =D! http://www.codechef.com/status/WW2,samuelgrig thank you again… (btw, is it okay to link solutions here? couldn’t find anything related in the FAQ)

1 Like
5

Yup… its perfectly ok to give link to solution(s) unless the problem is from an ongoing contest :slight_smile:

1 Like