Sparse Matrix Factorization Based On FPGA

Sparse matrix operations are widely used in science and technology, such as network design, computer-aided design, power system optimization design, mathematical programming, structural analysis, solving differential equation, theoretical genetics, graph theory etc. Sparse matrix algorithm has been an important branch of computational mathematics. Solving sparse linear equation is the core of many engineering and scientific applications. The study of sparse matrix operations is of great significance, in which supercomputers and distributed shared-memory multi- computers take a dominant position. While, with continuous developments in the silicon industry and advances in the structural design, FPGA technologies have enabled the implementation of system-on-a-programmable-chip computing platforms. New generation of FPGA has made it possible to integrate a large number of computation modules and build parallel machines in a single chip, which improves performance significantly in computation-intensive field. This dissertation mainly discusses the realization of sparse matrix factorization based on FPGA.Firstly, the characteristics and research value of sparse matrix are introduced. Then we describe various methods that have been explored in the past for speeding-up the process of LU factorization, on the basis of which our designs are presented including sparse ordering methods, LU factorization, symbolic LU factorization, numerical LU factorization and their realization based on FPGA. Finally, by taking advantage of FPGA resources we implement a parallel LU factorization which is verified by BDB sparse matrix and we analyze the experimental results.