计算机科学 ›› 2023, Vol. 50 ›› Issue (6): 45-51.doi: 10.11896/jsjkx.230200209
金洁茜1, 谢和虎2, 杜配冰3, 全哲1, 姜浩4
JIN Jiexi1, XIE Hehu2, DU Peibing3, QUAN Zhe1, JIANG Hao4
摘要: 当矩阵的规模较大或者条件数较高时,格拉姆-施密特(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倍左右,但获得了明显的精度提升效果。
中图分类号:
[1]LEON S J,BJORCK A,GANDER W.Gram-Schmidt orthogonalization:100 years and more[J].Numerical Linear Algebra with Applications,2013,20(3):492-532. [2]HUANG J,GU H.QuickBird image fusion based on Gram-Schmidt transform[C]//Geographic Information and Internet of Things Forum and Proceedings of the 2010 Annual Academic Conference of the Jiangsu Society of Surveying and Mapping.2010. [3]ZHANG K,HSIEH M H,LIU L,et al.Quantum Gram-Schmidt processes and their application to efficient state readout for quantum talgorithms[J].Physical Review Research,2021,3(4):043095. [4]BAILEY D H.A fortran-90 double-double library[J/OL].https://www.davidhbailey.com/dhbsoftware,2001. [5]BAILEY D H,KRASNY R,PELZ R.Multiple precision,multiple processor vortex sheet roll-up computation[R].Society for Industrial and Applied Mathematics(SIAM),Philadelphia,PA (United States),1993. [6]OGITA T,RUMP S M,OISHI S.Accurate sum and dot product[J].SIAM Journal on Scientific Computing,2005,26(6):1955-1988. [7]DEKKER T J.A floating-point technique for extending theavailable precision[J].Numerische Mathematik,1971,18(3):224-242. [8]KAHAN W.Pracniques:further remarks on reducing truncation errors[J].Communications of the ACM,1965,8(1):40. [9]KNUTH D E.The art of computer programming:Vol.3[M].Newyork:Pearson Education,1997. [10]STRANG G.Introduction to linear algebra(5th ed)[M].Wellesley-Cambridge Press,1993. [11]CARSON E,LUND K,ROZLOZNIK M.The Stability of Block Variants of Classical Gram-Schmidt[J].SIAM Journal on Matrix Analysis and Applications,2021,42(3):1365-1380. [12]CARSON E,LUND K,ROZLOZNÍK M,et al.Block Gram-Schmidt algorithms and their stability properties[J].Linear Algebra and its Applications,2022,638:150-195. [13]SCHMIDT E.Zur Theorie der linearen und nichtlinearen Integralgleichungen.III.Teil[J].Mathematische Annalen,1908,65(3):370-399. [14]GRAM J P.Ueber die Entwickelung reeller Functionen inReihen mittelst der Methode der kleinsten Quadrate[J].J Reine Angew Math,1883,94:41-73. [15]WONG Y K.An application of orthogonalization process to the theory of least squares[J].The Annals of Mathematical Statistics,1935,6(2):53-75. [16]DE LAPLACE P S.Théorie analytique des probabilités:Vol.7[M].Courcier,1820. [17]DANIEL J W,GRAGG W B,KAUFMAN L,et al.Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization[J].Mathematics of Computation,1976,30(136):772-795. [18]JALBY W,PHILIPPE B.Stability analysis and improvement of the block Gram-Schmidt algorithm[J].SIAM Journal on Scientific and Statistical Computing,1991,12(5):1058-1073. [19]BARLOW J L,SMOKTUNOWICZ A.Reorthogonalized blockclassical Gram-Schmidt[J].Numerische Mathematik,2013,123(3):395-423. [20]RIVAZ A,MOGHADAM M M,SADEGHI D,et al.An approach of orthogonalization within the Gram-Schmidt algorithm[J].Computational and Applied Mathematics,2018,37(2):1250-1262. [21]Standard for binary floating point arithmetic:ANSI/IEEEstandard 754-2008[S].IEEE,2008. [22]BJORCK A.Numerics of gram-schmidt orthogonalization[J].Linear Algebra and Its Applications,1994,197:297-316. [23]HIDA Y,LI X S,BAILEY D H.Algorithms for quad-double precision floating point arithmetic[C]//Proceedings 15th IEEE Symposium on Computer Arithmetic.IEEE,2001:155-162. [24]LAUCHLI P.Jordan-elimination und Ausgleichung nach kleinsten Quadraten[J].Numerische Mathematik,1961,3(1):226-240. [25]PEI M L.A test matrix for inversion procedures[J].Communications of the ACM,1962,5(10):508. [26]SMOKTUNOWICZ A,BARLOW J L,LANGOU J.A note on the error analysis of classical Gram-Schmidt[J].Numerische Mathematik,2006,105(2):299-313. [27]NISHI T,RUMP S M,OISHI S.On the generation of very ill-conditioned integer matrices[J].Nonlinear Theory and Its Applications,IEICE,2011,2(2):226-245. [28]GRAILLAT S,JÉZÉQUEL F,PICOT R.Numerical validationof compensated summation algorithms with stochastic arithmetic[J].Electronic Notes in Theoretical Computer Science,2015,317:55-69. [29]JIANG H.Study on reliable computing and rounding error ana-lysis in floating-point arithmetic[D].Changsha:National University of Defense Technology,2013. |
|