收稿日期: 2008-04-30
修回日期: 2008-07-02
网络出版日期: 2009-03-15
基金资助
国家自然科学基金(60533020)和中国科学院知识创新工程青年人才领域项目(O714051A01)资助
A block Gram-Schmidt algorithm with its application
Received date: 2008-04-30
Revised date: 2008-07-02
Online published: 2009-03-15
Gram-Schmidt正交化算法是数值线性代数中的基本算法之一,主要用于计算矩阵QR分解.经典和修正Gram-Schmidt正交化算法基于level 1/2 BLAS运算,低级BLAS运算对cache的利用率比较低,从而限制了算法性能.提出一种新的分块Gram-Schmidt正交化算法.新算法通过重正交保证产生矩阵 Q 的正交性达到机器精度,并且利用level 3 BLAS运算提高了算法性能.数值试验表明,新算法能使得矩阵 Q 的正交性达到机器精度,并且新算法使得性能得到显著提高.
关键词： Gram-Schmidt; Arnoldi算法; 正交化; 分块算法; QR分解
赵韬 , 姜金荣 . 分块Gram-Schmidt正交化算法及其应用[J]. 中国科学院大学学报, 2009 , 26(2) : 224 -229 . DOI: 10.7523/j.issn.2095-6134.2009.2.011
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
[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
/
| 〈 |
|
〉 |
