Inverse of a matrix

How long have you got?

Gaussian elimination in software on an implemented microprocessor will work, relatively slowly; if you've got enormous amounts of hardware, each entry of the inverse is of the form [some sum of six products of three entries from the matrix] divided by the determinant, which is a sum of 24 products each of four entries from the matrix, and you can compute everything in parallel and do the whole thing in a few cycles limited by the number of multipliers and by the depth of your addition trees.

Perhaps a good trade-off is Gaussian elimination in hardware; build a circuit which takes inputs A0..A7, B0..B7 and K, and outputs A0-B0*K, A1-B1*K ...

Then start off with

m00 m01 m02 m03 1 0 0 0 m10 m11 m12 m13 0 1 0 0 m20 m21 m22 m23 0 0 1 0 m30 m31 m32 m33 0 0 0 1

in four eight-wide registers, and do successively

row0 -> row0 * 1/m00 row1 -> row1 - m10 * row0 row2 -> row2 - m20 * row0 row3 -> row3 - m30 * row0 row1 -> row1 * 1/m11 row0 -> row0 - m01 * row1 row2 -> row2 - m21 * row1 row3 -> row3 - m31 * row1

and similarly scaling row2 and row3 to have a 1 in the diagonal element then subtracting them from the other rows to kill off the off-diagonal entries.

Or perhaps there are cleverer FPGA-appropriate methods; I'm a mathematician not a hardware person.

Tom

If you are trying to solve the equation

Ax = y

x = 1/A*y

Then there are simpler methods than finding the inverse and multiplying.

Otherwise, a long time ago, I used a symbolical math package that would symbolically give you the inverse of a matrix. That might give you an idea of the complexity. I'm sure that some of the newer ones will do it too.

Newman

There might be a systolic array implementation that would make a convenient FPGA pipeline.

How fast does it need to be? How big can it be?

You will also need the appropriate floating point logic blocks.

-- glen

Thanks all for your valuable feedback. At present, I could only think of the hard approach of doing the inverse, the traditional math way consuming lot of multipliers. Since the solution has to be in FPGA (Xilinx), I cannot think of any software approach. The Speed of operation should be at max 80 Mhz. However pipelining is allowed and latency is tolerant to a reasonable extent. I will be glad to get more feedback on any algorithms conducive for FPGA implementation.

Thanks again, Venkat.