kavehmj
جمعه 22 آبان 1394, 00:50 صبح
سلام بر همگی.
دوستان من یک کد برای محاسبه ی معکوس یک ماتریس در C++ نوشته ام.
کد به شکل زیر است:
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <iomanip>
#include <time.h>
using namespace std;
using std::setw;
#define cc 15
//-----------------------------------------------------
// Print matrix in general
void printM(long double c[][cc], int row, int column)
{
for (int i = 0; i<row; i++)
{
for (int j = 0; j<column; j++)
cout << setw(5) << c[i][j] << " ";
cout << "\n";
}
}
void build(long double b[][cc], long double a[][cc], int i, int n)
{
int h = 0, k = 0;
for (int l = 1; l<n; l++)
{
for (int j = 0; j<n; j++)
{
if (j == i)
continue;
b[h][k] = a[l][j];
k++;
if (k == n - 1)
{
h++;
k = 0;
}
}
}
}
//-----------------------------------------------------
// Build Initial Kahad Matrix
void buildKahadini(long double b[][cc], long double a[][cc], int i, int j, int n)
{
for (int l = 0; l < n - 1; l++){
for (int k = 0; k < n - 1; k++){
if (l < i && k < j)
b[l][k] = a[l][k];
else if (l<i && k >= j)
b[l][k] = a[l][k + 1];
else if (l >= i && k<j)
b[l][k] = a[l + 1][k];
else if (l >= i && k >= j)
b[l][k] = a[l + 1][k + 1];
}
}
}
//-----------------------------------------------------
//Transpose
void Trans(long double b[][cc], long double a[][cc], int r, int c){
for (int i = 0; i<c; i++){
for (int j = 0; j<r; j++)
b[i][j] = a[j][i];
}
}
//-----------------------------------------------------
//calculate determinte
long double det(long double a[][cc], int n)
{
int i;
long double sum = 0;
long double b[cc][cc];
if (n == 2)
{
sum = a[0][0] * a[1][1] - a[0][1] * a[1][0];
return sum;
}
else
{
for (i = 0; i<n; i++)
{
build(b, a, i, n);
sum += a[0][i] * pow(-1, i)*det(b, (n - 1));
}
}
return sum;
}
//-----------------------------------------------------
// Build Kahad Matrix
void buildKahad(long double C[][cc], long double a[][cc], int n){
long double Cini[cc][cc];
for (int ii = 0; ii < n; ii++)
for (int jj = 0; jj < n; jj++){
buildKahadini(Cini, a, ii, jj, n);
C[ii][jj] = pow(-1, ii + 1 + jj + 1)*det(Cini, n - 1);
}
}
//-----------------------------------------------------
// Inverse Matrix
void InverseM(long double ainv[][cc], long double a[][cc], int n)
{
long double Ct[cc][cc], C[cc][cc], d;
d = det(a, n);
buildKahad(C, a, n);
Trans(Ct, C, n, n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++){
ainv[i][j] = pow(d, -1)*Ct[i][j];
}
}
//-------------------------------------------
//main PROGRAM
int main()
{
//************************************************** ************************************************** ********************
// Main Codes
// test Speed
cout << "start test" << endl;
int testdim = 9,bt,et;
long double t1[cc][cc],tinv1[cc][cc],tI[cc][cc];
for (int i = 0; i < testdim; i++)
for (int j = 0; j < testdim; j++)
t1[i][j] = rand() % 10 + 1;
bt = time(0);
InverseM(tinv1, t1, testdim);
et = time(0);
multiplyM(t1, testdim, testdim, tinv1, testdim, testdim, tI);
cout << "\n\nt1" << endl;
printM(t1, testdim, testdim);
cout << "\n\ntinv1" << endl;
printM(tinv1, testdim, testdim);
cout << "\n\ntI" << endl;
printM(tI, testdim, testdim);
cout << "Calc time: " << et - bt << endl;
system("PAUSE");
//EO test Speed
return 0;
}
کد رو تست کردم و معکوس هر ماتریسی رو به درستی جواب می ده.
مشکلی که دارم، این هست که برای ماتریس های بزرگ، خصوصا وقتی ابعاد آن از 10 فراتر می روی، زمان زیادی صرف محاسبه ی معکوس آن می شود.
مثلا برای ماتریس 10x10 حدود 7 ثانیه، برای 11x11حدود 87 ثانیه ، 12x12 حدود 1130 ثانیه و کلا برای یه ماتریس nxn می شه (n+1)*(مدت زمان محاسبه معکوس ماتریس (n-1)*(n-1) )
در حالی که مثلا یه ماتریس 12x12 که اینجا 1130 ثانیه طول می کشه، همون ماتریس در متلب در کم تر از 1 ثانیه معکوسش محاسبه می شه!!!.
با بررسی هایی که انجام داذم، بیشتر زمان صرف شده صرف ساختن ماتریس ضرایب یا همون کهاد (در کد با نام buildkahad) می شود. از اونجایی که در این تابع برای هر عضوش باید دترمینان حساب شود، ظاهرا محاسبه ی دترمینان بیشتر از همه زمان می برد.
تنها چیزی که به ذهنم می رسه این هست که در محاسبه ی دترمینان از الگوریتم مناسبی استفاده نکردم.
اگر می توانید راهنمایی ام کنید که آیا واقعا مشکل زمان زیاد اجرای این کد مربوط به همین دترمینان هست؟ اگر آره راهی برای افزایش سرعت دارید؟
با تشکر
دوستان من یک کد برای محاسبه ی معکوس یک ماتریس در C++ نوشته ام.
کد به شکل زیر است:
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <iomanip>
#include <time.h>
using namespace std;
using std::setw;
#define cc 15
//-----------------------------------------------------
// Print matrix in general
void printM(long double c[][cc], int row, int column)
{
for (int i = 0; i<row; i++)
{
for (int j = 0; j<column; j++)
cout << setw(5) << c[i][j] << " ";
cout << "\n";
}
}
void build(long double b[][cc], long double a[][cc], int i, int n)
{
int h = 0, k = 0;
for (int l = 1; l<n; l++)
{
for (int j = 0; j<n; j++)
{
if (j == i)
continue;
b[h][k] = a[l][j];
k++;
if (k == n - 1)
{
h++;
k = 0;
}
}
}
}
//-----------------------------------------------------
// Build Initial Kahad Matrix
void buildKahadini(long double b[][cc], long double a[][cc], int i, int j, int n)
{
for (int l = 0; l < n - 1; l++){
for (int k = 0; k < n - 1; k++){
if (l < i && k < j)
b[l][k] = a[l][k];
else if (l<i && k >= j)
b[l][k] = a[l][k + 1];
else if (l >= i && k<j)
b[l][k] = a[l + 1][k];
else if (l >= i && k >= j)
b[l][k] = a[l + 1][k + 1];
}
}
}
//-----------------------------------------------------
//Transpose
void Trans(long double b[][cc], long double a[][cc], int r, int c){
for (int i = 0; i<c; i++){
for (int j = 0; j<r; j++)
b[i][j] = a[j][i];
}
}
//-----------------------------------------------------
//calculate determinte
long double det(long double a[][cc], int n)
{
int i;
long double sum = 0;
long double b[cc][cc];
if (n == 2)
{
sum = a[0][0] * a[1][1] - a[0][1] * a[1][0];
return sum;
}
else
{
for (i = 0; i<n; i++)
{
build(b, a, i, n);
sum += a[0][i] * pow(-1, i)*det(b, (n - 1));
}
}
return sum;
}
//-----------------------------------------------------
// Build Kahad Matrix
void buildKahad(long double C[][cc], long double a[][cc], int n){
long double Cini[cc][cc];
for (int ii = 0; ii < n; ii++)
for (int jj = 0; jj < n; jj++){
buildKahadini(Cini, a, ii, jj, n);
C[ii][jj] = pow(-1, ii + 1 + jj + 1)*det(Cini, n - 1);
}
}
//-----------------------------------------------------
// Inverse Matrix
void InverseM(long double ainv[][cc], long double a[][cc], int n)
{
long double Ct[cc][cc], C[cc][cc], d;
d = det(a, n);
buildKahad(C, a, n);
Trans(Ct, C, n, n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++){
ainv[i][j] = pow(d, -1)*Ct[i][j];
}
}
//-------------------------------------------
//main PROGRAM
int main()
{
//************************************************** ************************************************** ********************
// Main Codes
// test Speed
cout << "start test" << endl;
int testdim = 9,bt,et;
long double t1[cc][cc],tinv1[cc][cc],tI[cc][cc];
for (int i = 0; i < testdim; i++)
for (int j = 0; j < testdim; j++)
t1[i][j] = rand() % 10 + 1;
bt = time(0);
InverseM(tinv1, t1, testdim);
et = time(0);
multiplyM(t1, testdim, testdim, tinv1, testdim, testdim, tI);
cout << "\n\nt1" << endl;
printM(t1, testdim, testdim);
cout << "\n\ntinv1" << endl;
printM(tinv1, testdim, testdim);
cout << "\n\ntI" << endl;
printM(tI, testdim, testdim);
cout << "Calc time: " << et - bt << endl;
system("PAUSE");
//EO test Speed
return 0;
}
کد رو تست کردم و معکوس هر ماتریسی رو به درستی جواب می ده.
مشکلی که دارم، این هست که برای ماتریس های بزرگ، خصوصا وقتی ابعاد آن از 10 فراتر می روی، زمان زیادی صرف محاسبه ی معکوس آن می شود.
مثلا برای ماتریس 10x10 حدود 7 ثانیه، برای 11x11حدود 87 ثانیه ، 12x12 حدود 1130 ثانیه و کلا برای یه ماتریس nxn می شه (n+1)*(مدت زمان محاسبه معکوس ماتریس (n-1)*(n-1) )
در حالی که مثلا یه ماتریس 12x12 که اینجا 1130 ثانیه طول می کشه، همون ماتریس در متلب در کم تر از 1 ثانیه معکوسش محاسبه می شه!!!.
با بررسی هایی که انجام داذم، بیشتر زمان صرف شده صرف ساختن ماتریس ضرایب یا همون کهاد (در کد با نام buildkahad) می شود. از اونجایی که در این تابع برای هر عضوش باید دترمینان حساب شود، ظاهرا محاسبه ی دترمینان بیشتر از همه زمان می برد.
تنها چیزی که به ذهنم می رسه این هست که در محاسبه ی دترمینان از الگوریتم مناسبی استفاده نکردم.
اگر می توانید راهنمایی ام کنید که آیا واقعا مشکل زمان زیاد اجرای این کد مربوط به همین دترمینان هست؟ اگر آره راهی برای افزایش سرعت دارید؟
با تشکر