LU分解分块算法的研究与实现.pdfVIP

第3l卷计舞撬专辑 耩衮辉大学攘(自然辩学蔽) 2008筇12月 JOURNALOFNNJINGNORMALUNIVERSTrY(NaturalScien。e1 Dee，2008 LU分解分块算法的研究与实现 纪坤，陈建平 (囊逶大学诗簿糗辩学与鼓本学貔，注苏毒逶226019) [摘要】对稠密型线性方程缀的系数矩阵进行分块Lu分解，从而更充分地利用高速缓存，提高运算效率．文中对LU分解分块 算法进行了研究，用VC++6．0对分块算法进行宏现，并与标准的LU分解算法进行了比较，在大矩阵情况下，分块算法比标准 算法运锋速度提高40％一4s％． 【关键弱】瑗努舞，筵簿努块，矩瘁俊速程秉，VC++6。0 以求解线性方程组的I脚分解为代表的数值计算在现代科学研究和工程技术中得到广泛应用．当今 的计算机在高速的CPU和低速的存储器之间设置了二级或更多级的高速缓冲存储器(简称高缓，cache)． 高缓懿存取速度很快，毽容量较小，将计算桃当前歪在运算的数据或经常需要访闻的数据置予高缓中，让 数据存取的速度适应CPU的处理速度，从而提高计算视整体的运算速度．对于大型方程缀，其系数矩阵缀 大，标准LU分解直接对大矩阵进行计算，一次参与运算的数据量很大，不能很好地利用当今计算机的嵩 缓，运算效率不高．本文对LU分解运用分块算法，通过将火矩阵分块，使备部分小的子矩阵的数据运算能 够更多地在高缓中进行，嗣时采取矩阵转置、循环展开等优化技术，对分块算法中各个模块的计算设计了 较高效豹算法，提高了算法酶总体运算效率． 1 LU分解分块算法 LU分解用于求解线形方程组： 霹ll茁l+1112X2+…+a14茗=bl 8：，筏+a22x2+．…+口h茗n=6：或写成矩阵形式：舭：6 (1) a^1茁1+an2x2+…+口胁茗A=b“ 扶高豢潢去法出发，对其系数矩阵A经过一系裂初等行变换，A可分勰势单位下三兔阵纛j麓上三焦阵￡， 之积： ● ● ● 口 U H “ h 抡 h ■ ● ● 。 U 扎 笠 = 峨e是 A LU 2 h； h； ● ● ● 窿H ●k；k ●；k √ijjooooo飞 赫M 则方程组的求解化为：LUx=西 (3) 它等价于两个三角方程组Ly=b(下三角方程组)和酞=J，(上三角方程组)，很容易通过回代的方式求 簿。这样，线性方程组的求鳞闺题就归结为系数矩阵A的LU分解问题．陵矩阵乘法有： 秘鞋=8牡(J=1，2，…，精) 1n=all／u11(i=1，2，…，，1) u每：口茸一曼如柳(_『。¨+1’…，扎) (4) 如=《8镰一∑‰驻砒)／ua(i=k+1，露+2，…，rt；k=2，3，…，站) 式(4)即为标准LU分解的计算公式，蹩个数据计算在