Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (6): 45-51.doi: 10.11896/jsjkx.230200209

• High Performance Computing • Previous Articles     Next Articles

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

JIN Jiexi1, XIE Hehu2, DU Peibing3, QUAN Zhe1, JIANG Hao4   

  1. 1 College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China
    2 Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China
    3 Northwest Insititute of Nuclear Technology,Xi'an 710024,China
    4 College of Computer Science and Technology,National University of Defense Technology,Changsha 410073,China
  • Received:2023-02-27 Revised:2023-04-11 Online:2023-06-15 Published:2023-06-06
  • About author:JIN Jiexi,born in 1999,postgraduate,is a member of China Computer Federation.Her main research interest is high performance computing.JIANG Hao,born in 1983,Ph.D,professor,assoicate research fellow.His main research interests include high perfor-mance computing and numerical analysis.
  • Supported by:
    National Natural Science Foundation of China(61907034),National Key Research and Development Program of China(2020YFA0709803) and Science Challenge Project(TZ2016002).

PDF (PC)

3826

Abstract: 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.

Key words: Gram-Schmidt algorithm, QR decomposition, Error-free transformation, Double-double precision algorithm, Roundoff error, Floating-point arithmetic

CLC Number: 

  • TP391
[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.
[1] WANG Kun-shu, ZHANG Ze-hui, GAO Tie-gang. Reversible Hidden Algorithm for Remote Sensing Images Based on Hachimoji DNA and QR Decomposition [J]. Computer Science, 2022, 49(8): 127-135.
[2] CHEN Lei, TANG Tao, QI Hai-jun, JIANG Hao, HE Kang. Design and Implementation of Multithreaded Reproducible DGEMV for Phytium Processor [J]. Computer Science, 2022, 49(10): 27-35.
[3] WANG Wan-liang,CHEN Yu,QIU Hong and ZHENG Jian-wei. Incremental Kernel Discriminant Analysis Method via QR Decomposition [J]. Computer Science, 2014, 41(4): 297-301.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.