inverting matrix

[zerotolerance]

Hi

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.

Kas

[Bob_Schor]

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".

[zerotolerance]

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.

[Bob_Schor]

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.

[zerotolerance]

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.

[Bob_Schor]

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

[zerotolerance]

Ahh, thanks. Now it makes sense.