用GPU加速求解线性方程组的高斯消元法

Accelerating Gaussian elimination method for linear systems on GPU

提出了应用图形处理器(GPU)加速求解线性方程组的高斯消元法,用二维四通道纹理表示系数矩阵与常数向量构成的矩阵,在该矩阵内完成归一化、消元等操作。提出了新的纹理缩减算法,该算法不要求纹理的边长是2的幂,把该纹理算法应用于高斯消元法的列主元搜索和确定主元行号。根据这些算法,使用OpenGL着色语言编程,用图形处理器实现加速求解线性方程组的高斯消元法,运算时间与基于CPU的算法比较,随着方程组未知量数量增多,基于GPU的算法具有较快的运算速度,证实图形处理器能加速线性方程组的求解。

An algorithm accelerating Gaussian elimination method for linear systems on the GPU is presented. The matrix combined by the coefficient matrix and constant vector is expressed by a two-dimension four-channel texture, where normalization and elimination are implemented. Anewtexturereductionalgorithmnotrequiringthesizeofthetexturebethepowerof2ispresented, and the new reduction algorithrn is applied to finding the column pivot and determining the row index of the column pivot in Gaussian elimination method. Based on these algorithms, Gaussian elimination for solving linear systems is implemented using the GPU with OpenGL shading language. The running time is compared against those on the CPUs, and result proves that the algorithm on the GPU has a fast running time while the unknowns increasing. This work proves that the GPU can accelerate the solution for the linear systems.