Improved LU decomposition by exploiting structures in banded systems in model predictive control

Abstract

In large-scale control and simulation problems, efficient solutions for sparse matrices are crucial. Traditional methods, like direct LU decomposition, become computationally costly, particularly when matrix size increase, limiting their effectiveness in applications involving rapid computations. This dissertation introduces a new algorithm developed to address these challenges, specifically for large banded sparse matrices, with applications in linear time-invariant systems. The proposed algorithm begins by performing local LU decomposition on small repetitive block matrices within the overall structure, utilizing these foundational decompositions throughout the entire matrix. This decomposition transforms the matrix into a structured form that permits unified elimination of variables, preserving the banded and sparse characteristics crucial for computational efficiency. Through elimination process, the matrix further simplifies into one that is dependent on a single variable, reducing the problem’s dimensionality. This transformation achieves a reduction in computational complexity from $O(N(2m+n)^3)$ to $O(Nn^3)$. The restructured matrix exhibits a tridiagonal block form, suitable for efficient resolution through the block matrix chasing method, commonly known as the Thomas algorithm. To validate the effectiveness of the proposed algorithm, comparative numerical experiments were conducted using MPC benchmarks. Both the proposed algorithm and direct LU decomposition were applied to solve these benchmarks.