Home // ICDT 2021, The Sixteenth International Conference on Digital Telecommunications // View article

Optimized Architecture for Sparse LU Decomposition on Matrices with Random Sparsity Patterns

Authors:
Dinesh Kumar Murthy
Semih Aslan

Keywords: Pivoting; latency; linear systems; throughput; LU Decomposition; Field Programmable Gate Arrays (FPGAs).

Abstract:
This paper investigates a method for improving the performance of sparse Lower-Upper (LU) decomposition which is widely used to solve sparse linear systems of equations, appearing in many scientific and engineering application models. However, LU decomposition is considered a computationally expensive tool. When dealing with large sparse matrices, numerical decomposition takes more time using normal matrix LU implementation. The problem of interest here is the irregular sparsity pattern which limits performance gain. An efficient architecture for sparse LU decomposition is proposed for both symmetric and asymmetric matrices with random sparsity percentages and patterns. The algorithm spends time in simultaneous localization and mapping of the sparse matrix and then solving the linearized system. The performance of the algorithm with matrices of varying parameters is calculated and compared with a regular LU decomposition algorithm. In most cases, there are performance improvements in terms of speed, area, and power.

Pages: 6 to 10

Copyright: Copyright (c) IARIA, 2021

Publication date: April 18, 2021

Published in: conference

ISSN: 2308-3964

ISBN: 978-1-61208-835-8

Location: Porto, Portugal

Dates: from April 18, 2021 to April 22, 2021