LU_Decomposition_Experiment

项目概述

本项目旨在比较不同矩阵计算方法（高斯消元法、LU分解等）的性能差异。通过实验测试，我们分析了各种方法在不同矩阵维度下的时间性能和计算精度。

一个问题是，使用Python进行科学计算本身不是一个明智的选择，因为Python是解释性语言，代码要一行一行由解释器进行解释再执行，运行的速度较慢，特别是面对大矩阵的情形，面对时间复杂度为$O(n)$的算法，Python需要耗费大量运行时间。

本文的解决办法是，用Python中的numba库的jit模块，可以将Python内numpy类型的计算加速，通过将代码转化为机器码编译后运行，实际测试大大加速了程序的运行。

numba是一个用于编译Python数组和数值计算函数的编译器，这个编译器能够大幅提高直接使用Python编写的函数的运算速度。numba使用LLVM编译器架构将纯Python代码生成优化过的机器码从而加快运行速度。

环境要求

硬件配置

• CPU: Apple M3
• RAM: 16 GB
• 系统: macOS Sonoma 14.5

软件依赖

• Python 3.12.4
• 必需库：
  • numpy
  • scipy
  • numba

测试方法

1. 随机生成测试矩阵A和解向量x
2. 计算b = Ax作为已知值
3. 使用不同方法求解Ax = b
4. 比较计算结果与原始x的误差

性能测试结果

单次运行结果（1000维矩阵）

方法	时间 (s)	误差
高斯-若尔当法	1.3700	6.3034e-14
高斯消元法	0.5567	5.6826e-14
SciPy LU分解	0.0972	3.3437e-14
自定义LU分解	0.5487	5.0448e-14
自定义PLU分解	0.6407	5.0465e-14

单次运行结果（5000维矩阵）

方法	时间 (s)	误差
高斯-若尔当法	82.1222	2.9699e-13
高斯消元法	25.7189	2.8221e-13
SciPy LU分解	8.2013	1.6114e-13
自定义LU分解	32.2374	2.4348e-13
自定义PLU分解	35.1510	2.4357e-13

性能分析

时间性能

• 高斯-若尔当法：计算量最大，性能最差
• 高斯消元法：性能优于高斯-若尔当法
• SciPy LU分解：性能最优，利用硬件加速
• 自定义LU/PLU分解：性能接近高斯消元法

误差分析

• SciPy实现：误差最小，数值稳定性最好
• 自定义实现：误差略大，但仍在可接受范围
• 高斯-若尔当法：误差最大

时间复杂度对比

方法	单次求解时间复杂度	多次求解总时间复杂度 (m 次)
高斯消元法	O(n³)	O(m·n³)
LU 分解	O(n³) + O(n²)	O(n³) + m·O(n²)

结论

1. 对于单次求解，SciPy的LU分解性能最优
2. 对于多次求解，LU分解的性能优势更加明显
3. 使用numba的jit模块可以显著提升自定义实现的性能