矩阵计算复杂度（简洁版）(Computational complexity of matrix)

您所在的位置：网站首页 › 稀疏矩阵求逆复杂度 › 矩阵计算复杂度（简洁版）(Computational complexity of matrix)

矩阵计算复杂度（简洁版）(Computational complexity of matrix)

2024-03-30 02:31| 来源: 网络整理| 查看: 265

This blog mainly focuses on the complexity of matrix calculation. I will introduce this topic in three parts: main results, analysis, and proof, code.

I、 Results

Let $B\in{\mathbb R}^{n\times m}$ , $C\in{\mathbb R}^{m\times l}$ and invertible matrix $A\in{\mathbb R}^{n\times n}$ . Then we have following computational complexity $\Theta$ ：

(1) $\Theta(AB)=O(mn^2)$ ;

(2) $\Theta(ABC)=O(mn^2)+O(mnl)$ ;

(3) $\Theta(A^{-1})=O(n^3)$ ;

II、 Analysis and proof 2.1 Definition

The usual computation for integer multiplication has a complexity of $O(n^2)$ . This means that there is a constant $\eta$ such that the multiplication of two integers of at most n digits may be done in a time less than $\eta n^2$ .

2.2 Analysis

For model (1): Since $A$ is a n rows and n column and $B$ is n rows and m column, then there is $n\times m \times n$ times to multiply $A B$ , i.e., $O(mn^2)$ .

For model (2): Similar reason as (1) enable us to get there is $n\times m \times n$ times plus $m\times l \times n$ times to multiply $A B$ , i.e., $O(mn^2)+O(mnl)$ .

For model (3): Based on $PA = E$ , we can get invertible matrix through elementary row transform, i.e.,

$[E; A] = [A^{-1}; E]$ .

Hence we only need to consider how many times multiplication in the process of elementary row transforms. By easy calculation, we get $n\times n+ (n-1)\times n + ...+1\times n +n = \frac{(1+n)n}{2}n+n=\frac{1}{2}n^3+\frac{3}{2}n = O(n^3)$ .

III、 CODE

I omit the code for model(1) and model(2) as it is too easy.

code idea for model(3) :（Gaussian Elimination） # input an invertible matrix A # Suppose a ideal condition: no row transform import sys class MatrixInverse: def __init__(self, matrix): self.matrix = matrix self.a = len(self.matrix) self.b = len(self.matrix[0]) if self.a != self.b: print("This is a vertible matrix") def judge(self): c = 1 e = 0 m = self.matrix for i in range(self.a): for j in range(self.a): c = c * m[j % self.a][(i + j) % self.a] # print(f"{j % self.a},{(i + j) % self.a}") e = e + c c = 1 for i in range(self.a): for j, k in zip(range(0, self.a*2, 2), range(self.a)): c = c * m[k % self.a][(i + j) % self.a] # print(f"{k % self.a},{(i + j) % self.a}") e = e - c c = 1 print(f"该矩阵的值为：{e}", end=",") if e != 0: print("Exist invertible matrix。") else: print("No invertible matrix。") return e def calculate(self): """Use basic row change mathod""" if MatrixInverse.judge(self) == 0: sys.exit() d = [[0 for i in range(self.a*2)] for j in range(self.a)] e = [[0 for i in range(self.a)] for j in range(self.a)] for i, j in zip(range(self.a), range(self.a)): e[i][j] = 1 for i in range(self.a): for j in range(self.a): d[i][j] = self.matrix[i][j] for i in range(self.a): for j in range(self.a, self.a*2): d[i][j] = e[i][j-self.a] """Choose pivot again""" m1 = [] for i in range(self.a): m1.append(i) for i in range(self.a): m = 0 while m < self.a: # choose a suitable pivot if d[m][i] != 0 and i < self.a and m in m1: c2 = d[m][i] # c2 is pivot, m is row，i is column。 for x in range(self.a*2): # let pivot be 1 d[m][x] = d[m][x]/c2 # for j in range(self.a): # divide by pivot row c3 = d[j][i] for k in range(self.a*2): if j != m: d[j][k] = d[j][k]/c3 - d[m][k] m1.remove(m) m = self.a # this column finished next column else: m += 1 for i in range(self.a): for j in range(self.a): if d[i][j] != 0: c5 = d[i][j] for k in range(self.a*2): d[i][k] = d[i][k]/c5 """Save invertible matrxi into d2""" d2 = [[0 for i in range(self.a)] for j in range(self.a)] for i in range(self.a): for j in range(self.a, self.a*2): d2[i][j-self.a] = float('%.2f' % d[i][j]) print("The invertible matrix of A is：") print(d2) n = [[1, 2, 3], [2, 1, 3], [3, 4, 3]] s = MatrixInverse(n) s.calculate()

【本文地址】

矩阵计算复杂度（简洁版）(Computational complexity of matrix)

矩阵计算复杂度（简洁版）(Computational complexity of matrix)

今日新闻

推荐新闻