
Dec 28th, 2023, 06:33 AM
#1
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)

Dec 28th, 2023, 07:17 AM
#2
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>

Dec 28th, 2023, 10:14 AM
#3
Re: Matrix inversion
Originally Posted by 2kaud
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.

Dec 28th, 2023, 11:33 AM
#4
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 reinvented! If someone is thinking 'this would nice to have' then their thinking is going to be readjusted.
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)

Dec 28th, 2023, 02:00 PM
#5
Re: Matrix inversion
Originally Posted by 2kaud
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 reinvented! If someone is thinking 'this would nice to have' then their thinking is going to be readjusted.
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 Onotation 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.

Dec 28th, 2023, 03:10 PM
#6
Re: Matrix inversion
Originally Posted by OptionBase1
Edit to add: I have no idea what the Onotation 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>

Dec 28th, 2023, 04:13 PM
#7
Re: Matrix inversion
Originally Posted by wqweto
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!).

Dec 29th, 2023, 04:33 AM
#8
Re: Matrix inversion
Can you post the link to the slow c++ code you found that you have already tried?
https://stackoverflow.com/questions/...seofamatrix
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

Forum Rules

Click Here to Expand Forum to Full Width
