Paper Info
Title
Exploiting Kant and Kimura’s Matrix Inversion Algorithm on FPGA
Abstract
Matrix inversion for real-time applications can be a challenge for the designers since its computational complexity is typically cubic. Parallelism has been widely exploited to reduce such complexity, however most traditional methods do not scale well with the matrix size leading to communication bottlenecks. In this paper we exploit a decentralised parallel hardware architecture based on a strongly non-singular matrix inversion algorithm proposed by Kant and Kimura in 1978, which is a parallel-orientated method with communication mode independent of the matrix size, mitigating the problem of matrix scalability. The hardware architecture is implemented in two different approaches using fixed-point arithmetic: dedicated and shared. In the first approach a matrix can be inverted in linear time while the latter, for the best case, has a square complexity. Experimental results are demonstrated using a Stratix V GX FPGA. For instance, in dedicated approach an 8x8 matrix is inverted in 1.27us, while in shared approach a 64x64 matrix is inverted in 153.40us using 64 pipelined processing elements.
Year
DOI
Venue
2017
10.1109/DSD.2017.32
2017 Euromicro Conference on Digital System Design (DSD)
Keywords
Field
DocType
computational complexity,decentralised parallel hardware architecture,nonsingular matrix inversion algorithm,parallel-orientated method,square complexity,Stratix V GX FPGA,Kant-Kimura matrix inversion algorithm,fixed-point arithmetic
Stratix,Matrix (mathematics),Computer science,Matrix decomposition,Parallel computing,Field-programmable gate array,Algorithm,Time complexity,Scalability,Computational complexity theory,Hardware architecture
Conference
ISBN
Citations 
PageRank 
978-1-5386-2147-9
0
0.34
References 
Authors
9
5
Name
Order
Citations
PageRank
André B. Perina110.75
Paulo Matias200.68
Eduardo Marques311216.31
Vanderlei Bonato414517.19
Joao Miguel Gago Pontes de Brito Lima510.73