Development of Floating Point Multiplier Used in LU-Factorization Hardware Interpreter

Given a system of linear equations, a complete reduction of the coefficient matrix to Reduced Row Echelon (RRE) form is far from the most efficient algorithm if one is only interested in finding a solution to the system. However, the Elementary Row Operations (EROs) that constitute such a reduction are themselves at the heart of many frequently used numerical (i.e., computer-calculated) applications of Linear Algebra. EROs can be used to produce a so-called LU-factorization of a matrix into a product of two significantly simpler matrices. Unlike dagonalization and the polar decomposition for matrices these LU Decompositions can be computed reasonably quickly for many matrices. LU-factorizations are also an important tool for solving linear systems of equations. It should be noted that the factorization of complicated objects into simpler components is an extremely common problem solving technique in mathematics. The LU factorization algorithm is as such a very complex and time consuming task. The only way to reduce the time would be to use a hardware interpreter for executing the linear code. The interpreter which takes in a stream of variable length instructions representing the symbolic unrolled instructions in the LU factorization algorithm. The output of the interpreter is the sparse L and U factors where the matrix values are in IEEE-754 double precision format. In this paper, multiplication algorithms are analyzed, cores have been developed in Verilog HDL and its pipelined versions are tested using Field Programmable Gate Arrays (FPGAs).