分块Gram-Schmidt正交化算法及其应用

doi:10.7523/j.issn.2095-6134.2009.2.011

中国科学院大学学报 ›› 2009, Vol. 26 ›› Issue (2): 224-229.DOI: 10.7523/j.issn.2095-6134.2009.2.011

分块Gram-Schmidt正交化算法及其应用

赵韬^1,2, 姜金荣¹

1. 中国科学院计算机网络信息中心, 北京 100190;
2. 中国科学院研究生院, 北京 100049

收稿日期:2008-04-30 修回日期:2008-07-02 发布日期:2009-03-15
通讯作者: 赵韬
基金资助:
国家自然科学基金(60533020)和中国科学院知识创新工程青年人才领域项目(O714051A01)资助 

A block Gram-Schmidt algorithm with its application

ZHAO Tao^1,2, JIANG Jin-Rong¹

1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China;
2. Graduate University, Chinese Academy of Sciences, Beijing 100049, China

Received:2008-04-30 Revised:2008-07-02 Published:2009-03-15

摘要/Abstract

摘要：

Gram-Schmidt正交化算法是数值线性代数中的基本算法之一,主要用于计算矩阵QR分解.经典和修正Gram-Schmidt正交化算法基于level 1/2 BLAS运算,低级BLAS运算对cache的利用率比较低,从而限制了算法性能.提出一种新的分块Gram-Schmidt正交化算法.新算法通过重正交保证产生矩阵 Q 的正交性达到机器精度,并且利用level 3 BLAS运算提高了算法性能.数值试验表明,新算法能使得矩阵 Q 的正交性达到机器精度,并且新算法使得性能得到显著提高.

关键词: Gram-Schmidt, Arnoldi算法, 正交化, 分块算法, QR分解

Abstract:

Gram-Schmidt algorithm is one of the fundamental methods in linear algebra, which is mainly used to compute QR decomposition. The classical and modified Gram-Schmidt are both based on level 1 or level 2 BLAS operations which have low cache reuse. In this paper, a new block Gram-Schmidt algorithm is proposed. The new algorithm ensures the orthogonality of resulting matrix Q is close to machine precision and improves performance because of using level 3 BLAS. Numerical experiments confirm the favorable numerical stability of the new algorithm and its effectiveness on modern computers.

Key words: Gram-Schmidt, Arnoldi algorithm, orthogonalization, block algorithm, QR

中图分类号:

TP31

赵韬, 姜金荣. 分块Gram-Schmidt正交化算法及其应用[J]. 中国科学院大学学报, 2009, 26(2): 224-229.

ZHAO Tao, JIANG Jin-Rong. A block Gram-Schmidt algorithm with its application[J]. , 2009, 26(2): 224-229.

参考文献

[1] Golub GH, Van Loan CF, Matrix computations, 3rd ed. Baltimore: Johns Hopkins University Press, 1996

[2] Daniel JW, Gragg WB, Kaufman L, et al. Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization. Math Comp, 1976, 30:772~795

[3] Stewart GW. Matrix algorithms: basic decompositions. Philadelphia: SIAM, 1998

[4] Jalby W, Philippe B. Stability analysis and improvement of the block Gram-Schmidt algorithm. SIAM J Sci Statist Comput, 1991, 12:1058~1073

[5] Stathopoulos A, Wu K. A block orthogonalization procedure with constant sysnchronization requirements. SIAM J Sci Comput, 2002, 23:2165~2182

[6] Higham NJ. Accuracy and stability of numerical algorithms, 2nd ed. Philadelphia: SIAM, 2002

[7] Hoffmann W. Iterative algorithms for Gram-Schmidt orthogonalization. Computing, 1989, 41:353~367

[8] Abdelmalek NN. Round off error analysis for Gram-Schmidt method and solutions of linear least squares problems. BIT, 1971, 11:345~368

[9] Giraud L, Langou J, Rozloznik M, et al, Rounding error analysis of the classical Gram-Schmidt orthogonalization process. Numer Math, 2005, 101:87~100

[10] Bjorck A. Numerics of Gram-Schmidt orthogonalization. Linear Algebra Appl, 1994, 198:297~316

[11] Parlett N. The symmetric eigenvalue problem. New Jersey: Prentice-Hall, 1980

[12] Bjorck A. Solving linear least squares problems by Gram-Schmidt orthogonalization. BIT, 1967, 7:1~21

[13] Smoktunowicz A, Barlow JL,Langou J. A note on the error analysis of classical Gram-Schmidt. Numer Math, 2006, 105:299~313

[14] Jia ZX. Polynomail characterizations of the refined approximate eigenvectors by the refined Arnoldi method and an implicitly restarted refined Arnoldi algorithm. Linear Algebra Appl, 1999, 287:191~214

[15] Jia ZX. A refined iterative algorithm based on the block Arnoldi process for large unsymmetric eigenproblems. Linear Algebra Appl, 1998, 270:171~189

分块Gram-Schmidt正交化算法及其应用

A block Gram-Schmidt algorithm with its application

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

访问统计

联系我们