矩阵计算复杂度（简洁版）(Computational complexity of matrix)-Toy模板网

这篇具有很好参考价值的文章主要介绍了矩阵计算复杂度（简洁版）(Computational complexity of matrix)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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 , and invertible matrix . Then we have following computational complexity ：

(1) ;

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

(3) ;

II、 Analysis and proof

2.1 Definition

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

2.2 Analysis

For model (1): Since is a n rows and n column and is n rows and m column, then there is times to multiply, i.e., .

For model (2): Similar reason as (1) enable us to get there is times plus times to multiply, i.e., $矩阵计算复杂度（简洁版）(Computational complexity of matrix)$ .

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

Hence we only need to consider how many times multiplication in the process of elementary row transforms. By easy calculation, we get $矩阵计算复杂度（简洁版）(Computational complexity of matrix)$ .

III、 CODE

I omit the code for model(1) and model(2) as it is too easy. 文章来源地址https://www.toymoban.com/news/detail-412155.html

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)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！