C代写：CS140 Matrix-Vector Multiplication

发表于 | 分类于
本题需要求解矩阵的最大特征值

Introduction

Matrix和Vector是Linear algebra中最基础的概念。而利用计算机求解数学问题，是一种常见的做法。

将数学公式、定理用计算机编程实现，看起来并不是一件难事，但是对于某些算法，在不考虑时间复杂度的情况下，编写出来的代码运行效率将极其低下。尤其是I/O操作和循环结合的地方，在数据量大的情况下，往往不能快速地得到答案。因此在求解问题的过程中，对于原数学公式、定理的简化与改写，是很有必要的。

而本次需求需要在给定的时间复杂度条件下，求解一些基本的线性代数的问题。

Requirement

This request is to write a parallel program to multiply a matrix by a vector, and to use this routine in an implementation of the power method to find the absolute value of the largest eigenvalue of the matrix. You will write separate functions to generate the matrix and to perform the power method, and you will do some timing experiments with the power method routine.

Analysis

本题需要求解absolute value of the largest eigenvalue of the matrix，也就是矩阵的最大特征值。对于矩阵特征值的理解，请参考如何理解矩阵特征值？

Tips

本题需要求解的其中一个矩阵为

1
2
3
4
5
6
7
1 1 1 1 1 1 1
0 2 2 2 2 2 2
0 0 3 3 3 3 3
0 0 0 4 4 4 4
0 0 0 0 5 5 5
0 0 0 0 0 6 6
0 0 0 0 0 0 7

通过观察，上面的矩阵是一个上三角矩阵。而三角矩阵的特征值就是对角线上的各个元素。

因此我们需要编程判断，一个矩阵是否是三角矩阵，如果是，则取其对角线上的元素，作为矩阵的特征值。

下面给出判断一个矩阵是否是上三角矩阵的代码

1
2
3
4
5
6
7
8
9
10
11
int is_upper_triangular_matrix(int **matrix, int n) {
  int i, j;
  for (i = 0; i < n - 1; i++) {
    for (j = 0; j < i; j++) {
      if (matrix[i][j] != 0) {
        return 0;
      }
    }
  }
  return 1;
}