当前位置:首页 >> 建筑/土木 >>

QR分解 实验报告


并行计算课程考核 实验报告
考核题目:QR 分解算法的并行实现 并行实现方式:OpenMP 1. 问题概述 QR 分解法是目前求一般矩阵全部特征值的最有效并广泛应用的方法,一般矩阵先经过正交 相似变化成为 householder 矩阵,然后再应用 QR 方法求特征值和特征向量。它是将矩阵分 解成一个正规正交矩阵 Q 与上三角形矩阵 R,所以称为 QR 分解法。 2. 串

行代码描述 串行主要代码如下: #include <stdio.h> #include <math.h> #include <stdlib.h> #include <time.h> #define n 100 //maxN void Matrix_print(double A[n][n]) { for (int i=0;i<n;i++) { for (int j=0;j<n;j++) printf("%8.4lf\t",A[i][j]); printf("\n"); } } double Matrix_norm(double a[n]) { double d=0; for (int i=0;i<n;i++) d+=a[i]*a[i]; return sqrt(d); } void Matrix_multiply(double A[n][n],double B[n][n],double C[n][n]) { for (int i=0;i<n;i++) for (int j=0;j<n;j++) { C[i][j]=0; for (int t=0;t<n;t++) C[i][j]+=A[i][t]*B[t][j]; }

} void Matrix_copy(double A[n][n],double B[n][n]) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) A[i][j]=B[i][j]; } void householder_trans(double A[n][n],int k,double Q[n][n]) { double a[n]; for(int i=0;i<n-k;i++) a[i]=0; for(int i=n-k;i<n;i++) a[i]=A[i][n-k]; a[n-k]-=Matrix_norm(a); double d=Matrix_norm(a); for(int i=0;i<n;i++) a[i]=a[i]/d; double H[n][n]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) H[i][j]=-2*a[i]*a[j]; H[i][i]++; } //μ?H=I-2vvT double temp[n][n]; Matrix_multiply(H,A,temp); Matrix_copy(A,temp); Matrix_multiply(Q,H,temp); Matrix_copy(Q,temp); } void Matrix_input(double A[n][n]) { srand( (unsigned)time( NULL ) ); for(int i=0 ;i<n;i++) for(int j=0;j<n;j++) { /*printf("a[%d][%d]=",i,j); scanf("%lf",&A[i][j]);*/ A[i][j] = rand(); } } void main()

{ double Q[n][n]; double A[n][n]; Matrix_input(A); printf("A: \n"); Matrix_print(A); for (int i=0;i<n;i++) { for (int j=0;j<n;j++) Q[i][j]=0; Q[i][i]=1; } clock_t start = clock(); for (int i=n;i>=2;i--) householder_trans(A,i,Q); clock_t end = clock(); printf("\n\nR: \n"); Matrix_print(A); printf("Q: \n"); Matrix_print(Q); printf("串行时间 time=%.0f ms",double(end - start)); system("pause"); } 3. 并行化设计思路 a. 将有 for 循环且没有数据关系、计算量大的计算进行并行优化; b. 将毫不相关且可独立运行的代码块进行并行优化; c. 程序主要优化是对 householder 变换里的乘法和矩阵赋值进行优化。 4. 并行代码描述 #include <stdio.h> #include <math.h> #include <stdlib.h> #include <omp.h> #include <time.h> #define n 4 //maxN void Matrix_print(double A[n][n]) { for (int i=0;i<n;i++) { for (int j=0;j<n;j++) printf("%8.4lf\t",A[i][j]); printf("\n"); } }

void Matrix_input(double A[n][n]) { srand(unsigned(time(NULL))); for(int i=0 ;i<n;i++) for(int j=0;j<n;j++) { A[i][j] = rand(); } /*for(int i=0 ;i<n;i++) for(int j=0;j<n;j++) { printf("a[%d][%d]=",i,j); scanf("%f",&a[i][j]); }*/ } double Matrix_norm(double a[n]) { double d=0; #pragma omp parallel for num_threads(2) reduction(+:d) for (int i=0;i<n;i++) d+=a[i]*a[i]; return sqrt(d); } void Matrix_multiply(double A[n][n],double B[n][n],double C[n][n]) { int border = n*n; int i,j; #pragma omp parallel for num_threads(2) for (int index = 0; index < border; index++) { i = index/n; j = index%n; C[i][j]=0; for (int t=0;t<n;t++) C[i][j]+=A[i][t]*B[t][j]; } } void Matrix_copy(double A[n][n],double B[n][n]) { int i,j; int border = n*n; #pragma omp parallel for num_threads(2)

for (int index = 0; index < border; index++) { i = index/n; j = index%n; A[i][j]=B[i][j]; } } void householder_trans(double A[n][n],int k,double Q[n][n]) { double a[n]; #pragma omp parallel num_threads(2) { #pragma omp for for(int i=0;i<n-k;i++) a[i]=0; #pragma omp for for(int i=n-k;i<n;i++) a[i]=A[i][n-k]; } a[n-k]-=Matrix_norm(a); double d=Matrix_norm(a); #pragma omp parallel for num_threads(2) for(int i=0;i<n;i++) a[i]=a[i]/d; double H[n][n]; int border = n*n; int i,j; #pragma omp parallel for num_threads(2) for (int index = 0; index < border; index ++) { i = index/n; j = index%n; H[i][j] = -2*a[i]*a[j]; if (j == n-1) { H[i][i]++; } } double temp[n][n]; #pragma omp parallel sections private(temp) num_threads(2) { #pragma omp section

{ Matrix_multiply(H,A,temp); Matrix_copy(A,temp); } #pragma omp section { Matrix_multiply(Q,H,temp); Matrix_copy(Q,temp); } } } int main() { double Q[n][n]; double A[n][n]; Matrix_input(A); //printf("A: \n"); //Matrix_print(A); int border = n*n; int i,j; #pragma omp parallel for num_threads(2) for (int index = 0; index < border; index ++) { i = index/n; j = index%n; Q[i][j] = 0; if (j == n-1) { Q[i][i] = 1; } } clock_t start = clock(); for (int i=n;i>=2;i--) householder_trans(A,i,Q); clock_t end = clock(); double time = (double)end - start; printf("串行结果\nR: \n"); Matrix_print(A); printf("Q: \n"); Matrix_print(Q); printf("\n 并行时间:time = %.0f ms",time); system("pause"); return 0; }

5. 实验结果分析 1) 测试平台描述 系统:Windows 7 旗舰版 编译器:Visual Studio 2012 内存:4G CPU:AMD A6-4400M APU with Radeon(tm) HD 双核 2) 测试结果描述 (串行运行时间、并行运行时间) 数据量 80 100 120 140 160 串行时间(ms) 562 1310 2543 4992 9329 并行时间(ms) 515 1186 2153 3978 7285 加速比 1.091 1.105 1.181 1.255 1.281

3) 加速比分析 加速比=1/5(1.091+1.105+1.181+1.255+1.281) =1.1826


相关文章:
QR分解 实验报告
QR分解 实验报告_建筑/土木_工程科技_专业资料。QR分解,用C++语言实现,报告中包含QR分解的串行源码,也包含OpenMP的并行源码并行计算课程考核 实验报告考核题目:QR ...
数值与符号计算 LU和QR分解实验报告
撰写详细的实验报告 ii. 不必修改函数界面 iii. 用高斯列选主元消去法和矩阵 QR 分解两种方法求解下面 3 个方程组,比较这两种 方法的误差。 三、 实验算法...
数值与符号计算__LU和QR分解实验报告
矩阵的 QR 分解 bool hshld(double const*qr, double const*d, double*b, int n); 求线性代数方程 组的解 2 实验要求撰写详细的实验报告 不必修改函数界面 ...
QR分解的数值效果报告
§ 7.参考文献与附注……….20 2 QR 分解数值效果分析报告基于数值试验的 gram-schmit 方法,modified gram-schmit 方法,householder 变换,givens 变换计 算矩阵 Q...
实验三 矩阵的QR分解
实验三 1、原理 矩阵的 QR 分解 矩阵 QR 分解是一种特殊的三角分解,在解决矩阵特征值的计算、最小二乘法等问题中 起到重要作用。 ×设 A∈Cm n, m≥n ...
实验五 矩阵运算、分解和特征值
2.矩阵的 LU、QR 和 Cholesky 分解。3.矩阵的特征向量和特征值。 ? 1 ? ...V 称为奇异值分解三元组 心得 体会注:实验报告用 A4 纸双面打印,篇幅不要...
数学模型实验报告模板五矩阵运算、分解和特征值
数学模型实验报告模板五矩阵运算、分解和特征值_理学_高等教育_教育专区。矩阵...[Q,R]=qr(A) Q =-0.0776 -0.8331 0.5456 -0.0478 -0.3105 -...
matlab实验报告
matlab实验报告_理学_高等教育_教育专区。MATLAB 实验报告 1、在区间[-1,1]上...用基本 QR 算法求全部特征值(可用 MATLAB 函数“qr”实现矩阵的 QR 分解). ...
消元法实验报告13
LU和QR分解法解线性方程组 15页 2财富值 matlab实用程序百例-数值分... 31页 免费 高斯消元法MATLAB实现 5页 免费 消元法实验报告8 10页 免费如要投诉违规...
数值分析期末实验报告
数值分析期末实验报告_理学_高等教育_教育专区。数值分析期末实验报告:线性方程组...(householder 矩阵,反幂法,幂法,QR 分解) ;函数的插值方法(三次样条 插值,...
更多相关标签:
过氧化氢分解实验报告 | cholesky分解实验报告 | 功能分解法实验报告 | qr分解 | 矩阵的qr分解 | 矩阵qr分解 | matlab qr分解 | qr分解算法 |