Matrix Determinant

This is a discussion on Matrix Determinant within the C Programming forums, part of the General Programming Boards category; Ok, so I'm trying to work with C structures here. I'm supposed to recursively calculate the determinant of a matrix ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    24

    Matrix Determinant

    Ok, so I'm trying to work with C structures here.

    I'm supposed to recursively calculate the determinant of a matrix using a tree of processes. I'm wanting to use a structure to define each element of the matrix (which is a dynamically allocated array of 'elements'), but I keep running into syntax errors.

    I finally got the syntax clear, tried to compile, and...

    I have a lot of problems (coming back from my header file in particular), but I think I'm probably just setting the structure up wrong all over.

    I don't expect any of the process stuff to be correct right now, but I'd like to figure out what I'm doing wrong with handling structures. If anyone can help I'd appreciate it a lot:


    main
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<sys/types.h>
    #include<sys/wait.h>
    #include"determ.h"
    
    // DEFINE MATRIX ELEMENT //
    typedef struct matrix_element
    {
    	int value, row, column;
    
    }element;
    
    int main (int argc, char *argv[])
    {
    	// VARIABLES //
    	int size, levels;
    	element *matrix = NULL;
    	int i= 0;
    	int j= 0;
    	int determinant;
    	
    	if( argc != 4 ) //Check for correct number of arguments
    	{
    		printf("ERROR: Invalid number of arguments.\n", argc);
    		return 0;
    	}
    
    	else
    	{	
    		// MATRIX ATTRIBUTES //
    		size= atoi(argv[2]); //Set size 
    		levels= atoi(argv[3]); //Set levels
    
    		// CREATE MATRIX //
    		element* matrix = (element *)malloc( size*size*sizeof(element) ); //Allocate memory for matrix
    		fillMatrix(argv[1], matrix, size); //Read numbers for matrix
    		
    		// CALCULATE DETERMINATE //
    		pid_t pid;
    		int pd[2];
    		int buffer;
    		int wait_= 0;
    		int sum;
    
    		for( i= size; i> 0; i--)
    		{
    			pipe(pd);
    			pid= fork();
    
    			//Child
    			if(pid == 0)
    			{
    				for( j= 0; j= levels; j++)
    				{
    					close(pd[0]); //Close read pipe
    					buffer += calcDET(matrix, size);
    					write(pd[1], &buffer, sizeof(int));
    				}
    			}
    
    			//Parent
    			else
    			{
    				wait(0);
    				close(fd[1]); //Close write pipe
    				read(fd[0], &determinant, sizeof(int));	
    
     				sum += determinant;
    			}
    
    		}
    
    		printf("\n\nThe determinant of this matrix is: %d \n\n\n", sum);
    		
    	}
    
    	return 0;
    }

    header
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<sys/types.h>
    #include<sys/wait.h>
    #include"determ.h"
    
    typedef struct matrix_element
    {
    	int value, row, column;
    
    }element;
    
    //Reads file into matrix
    void fillMatrix(const char *text, element* matrix, int size);
    
    //Calculates sub matrix
    element* getSUB(element* matrix, int size, int row, int col);
    
    //Finds determinate
    int buildDET(element* matrix, int size);
    
    //Gathers determinate
    int calcDET(element* matrix, int size);

    functions
    Code:
    #include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    #include<unistd.h>
    #include<sys/types.h>
    #include<sys/wait.h>
    
    #define true 1
    #define false 0
    
    typedef struct matrix_element
    {
    	int value, row, column;
    
    }element;
    
    //FUNCTION: fillMatrix()
    void fillMatrix(const char *txt_file, element* matrix, int size)
    {
    
    	FILE *numbers = NULL;
    	int scan;
    
    	//Open file
    	numbers = fopen(txt_file, "r");
    
    	if( numbers == NULL )
    	{
    		printf("ERROR: Failed to open file.");
    
    		exit(0);
    	}
    
    	else 
    	{
    		int r= 1;
    		int c= 1;
    		int i= 0;
    		//Fill matrix with numbers from file
    		while( ( fscanf(numbers, "%d", scan) ) != EOF )
    		{
    			matrix[i].column = c;
    			matrix[i].row = r;
    			matrix[i].value = scan;
    			i++;
    			c++;
    			if( c % size == 0)
    			{
    				r++;
    				c= 1;
    			}
    		}
    
    		fclose(numbers);
    	}
    
    }
    //
    
    //FUNCTION: getSUB
    element* getSUB(element* matrix, int size, int row, int col)
    {
    	int i, j, k= 0;
    	int nSize= size-1;
    	int scan;
    	element* subMatrix = (element *)malloc( sizeof(element)*(nSize)*(nSize) );
    
    	for( i= 0; i< size*size; i++)
    		if( (matrix[i].row != row) && (matrix[i].column != col) )
    		{
    			subMatrix[k] = matrix[i];
    			k++;
    		}
    		
    	return subMatrix;
    }
    //
    
    //FUNCTION: buildDET
    int buildDET(element* matrix, int size)
    {
    	int det;
    
    	if( size == 1 )
    	{
    		det= matrix[0].value;
    		return det;
    	}
    
    
    	else
    	{
    		buildDET( getSUB(matrix, size, matrix[size].row, matrix[size].column), size );
    	}
    }
    
    //FUNCTION: calcDET
    int calcDET(element* matrix, int size)
    {
    	int determinate;
    
    		while( size > 0 )
    		{
    				determinate = buildDET(matrix, size);
    		}
    
    	return determinate;
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,465
    Next time, please post the error messages you get that you don't understand.

    I assume the header you posted is determ.h. A header should never include itself. Also, you always want include guards for all of your header files to avoid multiple inclusion. Don't re-declare matrix_element in main, it will be included with determ.h.

    Take care of those things and you should find the error list much more manageable.

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    24
    Quote Originally Posted by anduril462 View Post
    Next time, please post the error messages you get that you don't understand.

    I assume the header you posted is determ.h. A header should never include itself. Also, you always want include guards for all of your header files to avoid multiple inclusion. Don't re-declare matrix_element in main, it will be included with determ.h.

    Take care of those things and you should find the error list much more manageable.
    Well I was mostly just trying to get past the misuse of structures so I could compile, which is exactly what your solution did for me(thank you very much).

    This project is already turned in, but I would like to fix it up some more just for personal betterment. I'll show you the output that I get now; which I have no idea how to interpret.


    main.c
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<sys/types.h>
    #include<sys/wait.h>
    #include"determ.h"
    
    
    int main (int argc, char *argv[])
    {
    	// VARIABLES //
    	int size, levels;
    	element *matrix = NULL;
    	int i= 0;
    	int j= 0;
    	int determinant;
    	
    	if( argc != 4 ) //Check for correct number of arguments
    	{
    		printf("ERROR: Invalid number of arguments.\n", argc);
    		return 0;
    	}
    
    	else
    	{	
    		// MATRIX ATTRIBUTES //
    		size= atoi(argv[2]); //Set size 
    		levels= atoi(argv[3]); //Set levels
    
    		// CREATE MATRIX //
    		element* matrix = (element *)malloc( size*size*sizeof(element) ); //Allocate memory for matrix
    		fillMatrix(argv[1], matrix, size); //Read numbers for matrix
    		
    		// CALCULATE DETERMINATE //
    		pid_t pid;
    		int pd[2];
    		int buffer;
    		int wait_= 0;
    		int sum;
    
    		for( i= size; i> 0; i--)
    		{
    			pipe(pd);
    			pid= fork();
    
    			//Child
    			if(pid == 0)
    			{
    				for( j= 0; j= levels; j++)
    				{
    					close(pd[0]); //Close read pipe
    					buffer += calcDET(matrix, size);
    					write(pd[1], &buffer, sizeof(int));
    				}
    			}
    
    			//Parent
    			else
    			{
    				close(pd[1]); //Close write pipe
    				read(pd[0], &determinant, sizeof(int));	
    
     				sum += determinant;
    			}
    
    		}
    
    		printf("\n\nThe determinant of this matrix is: %d \n\n\n", sum);
    		
    		free(matrix);
    	}
    
    
    	return 0;
    }

    determ.h
    Code:
    typedef struct matrix_element
    {
    	int value, row, column;
    
    }element;
    
    //Reads file into matrix
    void fillMatrix(const char *text, element* matrix, int size);
    
    //Calculates sub matrix
    element* getSUB(element* matrix, int size, int row, int col);
    
    //Finds determinate
    int buildDET(element* matrix, int size);
    
    //Gathers determinate
    int calcDET(element* matrix, int size);

    f_determ.c
    Code:
    #include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    #include<unistd.h>
    #include<sys/types.h>
    #include<sys/wait.h>
    #include"determ.h"
    
    #define true 1
    #define false 0
    
    
    
    //FUNCTION: fillMatrix()
    void fillMatrix(const char *txt_file, element* matrix, int size)
    {
    
    	FILE *numbers = NULL;
    	int scan;
    
    	//Open file
    	numbers = fopen(txt_file, "r");
    
    	if( numbers == NULL )
    	{
    		printf("ERROR: Failed to open file.");
    
    		exit(0);
    	}
    
    	else 
    	{
    		int r= 1;
    		int c= 1;
    		int i= 0;
    		//Fill matrix with numbers from file
    		while( ( fscanf(numbers, "%d", &scan) ) != EOF )
    		{
    			matrix[i].column = c;
    			matrix[i].row = r;
    			matrix[i].value = scan;
    			i++;
    			c++;
    			if( c % size == 0)
    			{
    				r++;
    				c= 1;
    			}
    		}
    
    		fclose(numbers);
    	}
    
    }
    //
    
    //FUNCTION: getSUB
    element* getSUB(element* matrix, int size, int row, int col)
    {
    	int i, j, k= 0;
    	int nSize= size-1;
    	int scan;
    	element* subMatrix = (element *)malloc( sizeof(element)*(nSize)*(nSize) );
    
    	for( i= 0; i< size*size; i++)
    		if( (matrix[i].row != row) && (matrix[i].column != col) )
    		{
    			subMatrix[k] = matrix[i];
    			k++;
    		}
    		
    	return subMatrix;
    }
    //
    
    //FUNCTION: buildDET
    int buildDET(element* matrix, int size)
    {
    	int det;
    
    	if( size == 1 )
    	{
    		det= matrix[0].value;
    		return det;
    	}
    
    
    	else
    	{
    		buildDET( getSUB(matrix, size, matrix[size].row, matrix[size].column), size );
    	}
    }
    
    //FUNCTION: calcDET
    int calcDET(element* matrix, int size)
    {
    	int determinate;
    
    		while( size > 0 )
    		{
    				determinate = buildDET(matrix, size);
    		}
    
    	return determinate;
    }

    Output:
    Code:
    msu-mtrahan10@csci:~$ cd CSCI415/Assignment_2
    msu-mtrahan10@csci:~/CSCI415/Assignment_2$ ./assignment2 nums.txt 3 3
    assignment2: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
    assignment2: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
    assignment2: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
    
    
    The determinant of this matrix is: 0

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,465
    Googling those error messages suggests you're trashing the internal pointers used by malloc to allocate new memory. Try running your code through a memory profiler like valgrind and fix all the problems it reports. We have a brief tutorial here: Using Valgrind to Find Memory Leaks - Cprogramming.com.

    I ran your code through valgrind and found lots of invalid reads and writes, and a stack overflow. You need to check the return value from malloc for NULL (error) and free memory when you're done. You should avoid casting malloc. Also, your loop in calcDET never seems to end, which could be a problem since you allocate memory in getSUB (via buildDET) and never free it, so calcDET ends up using up all your heap.

    But like I said, there's lots of errors you need to resolve, so get valgrind up and running and profile your code. It's a great tool to use on all C code you write.

  5. #5
    Registered User
    Join Date
    Mar 2009
    Posts
    24
    Turns out it was because I had a lapse in logic and put an OR where an AND should have been.

    Reminds me of that Intel commercial.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting Matrix
    By alex 2010 in forum C++ Programming
    Replies: 0
    Last Post: 06-24-2010, 09:40 AM
  2. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  3. matrix determinant
    By roaan in forum C Programming
    Replies: 1
    Last Post: 06-30-2009, 12:44 PM
  4. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 04:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21