Complexity analysis of matrix inversion operation (complexity analysis of inverse matrix)

Complexity analysis of matrix inversion operation
Complexity analysis of inverse matrix

1 background

I wrote an article about matrix complexity analysis before , I didn't expect so many readers . about IT For those concerned , Combine the basic mathematical knowledge from the code level , We can well understand how the complexity of the matrix is calculated and analyzed . One of the readers suggested “ How to analyze the complexity of matrix inversion ”. Let's discuss it together today , I know , There are many ways to find the inverse of a matrix , Here is the most basic way , Other optimization methods , After reading this blog , Self analysis , Because the principle is basically not much different . This blog is just a guide .

2 Analysis of inverse operation

2.1 The basic principle of finding inverse matrix

Many readers here can easily ignore , Just to review .
$$(A|E)=(E|A^{-1})$$
I believe you are familiar with this formula , That is, after the original matrix is aligned with an identity matrix , Make row and column changes , We get the identity matrix , The right part is the inverse matrix .

Prove the following ：
$$A^{-1}(A|E)=(A^{-1}A|A^{-1}E)$$
$$=(E|A^{-1})$$
Think about why ？

because ：
$$A^{-1}A=E$$, Take the right $$A^{-1}$$ after ：
$$A^{-1}E=A^{-1}$$

So the bridge of change is existence $$A^{-1}$$

3 Inverse matrix complexity analysis - Gauss elimination

3.1 Code level

/*  Function description ： Primitive matrix a And an identity matrix E Make a large matrix (A,E),  Use elementary transformation to transform a become E, You will get (E,A^{-1}) In the form of  * */
void inverseMatrix(double arc[d][d], int n, double ans[d][d])// Calculate the inverse of the matrix 
{
    
    /* d = n :  Represent dimension  arc[d][d] :  Original matrix ,dxd ans[d][d] :  The changed result matrix ,dxd , Initially initialized to the identity matrix  */
    
	int i, j, k;// Column 
	double max, tempA, tempB, P;
	int max_num;
	double arcCopy[d][d];
	memcpy(arcCopy, arc, 288);
	for (i = 0; i < n; i++)
	{
    
		ans[i][i] = 1;
	}
	for (i = 0; i < n; i++)// The first i Column 
	{
    
		max = fabs(arcCopy[i][i]);
		max_num = i;
		for (j = i + 1; j < n; j++)// Select principal element 
		{
    
			if (fabs(arcCopy[j][i]) > max)
			{
    
				max = fabs(arcCopy[j][i]);
				max_num = j;
			}
		}

		for (k = 0; k < n; k++)// Exchange line 
		{
    
			tempA = arcCopy[i][k];
			arcCopy[i][k] = arcCopy[max_num][k];
			arcCopy[max_num][k] = tempA;
			tempB = ans[i][k];
			ans[i][k] = ans[max_num][k];
			ans[max_num][k] = tempB;
		}
		for (k = i + 1; k < n; k++)
		{
    
			P = arcCopy[k][i] / arcCopy[i][i];
			for (j = 0; j < n; j++)
			{
    
				arcCopy[k][j] = arcCopy[k][j] - arcCopy[i][j] * P;
				ans[k][j] = ans[k][j] - ans[i][j] * P;
			}
		}
	}
	for (i = 0; i < n; i++)// That's ok 
	{
    
		P = arcCopy[i][i];
		for (j = i; j < n; j++)
		{
    
			arcCopy[i][j] = arcCopy[i][j] / P;
		}
		for (j = 0; j < n; j++)
		{
    
			ans[i][j] = ans[i][j] / P;
		}
	}
	for (i = n - 1; i > 0; i--)
	{
    
		for (j = i - 1; j >= 0; j--)
		{
    
			for (k = 0; k < n; k++)
			{
    
				ans[j][k] = ans[j][k] - ans[i][k] * arcCopy[j][i];
			}
		}
	}
}

3.2 result

The time complexity of the inverse matrix is ：O(n^3)

The biggest cost is here ,

	for (i = n - 1; i > 0; i--)
	{
    
		for (j = i - 1; j >= 0; j--)
		{
    
			for (k = 0; k < n; k++)
			{
    
				ans[j][k] = ans[j][k] - ans[i][k] * arcCopy[j][i];
			}
		}
	}

4 Inverse matrix complexity analysis - Adjoint matrix

This is more direct ：
$$A^{-1}=A^{\ast }/det(A)$$
namely To calculate A The adjoint matrix of , Calculate again A The determinant value of .
The former The complexity of is ：$$N\ast O(N!)$$
The complexity of the latter is ：$$N^2\ast O((N-1)!)$$

Therefore, the complexity of solving the adjoint matrix is ：
$$N\ast O(N!)+N^2\ast O((N-1)!)$$

ps： This blog only considers the basic operation , Do not consider optimization