分块Gram-Schmidt正交化算法及其应用 |
| |
作者姓名: | 赵韬 姜金荣 |
| |
作者单位: | 1. 中国科学院计算机网络信息中心, 北京 100190;
2. 中国科学院研究生院, 北京 100049 |
| |
基金项目: | 国家自然科学基金(60533020)和中国科学院知识创新工程青年人才领域项目(O714051A01)资助 |
| |
摘 要: | Gram-Schmidt正交化算法是数值线性代数中的基本算法之一,主要用于计算矩阵QR分解.经典和修正Gram-Schmidt正交化算法基于level 1/2 BLAS运算,低级BLAS运算对cache的利用率比较低,从而限制了算法性能.提出一种新的分块Gram-Schmidt正交化算法.新算法通过重正交保证产生矩阵 Q 的正交性达到机器精度,并且利用level 3 BLAS运算提高了算法性能.数值试验表明,新算法能使得矩阵 Q 的正交性达到机器精度,并且新算法使得性能得到显著提高.
|
关 键 词: | Gram-Schmidt Arnoldi算法 正交化 分块算法 QR分解 |
收稿时间: | 2008-04-30 |
修稿时间: | 2008-07-02 |
A block Gram-Schmidt algorithm with its application |
| |
Authors: | ZHAO Tao JIANG Jin-Rong |
| |
Institution: | 1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China;
2. Graduate University, Chinese Academy of Sciences, Beijing 100049, China |
| |
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. |
| |
Keywords: | Gram-Schmidt Arnoldi algorithm orthogonalization block algorithm QR |
|
| 点击此处可从《》浏览原始摘要信息 |
| 点击此处可从《》下载免费的PDF全文 |
|