Results 1 to 8 of 8

Thread: Matrix inversion

  1. #1

    Thread Starter
    Frenzied Member 2kaud's Avatar
    Join Date
    May 2014
    Location
    England
    Posts
    1,037

    Matrix inversion

    I've been tasked with coding a 2d square matrix inversion routine in c/c++. The side of the matrix is expected to be in the range >= 2 and <= 70. My knowledge of numerical algorithms is very limited - but as I wasn't present when the task was handed out I drew by default the short straw as nobody else wanted it either! Please don't ask why or say that matrix inversion is usually not the way to go etc etc etc. I'm not to reason why but to produce or die!

    I've looked on the internet and found some C++ code that does the job - but it's O(n!) (yes, n factorial). It works but is obviously slow for larger matrix sizes. Other internet references mention gauss elimination etc etc but this is beyond my maths level for this topic.

    Can anyone help with a link to a resource that explains simply how to invert a matrix or - even better - a link to some c/c++ that is efficient for large matrix sizes.

    Thanks.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  2. #2
    PowerPoster wqweto's Avatar
    Join Date
    May 2011
    Location
    Sofia, Bulgaria
    Posts
    5,301

    Re: Matrix inversion

    Matrix Inversion using LU Decomposition is O(n^3) algorithm for square matrixes and looks doable i.e. there is no Fourier Transform used.

    Ask ChatGPT for explanation incl. sekeleton/scaffolding of the code.

    There are some O(n^2.7) algorithms but for n <= 70 there is just no point considering these.

    cheers,
    </wqw>

  3. #3
    PowerPoster
    Join Date
    Nov 2017
    Posts
    3,248

    Re: Matrix inversion

    Quote Originally Posted by 2kaud View Post
    I've looked on the internet and found some C++ code that does the job - but it's O(n!) (yes, n factorial). It works but is obviously slow for larger matrix sizes. Other internet references mention gauss elimination etc etc but this is beyond my maths level for this topic.
    Gauss elimination is probably the simplest method to do this. If you would struggle to do this on paper, then writing code to do it is going to be problematic.

    If your company is making frequent use of matrices in code, then you must have code available that performs an rref of a matrix.

    For an nxn matrix, just create a new nx2n matrix where the "left nxn" matrix is the original, and the "right nxn" matrix is the nxn Identity Matrix (diagonal 1's from top left to bottom right, all other values are 0).

    Pass that new matrix to an rref function. The returned nx2n matrix should now be in the format where the returned "left nxn" matrix is the Identity Matrix, and the "right nxn" matrix is the inverse of the original.

    Good luck.

  4. #4

    Thread Starter
    Frenzied Member 2kaud's Avatar
    Join Date
    May 2014
    Location
    England
    Posts
    1,037

    Re: Matrix inversion

    If you would struggle to do this on paper, then writing code to do it is going to be problematic.
    Yes! That's why I was hoping for a link to some working c/c++ code.

    If your company is making frequent use of matrices in code, then you must have code available that performs an rref of a matrix.
    Not that I know of, but if we are somewhere then we should be using a 3rd party library such as Eigen.

    As I suspected, this isn't going to be a task to do if you don't know the maths. I'm also making enquiries as to why it's being asked for and who's asking and for what reason. If someone is doing a project that's making heavy use of matrices then they should be using Eigen rather then having wheels re-invented! If someone is thinking 'this would nice to have' then their thinking is going to be re-adjusted.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  5. #5
    PowerPoster
    Join Date
    Nov 2017
    Posts
    3,248

    Re: Matrix inversion

    Quote Originally Posted by 2kaud View Post
    Yes! That's why I was hoping for a link to some working c/c++ code.



    Not that I know of, but if we are somewhere then we should be using a 3rd party library such as Eigen.

    As I suspected, this isn't going to be a task to do if you don't know the maths. I'm also making enquiries as to why it's being asked for and who's asking and for what reason. If someone is doing a project that's making heavy use of matrices then they should be using Eigen rather then having wheels re-invented! If someone is thinking 'this would nice to have' then their thinking is going to be re-adjusted.
    This may or may not be helpful, if you haven't seen it already.

    https://en.wikipedia.org/wiki/Gaussi...ion#Pseudocode

    That's the key part of the process, since REF->RREF is trivial.

    Good luck.

    Edit to add: I have no idea what the O-notation cost is of that pseudocode. It is entirely possible that a full implementation of that psueudocode along with the remaining code that would be necessary to complete the solution would also be O(n!), which would put you back where you already are at, which is you have code you found but it is too slow.

    Can you post the link to the slow c++ code you found that you have already tried?
    Last edited by OptionBase1; Dec 28th, 2023 at 02:04 PM.

  6. #6
    PowerPoster wqweto's Avatar
    Join Date
    May 2011
    Location
    Sofia, Bulgaria
    Posts
    5,301

    Re: Matrix inversion

    Quote Originally Posted by OptionBase1 View Post
    Edit to add: I have no idea what the O-notation cost is of that pseudocode. It is entirely possible that a full implementation of that psueudocode along with the remaining code that would be necessary to complete the solution would also be O(n!), which would put you back where you already are at, which is you have code you found but it is too slow.
    Btw, the same article says ". . . it has a time complexity of O(n^3)."

    cheers,
    </wqw>

  7. #7
    PowerPoster
    Join Date
    Nov 2017
    Posts
    3,248

    Re: Matrix inversion

    Quote Originally Posted by wqweto View Post
    Btw, the same article says ". . . it has a time complexity of O(n^3)."

    cheers,
    </wqw>
    Thanks, I missed that.

    That being said, I bet I could come up with code to calculate the RREF from the REF that would balloon the whole process back to O(n!).

  8. #8

    Thread Starter
    Frenzied Member 2kaud's Avatar
    Join Date
    May 2014
    Location
    England
    Posts
    1,037

    Re: Matrix inversion

    Can you post the link to the slow c++ code you found that you have already tried?
    https://stackoverflow.com/questions/...se-of-a-matrix
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++23 Compiler: Microsoft VS2022 (17.6.5)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width