Journal of University of Chinese Academy of Sciences >
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 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
ZHAO Tao , JIANG Jin-Rong . A block Gram-Schmidt algorithm with its application[J]. Journal of University of Chinese Academy of Sciences, 2009 , 26(2) : 224 -229 . DOI: 10.7523/j.issn.2095-6134.2009.2.011
[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
/
| 〈 |
|
〉 |