Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/139161
Title: New heuristics for the shortest linear program (SLP) problem for large matrices
Authors: Ng, Chih Qing
Keywords: Science::Mathematics
Issue Date: 2020
Publisher: Nanyang Technological University
Abstract: The aim of this paper is to propose an efficient algorithm (with polynomial or lower time complexity) to minimise the number of XOR gates required to compute a system of linear equations over GF(2) field. Firstly, famous Paar and Boyar-Peralta’s algorithms are reviewed, followed by introducing two new heuristic which incorporate the fundamental concepts of Paar and Boyar-Peralta’s algorithms. The two new method outperform Paar in terms of having lower XOR counts for matrices with high density (ρ = 0.7 to 0.9) and in terms of computational timing, both methods greatly lower the time required as compared to Boyar-Peralta’s algorithm. Therefore, making both methods applicable and efficient in solving large matrices of size greater than 32 × 32, especially if the matrices are of high density.
URI: https://hdl.handle.net/10356/139161
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
FYP_THESIS.pdf
  Restricted Access
346.3 kBAdobe PDFView/Open

Page view(s)

152
Updated on May 15, 2022

Download(s) 50

26
Updated on May 15, 2022

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.