2ndSequence's blog

Absorbing markov chains implementation (Help).
By 2ndSequence, history, 3 years ago, In English

Greeting,

I was trying to implement that algorithm but i don't know how to calculate F = (I — Q) ^ -1 part, I can not calculate the inverse of the matrix (because i also want to keep the proper fractions as it is)..

Any thoughts? (Or even a blog to read).

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the matrix times the comatrix is det times identity. so inverse is comatrix divided by det, it can be computed in O(n^4) (the comatrix). Wikipedia speaks also of LU decomposition maybe it might help and be faster I don't know if it stays in fractions.

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

    Gaussian elimination, also known as row reduction,

    enable to compute the inverse in O(n^3) and stay in the fraction.

    You write identity next to your matrix and you apply it the same operation as to your matrix,

    when your matrix becomes identity, the identity becomes the inverse

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you so much for your interest..

    I think i knew about Gaussian but i am pretty sure that it doesn't maintain the proper fraction (not sure... to weak in math but it is an assignment..)

    I will try to use the determinant and see what i can do, also i don't care about complexity, Just maintaining the proper fraction.

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

      Just do the calculations in rationals.

      → Reply