可变维核心矩阵LU分解方法

The LU Decomposition of Dynamic Kernel Matrix

在线性规划问题的发展过程中,基的分解技术一直是求解线性规划问题算法实现的一个重要问题。在传统的线性规划算法中,基逆的乘积形式(PFI)方法和LU分解方法很好的解决了基逆的稀疏性、累计误差等问题。随着线性规划动态分解和核心矩阵的出现,矩阵的动态分解成为了一个新的研究课题。本文主要研究和分析单纯形算法中的核心矩阵的动态分解和存储方法,将经典的LU分解方法应用于核心矩阵的动态分解和存储中,保持了核心距阵的数值稳定性和稀疏性。同时,本文提出置换消元方法可以大大减少LU更新的时间。

With the development of linear programming, the decomposition technology has been playing a significant role in the implementation of the algorithm. In the traditional simplex method, product form of inverse （PFI） and LU decomposition keep the sparsity of the A matrix and decrease the round--off error. Decomposition of dynamic matrix becomes a new research topic as soon as the LP dynamic factorization and kernel matrix came out. This paper discusses the decomposition and storage of kernel matrix hy applying the LU decomposition method, which makes a good result on matrix sparsity and round--off error. Additionally, the permutation elimination method proposed in this paper makes the LU update process more efficient.