Matrix inversion

[2kaud]

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.

[wqweto]

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>

[OptionBase1]

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.

[2kaud]

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.

[OptionBase1]

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?

[wqweto]

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>

[OptionBase1]

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!).

[2kaud]

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