'How to calculate time complexity of matrix multiplication, if the matrix size is 2000?
I need to calculate the time complexity of matrix multiplication, the size of the matrices is 2000, but when I run the program, doesn't print anything. The program works fine when I change the size to 200. Basically, I just need to calculate the time that it takes to multiply matrices for n = 500, 1000, 1500, 2000. I've read that if you have a matrix with a big size, you should declare it as global, I've tried that but it's the same.
This is the main file:
#include <iostream>
#include <time.h>
#include "matrices.h"
using namespace std;
int size = 2000;
int** mat1;
int** mat2;
int** mat3;
int main(int argc, char** argv) {
//int** mat1;
mat = new int* [size];
//int** mat2;
mat2 = new int* [size];
//int** mat3;
mat3 = new int* [size];
int step = 500;
double ticksPerMs = double{ CLOCKS_PER_SEC } / 1000;
clock_t startTime = clock();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
mat1[i] = new int[size];
}
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
mat2[i] = new int[size];
}
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
mat3[i] = new int[size];
}
}
for (int n = 0; n <= size; n += step) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
mat1[i][j] = n - i;
mat2[i][j] = n - i;
mat3[i][j] = 0;
}
}
matMult1(mat1, mat2, mat3, n);
double durationMs = (clock() - startTime) / ticksPerMs;
cout << "Step: " << n << endl;
cout << "Matrix Multiplication 1: " << durationMs << endl;
}
for (int n = 0; n <= size; n += step) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
mat1[i][j] = n - i;
mat2[i][j] = n - i;
mat3[i][j] = 0;
}
}
matMult2(mat1, mat2, mat3, n);
double durationMs = (clock() - startTime) / ticksPerMs;
cout << "Step: " << n << endl;
cout << "Matrix Multiplication 2: " << durationMs << endl;
}
for (int n = 0; n <= size; n += step) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
mat1[i][j] = n - i;
mat2[i][j] = n - i;
mat3[i][j] = 0;
}
}
matMult3(mat1, mat2, mat3, n);
double durationMs = (clock() - startTime) / ticksPerMs;
cout << "Step: " << n << endl;
cout << "Matrix Multiplication 3: " << durationMs << endl;
}
return 0;
}
And this is the header file:
#ifndef _MATRIX_H
#define _MATRIX_H
void matMult1(int **a, int **b, int **c, int n);
void matMult2(int **a, int **b, int **c, int n);
void transpone(int **a, int n);
void matMult3(int **a, int **b, int **c, int n);
void matMult1(int **a, int **b, int **c, int n)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) {
int sum =0;
for(int k=0; k<n; k++)
sum += a[i][k] * b[k][j];
c[i][j]= sum;
}
}
void matMult2(int **a, int **b, int **c, int n)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
c[i][j] = 0;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
for(int k=0; k<n; k++) {
c[i][j] += a[i][k] * b[k][j];
}
}
void transpone(int **a, int n)
{
int tmp;
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++) {
tmp = a[i][j];
a[i][j] = a[j][i];
a[j][i] = tmp;
}
}
void matMult3(int **a, int **b, int **c, int n)
{
int sum;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
c[i][j] = 0;
transpone(b, n);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) {
sum = 0;
for(int k=0; k<n; k++)
sum += a[i][k] * b[j][k];
c[i][j] = sum;
}
}
#endif
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
