More math (bah!)

Discussion in 'General Discussion' started by Frigo, Feb 16, 2006.

Remove all ads!
Support Terra-Arcanum:

GOG.com

PayPal - The safer, easier way to pay online!
  1. Frigo

    Frigo New Member

    Messages:
    2,107
    Likes Received:
    0
    Joined:
    Jan 21, 2006
    I have a problem...

    I have an nxn matrix A what I want to invert:

    A^-1 * A = I
    A^-1 * (A * A^T) = A^T
    A^-1 * (L * L^T) = A^T
    A^-1 * L = A^T * L^T^-1
    A^-1 = A^T * L^T^-1 * L^-1

    L is a lower triangular matrix such that (L * L^T) = (A * A^T). We get L with the use of Cholesky decompositio. It needs a symmetric, positive definite matrix to decompose; and multiplying a matrix with its own transpose always results with such.

    Operation count:

    A * A^T -> 1/2 * n^3 (we need only the half of the matrix)
    cholesky decomposition: 1/6 * n^3
    lower triangular inverting: 1/6 * n^3
    A^T * L^T^-1 -> 1/2 * n^3
    A^T * L^T^-1 * L^-1 -> 1/2 * n^3

    total operation count: 11/6 * n^3 ~ 2 * n^3 -> BAAAAD! This is the problem!

    To my knowledge this algorithm can be done with about 1 * n^3 operation counts, but I don't know how. Can anyone help?

    ---

    And another problem: how can I decompose an nxn matrix A into a symmetric matrix and any other component that is easily invertible, with few operations, and great stability?
     
  2. Bunny

    Bunny New Member

    Messages:
    2,028
    Likes Received:
    0
    Joined:
    Nov 13, 2004
    And I will never ever ever ever ever write a song about a Frigo!

    (I was going to sing "I freaking hate Frigo!" but that's not completely true, I just hate your maths.)
     
  3. Sofokl

    Sofokl New Member

    Messages:
    913
    Likes Received:
    0
    Joined:
    Nov 1, 2005
    Frigo, If I would have known words and symbols you used, I maybe would have solved this problem.
     
  4. Wolfsbane

    Wolfsbane Well-Known Member

    Messages:
    4,485
    Likes Received:
    3
    Joined:
    Nov 11, 2005
    ... I think he's trying to slowly kill us.
     
  5. Sofokl

    Sofokl New Member

    Messages:
    913
    Likes Received:
    0
    Joined:
    Nov 1, 2005
    No, Wolfsbanefurer, he only tries to establish new Austro-Hungarian Empire straightly on our heads.
     
  6. Stringy Pete

    Stringy Pete New Member

    Messages:
    78
    Likes Received:
    0
    Joined:
    Feb 8, 2006
    Whatever he is doing, it's cunning and we couldn't guess what it is even in our wildest dreams.
    He is deluding our minds with his strange and complex math while doing something unthinkable.
     
  7. Blinky969

    Blinky969 Active Member

    Messages:
    4,132
    Likes Received:
    0
    Joined:
    Jul 8, 2003
    I have a question for you Frigo. This is one of my math problems. Ready?

    Prove 7.
     
  8. Jarinor

    Jarinor New Member

    Messages:
    6,350
    Likes Received:
    1
    Joined:
    Aug 5, 2001
    I did cryptography at uni and I have no fucking idea what you are talking about Frigo.

    No u.
     
  9. Frigo

    Frigo New Member

    Messages:
    2,107
    Likes Received:
    0
    Joined:
    Jan 21, 2006
    It's not crypto; it is just plain linear algebra, matrix inversion; with a "little" inaccuracy in the conventional notation; A^T means transposed A; A^-1 means inverted A.

    But I have found the better algorithm I was talking about the end of my reply; I was misinformed, that algorithm used Strassen's algorithm, not Cholesky's.

    ---

    Did you learn RSA?
     
  10. rosenshyne

    rosenshyne New Member

    Messages:
    3,609
    Likes Received:
    0
    Joined:
    Feb 26, 2002
  11. Jarinor

    Jarinor New Member

    Messages:
    6,350
    Likes Received:
    1
    Joined:
    Aug 5, 2001
    Yes, yes I did learn RSA. I've still got my crypto text book actually.
     
  12. DarkFool

    DarkFool Nemesis of the Ancients

    Messages:
    4,003
    Likes Received:
    5
    Joined:
    Jan 28, 2005
    11 = x + 4
    - 4 - 4
    7 = x
    x = x
    7 = 7

    Right! Done with that... what's next?
     
  13. Peter Quincy

    Peter Quincy Member

    Messages:
    879
    Likes Received:
    0
    Joined:
    Dec 12, 2002
  14. rosenshyne

    rosenshyne New Member

    Messages:
    3,609
    Likes Received:
    0
    Joined:
    Feb 26, 2002
    why don't you prove that y'all aren't losers?
     
  15. Sofokl

    Sofokl New Member

    Messages:
    913
    Likes Received:
    0
    Joined:
    Nov 1, 2005
    Because we had not already studied how to prove it. :-(
    Ot because this cannot be proved. :cry:
     
  16. Blinky969

    Blinky969 Active Member

    Messages:
    4,132
    Likes Received:
    0
    Joined:
    Jul 8, 2003
    Good job, I think you just proved it. Dumb ass.
     
  17. Sofokl

    Sofokl New Member

    Messages:
    913
    Likes Received:
    0
    Joined:
    Nov 1, 2005
    Thanks. :cry:
     
  18. Peter Quincy

    Peter Quincy Member

    Messages:
    879
    Likes Received:
    0
    Joined:
    Dec 12, 2002
    As a reward I present you with the Spoiled Cheese Whiz Of Mediocrity.
     
  19. Blinky969

    Blinky969 Active Member

    Messages:
    4,132
    Likes Received:
    0
    Joined:
    Jul 8, 2003
    Because his mediocrity is only second to his inferiority?
     
  20. Sofokl

    Sofokl New Member

    Messages:
    913
    Likes Received:
    0
    Joined:
    Nov 1, 2005
    Yes. I'm too bored to argument with you.
     
Our Host!