hippie's blog

Matrix Exponentiation for TWO-Dimensional Dynamic Programming
By hippie, 10 years ago, In English

The only resource available on the internet regarding the application of matrix exponentiation to TWO-DIMENSIONAL dynamic programming problems is this :-

http://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation

Though the author has covered the topic with nice examples, I have some doubts:-

1) Unlike solving linear recurrences (using matrix exponentiation), I cannot find any solid mathematics behind the steps (or how does it work mathematically) involved in this technique.

2) How are the base-states taken into account in this technique? After building the adjacency-matrix (as is explained in the quora-article), and exponentiating it, what all values do we have to sum up to get the final answer?

I am pretty vague about all these details so any help will be much appreciated.

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The key idea is to convert the problem into a graph problem about finding the number of paths in the graph from some source(s) of a fixed length. The process of doing that depends on the problem and I covered some examples in my comment on that thread, you can look into that. Also, the mathematics behind counting number of paths of a fixed length is pretty basic and standard.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks for the reply. Can I assume that the "source(s)" you mention, in fact, represent the base-case? Also, if i'm not mistaken, the matrix should be raised to the power 'n' and not 'n-1' (as is written in the write-up), right?

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://e-maxx.ru/forum/viewtopic.php?id=444

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is this forum post on tree-DP related to solving 2-D DP problems using matrix exponentiation ?

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I post some time before, a question about matrix exponentiation maybe this can help you, and i posting a link that i found about this topic. this is the post

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your post, but the your link is about solving linear recurrences and not 2-D DP problems.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is one obvious way how to turn some of multi-dimensional recurrences to linear ones. Just like in the last example in your article. For example, if we have 3 parameters (i,j,k) which are bounded: 0<=i<n, 0<=j<m, 0<=k<s, then we can make following substitution: (i,j,k) <-> p=s*(m*i+j)+k, where 0<=p<n*m*s. Now you can re-write all dependences in terms of dp[p]=... But in some cases (hope, not everytime) it can cause more troubles in solving than original problem.

I can't create any really useful example right now, but just to show how it works... Let's take some stupid recurrence: c[i,j]=c[i-1,j]+c[i,j-1] for 1<i<n, 1<j<m. Then we can use the method above: c[i,j]=d[m*i+j] => d[m*i+j]=d[m*i+j-m]+d[m*i+j-1] or simply d[x]=d[x-m]+d[x-1]. And if you have large n but small m — well, maybe it will help.

→ Reply