基于双倍双精度施密特正交化方法的QR分解算法  

QR Decomposition Based on Double-double Precision Gram-Schmidt Orthogonalization Method

作　　者：金洁茜 谢和虎[2] 杜配冰 全哲 姜浩[4] JIN Jiexi;XIE Hehu;DU Peibing;QUAN Zhe;JIANG Hao(College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China;Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China;Northwest Insititute of Nuclear Technology,Xi'an 710024,China;College of Computer Science and Technology,National University of Defense Technology,Changsha 410073,China)

机构地区：[1]湖南大学信息科学与工程学院,长沙410082 [2]中国科学院数学与系统科学研究院,北京100190 [3]西北核技术研究所,西安710024 [4]国防科技大学计算机学院,长沙410073

出　　处：《计算机科学》2023年第6期45-51,共7页Computer Science

基　　金：国家自然科学基金(61907034);国家重点研发计划(2020YFA0709803);科学挑战专题(TZ2016002)。

摘　　要：当矩阵的规模较大或者条件数较高时,格拉姆-施密特(Gram-Schmidt)正交化算法和其相关修正算法时常表现出数值不稳定性的现象。为了解决该问题,探索了修正Gram-Schmidt算法(MGS)中舍入误差的累积效应,然后基于无误差变换技术和双倍双精度算法,设计并实现了双倍双精度修正Gram-Schmidt正交化算法(DDMGS)。该算法的精度测试中显示所提算法较分块施密特正交化(BMGS_SVL,BMGS_CWY,BCGS_PIP与BCGS_PIO)的变体算法具有更好的数值稳定性,证明了DDMGS算法能够有效地减少矩阵的正交性损失,提升数值精度,展示了所提算法的可靠性。在算法的性能测试中,首先计算并比较了不同算法的浮点计算量(flops),随后将所提DDMGS算法与修正施密特正交化算法在ARM和Intel两款处理器上作比较,虽然DDMGS算法的运行时间分别是MGS的5.03倍和18.06倍左右,但获得了明显的精度提升效果。The Gram-Schmidt orthogonalization algorithm and its related modified algorithms often show numerical instability when computing ill-conditioned or large-scale matrices.To solve this problem,this paper explores the cumulative effect of round-off errors of modified Gram-Schmidt algorithm(MGS),and then designs and implements a double-double precision modified Gram-Schmidt orthogonalization algorithm(DDMGS)based on the error-free transformation technology and double-double precision algorithm.A variety of accuracy tests illustrate that DDMGS algorithm has better numerical stability than the varients of BMGS_SVL,BMGS_CWY,BCGS_PIP and BCGS_PIO algorithms,which proves that DDMGS algorithm can effectively reduce the loss of orthogonality of matrix,improve the numerical accuracy,and demonstrate the stability of our algorithm.In the performance test,the floating point computations(flops)of different algorithms are calculated and then compared DDMGS algorithm with the modified Gram-Schmidt algorithm on ARM and Intel processors,the runtime of the DDMGS algorithm proposed in this paper isabout 5.03 and 18.06 times that of MGS respectively,but the accuracy is improved significantly.

关 键 词：施密特正交化算法 QR分解 无误差变换 双倍双精度算法 舍入误差 浮点算术 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]