Real and complex matrices and their various operations implemented in C language

I. Introduction

I recently worked as an intern in a company and spent three weeks working on an indoor positioning algorithm (rudimentary, not yet optimized) to realize the joint writing and debugging of matlab and C. The author believes that the difficulty lies in the various operations of the matrix. In C++ There is Eigen library available. Eigen, which was used under Ubuntu for a period of time when learning slam and doing projects, is powerful and provides various typical matrix computing interfaces, but in C, we need to write each function module by ourselves. The core code of the algorithm, matlab, has only about 100 lines (here, let me sigh again that matlab is really born for matrix calculation, and it is powerful against the sky), but I wrote about 1500 lines in C. I would like to use this serialized document to record the key to algorithm development – ​​the implementation of complex matrix operations.
There are many demo s on the Internet about the implementation of matrix operations in C language, but they are generally not complete and accurate. Many function s directly git down various problems, and there is no unified standard for use. In addition, they are only discussed in the real number field (Double), but We know that in the field of algorithms, many matrix operations involve Complex operations, and the matrix operations in the Complex field are actually quite different from the real field (PS: This is also a pit I encountered when writing C programs. will be introduced one by one).
Therefore, in this serial article, I will completely use C language to complete the basic functions of matrix definition, memory initialization, access index, memory destruction, and more importantly, write the calculation of the cofactor, determinant, inverse matrix, coordinator Variance matrix, eigenvalues, eigenvectors and other functional functions. I have taken out all the function demos and explained them carefully, combined with matlab, programming comparison to verify the correctness of the demos, you can read and use them with confidence.

2. Knowledge Reserve and Programming Tools

   1. Knowledge reserve: skilled C Language, proficient in pointers, arrays, etc. C Language "soul" knowledge;
   2. IDE tool: Visual Studio2019Community; MATLAB2019a;
   3. C Relevant header files: complex library

3. Definition of Matrix

I noticed that some friends in the community use a two-dimensional array to define a matrix, but the matrix is ​​not always two-dimensional. In matlab, the matrix can be N-dimensional. If you try to use a higher-dimensional array to complete the definition, in Subsequent accesses to matrix/array cells are very redundant. Although C is a structured programming language, a certain "robustness" is also required. In addition, I mostly use C++ and matlab, so I always have a certain C++ idea when programming. The latter is object-oriented, with class templates and template functions.
PS: In the code posted later, I will give two demo s of Double and Complex respectively, as well as the description of the related function interface of the complex library file called.

1. Header file

	 # include <complex.h>  // Complex Numbers
	 # include <stdlib.h>   // malloc/free, et.al

illustrate:
Regarding the plural header files, C11 began to provide a large number of function interfaces. Here I will only talk about the ones that are used. If you are interested, you can click on the open source file to see what is there. The first is the definition, the source file is as follows:

	#ifndef _C_COMPLEX_T
    	#define _C_COMPLEX_T
    	typedef struct _C_double_complex
    	{
       	 double _Val[2];
    	} _C_double_complex;  // This is what I need

   	 typedef struct _C_float_complex
    	{
        	float _Val[2];
    	} _C_float_complex;

    	typedef struct _C_ldouble_complex
    	{
        	long double _Val[2];
    	} _C_ldouble_complex;
	#endif

	typedef _C_double_complex  _Dcomplex;  // This is what I need
	typedef _C_float_complex   _Fcomplex;
	typedef _C_ldouble_complex _Lcomplex;

In short, the complex.h header file represents a complex number by defining a structure. Specifically, the internal member of the structure is a one-dimensional array, which stores two data, and the array stores the real part (real) and the imaginary part (imaginary) of the complex number. There are three kinds of arrays, which are double, float, and long double. Three types of structures are defined correspondingly, and three functions are defined corresponding to each function. Remember that these three general types refer to the data types of the real and imaginary parts of complex numbers. In the algorithm, I use the double type. So I only call the functions related to the double type in the complex.h header file when it comes to complex number operations.

2. Definition

Here I use a structure to complete the definition and "simulation" of the matrix.

	typedef _Dcomplex ComplexType;   // Complex Variables
	typedef double DoubleType;       // Double Variables

	/* Complex Cell */
	typedef struct   // Matrix Structor
	{
		int row, column;  // Size
		ComplexType* arrayComplex;     // Pointer to Cell
	}Matrix;

	/* Double Cell */
	typedef struct
	{
		int row, column;
		DoubleType* arrayDouble;
	}Matrix2Double;
	/* bool */
	typedef enum 
	{ 
		False = 0, True = 1 
	}Bool;

illustrate:
(1) Although the complex.h header file has taken the alias _Dcomplex for the complex type _C_double_complex, in order to distinguish double and complex, I have taken an alias for the two again, following the Google naming rules, and then define the two matrix The structure type is the same as the enumeration type of the bool variable;
(2) Here comes the point, for two matrices of different element types, I have defined two structures, one is that the cell is a real type, and the other is a complex type. The two members of type int inside the structure represent the number of rows (row) and the number of columns (column) of the matrix. The pointer member is used to point to a piece of memory that stores elements/cells, so the matrix cells can use pointers To access and traverse, at this time, the internal data structure pointer is 1D, but it can represent 2D and above matrices. From here, we can see the advantages of pointers instead of arrays;
(3) Finally, the author also defines an enumeration type, which is useful for subsequent functions used for security mechanisms;
(4) It can be seen that the structures of two different types of matrices are actually the same, but the types of internal pointer variables are different.

3. Initialize memory allocation

The first is to write a function that initializes a complex number, because a complex number is also a structure. When defining a complex variable, it is best to initialize it as well. In addition, the subsequent accumulation and multiplication of complex numbers are involved, so they also need to be assigned and initialized:

	/* Initiation of Complex Number */
	void InitComplex(ComplexType* Complex)  // Transfer of Pointer
	{
		Complex->_Val[0] = 0.0;
		Complex->_Val[1] = 0.0;

	}

Then initialize the matrix:

	/* Initiation of Complex Matrix */
	void InitComplexMatrix(Matrix* matrix, int row, int column)  // Transmiss of Pointer
	{
		int size = row * column * sizeof(ComplexType);
		if (size <= 0)
		{
			puts("ERROE: An invalid matrix!\n");
			return;
		}
		matrix->arrayComplex = (ComplexType*)malloc(size); 			// initiate pointer
		if(matrix->arrayComplex)
		{
			matrix->row = row;                           			 //  initiate row and size
			matrix->column = column;
			for (int index = 0; index < row * column; index++)       //  initiate cell
			{
				InitComplex(matrix->arrayComplex + index);  // call InitComplex() function
			}
		}
	}
	

	/* Initiation of Double Matrix */
	void InitDoubleMatrix(Matrix2Double* matrix, int row, int column)
	{
		int size = row * column * sizeof(DoubleType);
		if (size <= 0)
		{
			puts("ERROE: An invalid matrix!\n");
			return;
		}
		matrix->arrayDouble = (DoubleType*)malloc(size);
		if (matrix->arrayDouble)
		{
			matrix->row = row;
			matrix->column = column;
			for (int row_i = 0; row_i < row; ++row_i)
			{
				for (int column_j = 0; column_j < column; ++column_j)
				{
					matrix->arrayDouble[row_i * matrix->column + column_j] = 0.0;
				}
			}

		}	
	}

illustrate:
(1) Matrix initialization involves determining the size of the matrix row/column and initializing the cells, that is, initializing and assigning structure variables. The core is to dynamically apply for a piece of memory for the pointer, using the malloc() function, which is included in the header. In the file stdlib.h;
(2) Use pointers to access/traverse (iteration) matrix cells, which is actually the number stored in each cell pointed to by the pointer. In the initial cell link, there are actually three representations, mainly pointer access elements and matrix access elements. cells in different ways. When accessing elements/cells later, I randomly choose one to write (sorry, these were not the focus when I was writing code, so I thought of which one to write), but in order to avoid confusion for readers, here, the author gives come out:

	// Solution_1
	for (int index = 0; index < row * column; index++)       //  initiate cell
	{
		InitComplex(matrix->arrayComplex + index);
	}
	// Solution_2
	for (int index = 0; index < row * column; index++)
	{
		InitComplex(&(matrix->arrayComplex[index]));
	}
	// Solution_3
	for (int row_i = 0; row_i < row; ++row_i)
	{
		for (int column_j = 0; column_j < column; ++column_j)
		{
			InitComplex(matrix->arrayComplex + row_i * matrix->column + column_j);
		}
	}

(3) In addition, for the sake of safety, I also added two if statements, which can further reduce various memory bug s and exception s such as stack overflow in the final compilation, such as free ing the memory that no longer exists or the memory that malloc fails, That is, the wild pointer and heap errors that occur when using pointers in the C language;
(4) The matrix of the double type is similar to the complex type, and it is even simpler to initialize the value, because each double cell has only one element, and the complex has two real and imaginary parts.

4. Memory destruction

We know that in Linux, the malloc() and free() system functions always appear in pairs, and a memory application must be freed. Also in VS, after defining a matrix with a structure variable, call malloc( ) function applies for a piece of memory, so it needs to be released:

	/* Validity of Complex Matrix */
	Bool IsNullComplexMatrix(const Matrix* matrix)
	{
		int size = matrix->row * matrix->column;

		if (size <= 0 || matrix->arrayComplex == NULL)
		{
			return True;
		}
		return False;
	}	
	/* Free Memory of Complex Matrix */
	void DestroyComplexMatrix(Matrix* matrix)
	{
		if (!IsNullComplexMatrix(matrix))    // Nested Call of IsNullComplexMatrix()
		{
			free(matrix->arrayComplex);      // Pair: malloc--free
			matrix->arrayComplex = NULL;
		}
		matrix->row = matrix->column = 0;
	}
	
	
	/* Validity of Double Matrix */
	Bool IsNullDoubleMatrix(const Matrix2Double* matrix)
	{
		int size = matrix->row * matrix->column;

		if (size <= 0 || matrix->arrayDouble == NULL)
		{
			return True;
		}
		return False;
	}
	/* Free Memory of Double Matrix */
	void DestroyDoubleMatrix(Matrix2Double* matrix)
	{
		if (!IsNullDoubleMatrix(matrix))
		{
			free(matrix->arrayDouble); 
			matrix->arrayDouble = NULL;
		}
		matrix->row = matrix->column = 0;
	}

illustrate:
(1) First, define an IsNullComplexMatrix() function to judge whether the matrix is ​​initialized successfully, mainly to judge whether the member inside the structure is successfully initialized (reflected in the matrix, that is, the number of rows and columns and memory). It is an operation that guarantees memory safety. See, here I call the Bool enumeration type member mentioned above;
(2) After that, define a DestroyComplexMatrix() function to release the member inside the structure, that is, to call free() nested to release the memory pointed to by the pointer member, and set it to NULL (although this step is not necessary, the author recommends that readers every time Add both times), and then set the member variables of the two other int types to 0;
(3) Regarding the double type, it is also given and will not be repeated.
(4) In addition, in my algorithm framework, a large number of matrix definitions have appeared, that is, multiple memory applications and releases, and even more than 20 matrices have appeared in several core algorithm functions. If Calling the initialization and destruction functions once for each matrix will seriously affect the beauty and efficiency of programming. Therefore, I wrote several initialization (initiate) and memory (destroy) functions, the purpose of which is to call only one function at a time to apply and release all the matrices I need. Of course, this function can only be used in my specific algorithm scenario, so I just made a supplementary expansion and posted it. In addition, I only give the memory destruction function, and I will write demo s in turn to verify this function:

	/* Free Memory of Complex Matrice Array */
	void DestroyComplexMatrixArray(Matrix matrixArray[], int num)  // Array Transfer--->Pointer Transfer
	{
		if (num)      // if no matrix
		{
			for (int i = 0; i < num; i++)
			{
				DestroyComplexMatrix(&matrixArray[i]);  // Nested Call of DestroyComplexMatrix()
			}
		}
	}


	/* Free Memory of Double Matrice Array */
	void DestroyDoubleMatrixArray(Matrix2Double* matrixArray, int num)
	{
		if (num)  // if no cell
		{
			for (int i = 0; i < num; i++)
			{
				DestroyDoubleMatrix(&matrixArray[i]);
			}
		}
	}

5. Get the number of rows, columns and cells of the matrix

Here I also define three functions to return the corresponding values:

/* Return Matrix Row Size */
int MatrixRow(const Matrix* matrix)
{
	return matrix->row;
}
/* Return Matrix Column Size */
int MatrixColumn(const Matrix* matrix)
{
	return matrix->column;
}
/* Return Complex Matrix Size */
int MatrixSize(const Matrix* matrix)
{
	return MatrixRow(matrix) * MatrixColumn(matrix) ;   // Size Refers to Numbers of Cell of Matrix
}

illustrate:
(1) Since the structure of the matrix here is used by the author to achieve ~~"simulation"~~, in order to make the matrix look "more like" the "format" in our mathematics, mathematical aesthetics should be implemented by computer, or defined The relevant function is used to return the quantity we want, so in fact, it can be directly obtained directly in the following format:

matrix->row;
matrix->column;
matrix->row * matrix->column;

4. Summary

This is the content of the first chapter. On the whole, it is only to complete the definition, initialization, memory destruction, etc. of the matrix, but it is very important, because all subsequent matrix operation functions and interfaces are based on this. In fact, I encountered Many problems arise in this part. In order to facilitate readers to read later, or to help readers clear mines when programming, the author summarizes personal programming habits and the pits encountered in this part:

  1. Try to write void-type functions, avoid defining local variable s, that is, local matrices, within functions, and frequently call initialization and destruction functions, resulting in frequent application and release of computer memory;
  2. Function parameters should be defined as pointer types as much as possible, especially matrix/structure variables, because they are void functions and have no return value.
  3. When calling a function, try to define the actual parameters as general variables, especially matrix/structure variables, so as to avoid the need to allocate and release memory for the structure pointer variable itself. Regarding this point, because the author has not much experience in programming in C language, Therefore, the actual parameters were all defined as pointers at that time, resulting in a large number of structure pointer initialization and structure internal pointer initialization operations in each function. After there are too many matrices, it will be very confusing. If the allocation and release are not timely, it will be Caused various cast exception s during compilation, which was the first big pit I encountered at the time;
  4. In the next chapter I will detail the functions for matrix operations on the real and complex fields.

Tags: C Algorithm pointer matrix

Posted by manchuwok on Sun, 22 May 2022 14:49:52 +0300