ضرب ماتریس اسپارس

[zeinab03]

سلام دوستان عزیز
اگه ممکنه الگوریتم ضرب دو ماتریس اسپارس رو توضیح بدین..ممنون:چشمک:

[yoosof_145]

ماتریس اسپارسو واسم تعریف کن تا الگوریتمش رو بتونم بگم.

==============
اخوی فارسی تایپ کن
وگرنه دفعه بعد طبق مقررات پستت حذف میشه.
ممنون

سپیدار

[Golden Galaxy]

سلام دوست عزیز
در ماتریس های اسپارس همانطور که می دانید تعداد خانه های صفر ( یک مدل ) زیاد است پس صرفه به استفاده از روش معمولی نیست .
حتما با روش ذخیره سازی این نوع ماتریس ها آشنا هستید .
باید در هر مرحله عنصر k ام سطر i ام از ماتریس اول را در عنصر k ام از ستون j ام از ماتریس دوم را در هم ضرب کرد و حاصل را به عنوان عنصر در مکان i , j از ماتریس سوم قرار داد .
نکته مهم این است که حاصل ضرب دو ماتریس اسپارس حتما یک ماتریس اسپارس نخواهد بود .
عمل بالا را می توان با سه حلقه for تو در تو پیاده سازی کرد و برای جستجو هم از جستجوی خطی ساده استفاده کرد .
برای اطلاعات بیشتر : کتاب ساختمان داده ها در ++ C مهندس جعفر نژاد قمی

[اَرژنگ]

matrise spars ro baram tarif kon ta algoritmesho behetun begam
http://www.nist.gov/dads/HTML/sparsematrix.html

[bahman_asham]

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int **arr,**bb,*t,*p;
int main()
{ clrscr();
int i,j,x,y,a=2,b=1,z=0,u=3;
cout<<"enter x:";
cin>>x;
cout<<"enter y:";
cin>>y;
p=(int *)malloc(sizeof(int)* x);
for(i=1;i<=x;i++)
arr[i]=(int *)malloc(y * sizeof(int));
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
{
cout<<"enter arr["<<i<<"]["<<j<<"]=";
cin>>arr[i][j];
}
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
if(arr[i][j]!=0 )z++;
t=(int *)malloc(u * sizeof(int));
for(i=1;i<x;i++)
bb[i]=(int *) malloc(z * sizeof(int));

bb[1][1]=x;
bb[1][2]=y;
bb[1][3]=z;
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
if(arr[i][j]!=0)
{
bb[a][b]=i;
b++;
bb[a][b]=j;
b++;
bb[a][b]=arr[i][j];
b=1;
a++;
}
for(i=1;i<=(z+1);i++)
for(j=1;j<=3;j++)
{
cout<<bb[i][j];
if (j==3)
cout<<endl;
}
getch();
return 0;
}

[Sepidar]

اگه مطمئن بودم برای پروژه دانشجویی ازشون استفاده نمیشه، کتابخانه های ماتریسم رو رو سایت آپلود میکردم...

ضرب ماتریس اسپارس هیچ فرقی با ضرب ماتریس های معمولی نداره. تنها تفاوت در روش ذخیره سازی این ماتریسهاست. اینجا (http://www.cs.utk.edu/%7Edongarra/etemplates/node372.html) میتونین یه سری از روشهای معروف ذخیره سازی این ماتریس رو ببینین. اگر چه من خودم از هیچکدوم از روشهای اون مقاله استفاده نمیکنم و عوضش از یه درخت برای نگهداری ساختار این ماتریسها استفاده میکنم.

[kh1387]

میشه کسی طریقه ضرب رو توضیح بده؟
متشکرم

[saba_v]

سلام
برای ضرب دو ماتریس اسپارس باید ماتریس دومی را ترانهاده اش را بدست آورد و سپس در ماتریس اول ضرب کرد. همان طور که برای جمع دو ماتریس اسپارس باید 2 ماتریس را ترانهاده آنها را بدست آورد و سپس جمع کرد .

[h_math]

سلام
دوست عزيز آقای bahman_asham ممنون از برنامه ضرب ماتریس اسپارس
متاسفانه من آشنایی کاملی به دستورات حرفه ای زبان C ندارم و از این الگوریتم های طولانی چیزی سردر نمیارم
ممنون میشم اگه سطر چهارم از برنامه یعنی int **arr,**bb,*t,*p رو برام توضیح بدین نفهمیدم چی تعریف کردین؟
فقط من تا 2روز وقت دارم اینو بفهمم
ممنونم اگه زود...

[csharpprogramer88]

نکته مهم این است که حاصل ضرب دو ماتریس اسپارس حتما یک ماتریس اسپارس نخواهد بود .
عمل بالا را می توان با سه حلقه for تو در تو پیاده سازی کرد و برای جستجو هم از جستجوی خطی ساده استفاده کرد .
برای اطلاعات بیشتر : کتاب ساختمان داده ها در ++ C مهندس جعفر نژاد قمی
سلام

دوست عزیز لطفا در این باره برام توضیح بدید و یک مثال هم بگید
در باره حاصل جمع هم حرف شما صادقه؟

[soorena]

اگه مطمئن بودم برای پروژه دانشجویی ازشون استفاده نمیشه، کتابخانه های ماتریسم رو رو سایت آپلود میکردم...

هر کی ندونه فکر ميکنه طرف يه کتابخونه پيچيده نوشته که الان ناسا هم برای پرتاب موشک جديدش داره ازش استفاده ميکنه.....
بابا تو خيلی خيلی ... خفنی.....خفن....خوف....خف..

[amir_saniyan]

این هم ماتریس اسپارس که خودم نوشتم :)


#include <cstdlib>
#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;
template <class T>
class sparse_matrix_element
{
public:
sparse_matrix_element(int _row, int _column, T _value)
{
if(_row < 0)
{
throw invalid_argument("_row");
}
if(_column < 0)
{
throw invalid_argument("_column");
}
m_row = _row;
m_column = _column;
m_value = _value;
}
int row(void) const
{
return m_row;
}
int column(void) const
{
return m_column;
}
T value(void) const
{
return m_value;
}
void value(T _val)
{
m_value = _val;
return;
}
private:
int m_row;
int m_column;
T m_value;
};
template <class T>
class sparse_matrix
{
public:
sparse_matrix(int _rows_length, int _columns_length)
{
if(_rows_length <= 0)
{
throw invalid_argument("_rows_length");
}
if(_columns_length <= 0)
{
throw invalid_argument("_columns_length");
}
m_rows_length = _rows_length;
m_columns_length = _columns_length;
}
int rows_length(void) const
{
return m_rows_length;
}
int columns_length(void) const
{
return m_columns_length;
}
T element(int _row, int _column) const
{
if(_row < 0 || _row >= m_rows_length)
{
throw invalid_argument("_row");
}
if(_column < 0 || _column >= m_columns_length)
{
throw invalid_argument("_column");
}
for(vector<sparse_matrix_element<T>>::size_type i = 0; i < m_elements.size(); i++)
{
if(m_elements[i].row() == _row && m_elements[i].column() == _column)
{
return m_elements[i].value();
}
}
return 0;
}
void element(int _row, int _column, T _value)
{
if(_row < 0 || _row >= m_rows_length)
{
throw invalid_argument("_row");
}
if(_column < 0 || _column >= m_columns_length)
{
throw invalid_argument("_column");
}
for(vector<sparse_matrix_element<T>>::size_type i = 0; i < m_elements.size(); i++)
{
if(m_elements[i].row() == _row && m_elements[i].column() == _column)
{
if(_value != 0)
{
m_elements[i].value(_value);
}
else
{
m_elements.erase(m_elements.begin() + i);
}
return;
}
}
if(_value != 0)
{
sparse_matrix_element<T> element(_row, _column, _value);
m_elements.push_back(element);
}
return;
}
sparse_matrix<T> transpose(void) const
{
sparse_matrix<T> result(columns_length(), rows_length());
for(int row = 0; row < rows_length(); row++)
{
for(int column = 0; column < columns_length(); column++)
{
T e = element(row, column);
result.element(column, row, e);
}
}
return result;
}
sparse_matrix<T> add(const sparse_matrix& _matrix) const
{
if(rows_length() != _matrix.rows_length() || columns_length() != _matrix.columns_length())
{
throw logic_error("Matrices of the same size can be added or subtracted.");
}
sparse_matrix<T> result(rows_length(), columns_length());
for(int row = 0; row < rows_length(); row++)
{
for(int column = 0; column < columns_length(); column++)
{
T element1 = element(row, column);
T element2 = _matrix.element(row, column);
T sum = element1 + element2;
result.element(row, column, sum);
}
}
return result;
}
sparse_matrix<T> subtract(const sparse_matrix& _matrix) const
{
if(rows_length() != _matrix.rows_length() || columns_length() != _matrix.columns_length())
{
throw logic_error("Matrices of the same size can be added or subtracted.");
}
sparse_matrix<T> result(rows_length(), columns_length());
for(int row = 0; row < rows_length(); row++)
{
for(int column = 0; column < columns_length(); column++)
{
T element1 = element(row, column);
T element2 = _matrix.element(row, column);
T sum = element1 - element2;
result.element(row, column, sum);
}
}
return result;
}
sparse_matrix<T> scalar_multiply(T _x) const
{
sparse_matrix<T> result(rows_length(), columns_length());
for(int row = 0; row < rows_length(); row++)
{
for(int column = 0; column < columns_length(); column++)
{
T e = _x * element(row, column);
result.element(row, column, e);
}
}
return result;
}
sparse_matrix<T> multiply(const sparse_matrix& _matrix) const
{
if(columns_length() != _matrix.rows_length())
{
throw logic_error("Two matrices can be multiplied only when the number of columns in the first equals the number of rows in the second.");
}
sparse_matrix<T> result(rows_length(), _matrix.columns_length());
for(int row = 0; row < rows_length(); row++)
{
for(int column = 0; column < _matrix.columns_length(); column++)
{
T sum = 0;
for(int i = 0; i < columns_length(); i++)
{
T element1 = element(row, i);
T element2 = _matrix.element(i, column);
sum += element1 * element2;
}
result.element(row, column, sum);
}
}
return result;
}
private:
int m_rows_length;
int m_columns_length;
vector<sparse_matrix_element<T>> m_elements;
};
template <class T>
sparse_matrix<T> read_sparse_matrix(void)
{
int rows_length;
cout << "Please enter rows length (eg. 10): ";
cin >> rows_length;
int columns_length;
cout << "Please enter columns length (eg. 15): ";
cin >> columns_length;
sparse_matrix<T> matrix(rows_length, columns_length);
while(true)
{
char confirm;
cout << "Do you want to enter an element? [y|n]: ";
cin >> confirm;
if(confirm != 'y' && confirm != 'Y')
{
break;
}
int row;
cout << "Please enter zero base row (eg. 5): ";
cin >> row;
int column;
cout << "Please enter zero base column (eg. 10): ";
cin >> column;
T value;
cout << "Please enter zero element value: ";
cin >> value;
matrix.element(row, column, value);
}
return matrix;
}
template <class T>
void print_sparse_matrix(const sparse_matrix<T>& _matrix)
{
for(int row = 0; row < _matrix.rows_length(); row++)
{
cout << "[";
for(int column = 0; column < _matrix.columns_length(); column++)
{
cout << _matrix.element(row, column);
if(column < (_matrix.columns_length() -1))
{
cout << ", ";
}
}
cout << "]" << endl;
}
return;
}
int main()
{
sparse_matrix<double> m1(10, 10);
sparse_matrix<double> m2(10, 10);
while(true)
{
try
{
cout << "Commands:" << endl;
cout << "1) Read sparse matrix m1." << endl;
cout << "2) Read sparse matrix m2." << endl;
cout << "3) Print sparse matrix m1." << endl;
cout << "4) Print sparse matrix m2." << endl;
cout << "5) Print transpose of matrix m1." << endl;
cout << "6) Print transpose of matrix m2." << endl;
cout << "7) Print m1 + m2." << endl;
cout << "8) Print m1 - m2." << endl;
cout << "9) Print scalar * m1." << endl;
cout << "10) Print scalar * m2." << endl;
cout << "11) Print m1 * m2." << endl;
cout << "12) Exit." << endl;
int command;
cout << "Please enter command number: ";
cin >> command;
switch(command)
{
case 1:
{
m1 = read_sparse_matrix<double>();
}
break;
case 2:
{
m2 = read_sparse_matrix<double>();
}
break;
case 3:
{
print_sparse_matrix<double>(m1);
}
break;
case 4:
{
print_sparse_matrix<double>(m2);
}
break;
case 5:
{
sparse_matrix<double> transpose = m1.transpose();
print_sparse_matrix<double>(transpose);
}
break;
case 6:
{
sparse_matrix<double> transpose = m2.transpose();
print_sparse_matrix<double>(transpose);
}
break;
case 7:
{
sparse_matrix<double> result = m1.add(m2);
print_sparse_matrix<double>(result);
}
break;
case 8:
{
sparse_matrix<double> result = m1.subtract(m2);
print_sparse_matrix<double>(result);
}
break;
case 9:
{
double scalar;
cout << "Please enter a scalar: ";
cin >> scalar;
sparse_matrix<double> result = m1.scalar_multiply(scalar);
print_sparse_matrix<double>(result);
}
break;
case 10:
{
double scalar;
cout << "Please enter a scalar: ";
cin >> scalar;
sparse_matrix<double> result = m2.scalar_multiply(scalar);
print_sparse_matrix<double>(result);
}
break;
case 11:
{
sparse_matrix<double> result = m1.multiply(m2);
print_sparse_matrix<double>(result);
}
break;
case 12:
{
exit(0);
}
break;
default:
{
cout << "Invalid command." << endl;
}
break;
}
}
catch(exception e)
{
cout << "Error: " << e.what() << endl;
}
cout << endl;
}
return 0;
}