I'm trying to create a Matrix Inversion algorithm using Gaussian elimination method. I know LabView has a built-in functionality for this, but I need to do this over a finite field (i.e. a Galois Field of GF(2^16) ) and be optimised for speed.
Attached are the GF(2^16) VI's, where any subtraction and addittion is a simple XORE operation.
The reason it needs to be a Gaussian elimination method is because of speed. I'll be dealing with very large matrices (guaranteed to be Square and invertible).
While the theory in paper is simple enough, I can't seem to port that methodology into a labview algorithm.
Any help appriciated.
Doing a Web search for Galois Field Arithmetic may give you some ideas. Incidently, if you are using GF(2^16), when you do your multiplication, I don't understand why you are doing mod (2^16)-1. Note you can do mod 2^16 really quickly by using "Convert to U16" or "Convert to I16".
I think you miss-understood the post.
The problem is not the GF Arithmetics. The attached VI's allready work just fine. Its "Matrix Inversion" using "Gaussian Elimination" where the problem lies.
I understnd how to accomplish this by hand. Its trivial mathematics, the problem is importing the methodology into an algorithm.
As for the (2^16)-1, when I generated the log table, I removed 1 element (a 0 and a -1) from both log and inverse log, so I have to reduce the input value (or index) by -1 as well.
You are correct that I didn't directly answer your question about Gaussian Elimination. However, my point about "saving one element" still holds. 0 is a "legal" value in a Galois Field, though it doesn't have an inverse. Multiplication by 0 should give 0. Try it with your multiplication routine -- you'll see that 0 behaves as though it were 1.
There's an obvious problem adding an entry for 0 to a log table (unless you use reals, which can admit NaN). However, by adding a single entry to your table, you should greatly speed up your lookup time. Note that you could put a "fictitious" entry in for 0 (making the table a "nice size"), then just ensure that you never use this entry (by testing the multiplicands for = 0, in which case you don't have to look up anything because you know the product, 0).
In GF(256), there appears to be some well-studied results, and hints that GF(2^32) might be "nice". Why GF(2^16) would be tricky I have no idea.
Hi Bob. Thanks for your reply.
Speed is actually a very important factor in this case (hence the look-up table routine). So when you said...
However, by adding a single entry to your table, you should greatly speed up your lookup time.
Do you mean that I shourld replace the deleted elements from both tables (obviously not with -1), whereby removing the need to subtract the index by -1? I didn't think that -1 would hamper speed much, but then again I never tested it.
It's not the -1, its the division by 65535! You skip the division step (simply convert to a U16, which is very cheap and fast).