# LabVIEW

cancel
Showing results for
Did you mean:

## inverting matrix

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

Message 1 of 7
(2,640 Views)

## Re: inverting matrix

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

Message 2 of 7
(2,603 Views)

## Re: inverting matrix

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.

Message 3 of 7
(2,588 Views)

## Re: inverting matrix

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.

Message 4 of 7
(2,550 Views)

## Re: inverting matrix

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.

Message 5 of 7
(2,541 Views)

## Re: inverting matrix

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

Message 6 of 7
(2,532 Views)

## Re: inverting matrix

Ahh, thanks. Now it makes sense.

Message 7 of 7
(2,528 Views)