A Performance Analysis of LU Decomposition and Storage Schemes for Sparse Matrices in MATLAB

The efficient solution of large-scale linear systems, particularly those arising from sparse matrices, is fundamental to numerous applications in science, engineering, and machine learning. Direct methods, such as LU decomposition, offer robustness but face challenges related to computational cost and memory usage when applied naively to sparse problems, primarily due to the phenomenon of fill-in. This thesis investigates the practical performance characteristics of LU decomposition for sparse matrices, focusing on MATLAB's widely used built-in lu() function. A baseline comparison is first established by contrasting a custom LU implementation (myLU) designed for dense matrices with MATLAB's lu() applied to both dense and sparse inputs. Performance is evaluated based on execution time, numerical accuracy, and factor sparsity (fill-in). Subsequently, the thesis explores a key enabler of sparse algorithm efficiency: data storage schemes. The impact of Coordinate (COO), Compressed Sparse Row (CSR), and Compressed Sparse Column (CSC) formats on the performance of the fundamental Sparse Matrix-Vector Multiplication (SpMV) operation is experimentally analyzed and compared against MATLAB's optimized built-in SpMV. Results demonstrate that MATLAB's sparsity-aware lu() function significantly outperforms dense approaches in both speed and memory efficiency, via controlled fill-in, when handling sparse matrices. Furthermore, the SpMV analysis confirms the superior performance of compressed storage formats (CSR/CSC) over COO, while highlighting the exceptional optimization of MATLAB's internal routines. Collectively, these findings underscore the critical importance of utilizing both sparsity-aware algorithms and efficient underlying data structures for tackling large-scale sparse linear systems effectively.