PDA

View Full Version : ضرب ماتریس اسپارس



zeinab03
چهارشنبه 02 فروردین 1385, 16:58 بعد از ظهر
سلام دوستان عزیز
اگه ممکنه الگوریتم ضرب دو ماتریس اسپارس رو توضیح بدین..ممنون:چشمک:

yoosof_145
پنجشنبه 03 فروردین 1385, 14:51 بعد از ظهر
ماتریس اسپارسو واسم تعریف کن تا الگوریتمش رو بتونم بگم.

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

سپیدار

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

اَرژنگ
دوشنبه 07 فروردین 1385, 03:09 قبل از ظهر
matrise spars ro baram tarif kon ta algoritmesho behetun begam
http://www.nist.gov/dads/HTML/sparsematrix.html

bahman_asham
چهارشنبه 09 فروردین 1385, 12:07 بعد از ظهر
#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
دوشنبه 01 آبان 1385, 17:49 بعد از ظهر
اگه مطمئن بودم برای پروژه دانشجویی ازشون استفاده نمیشه، کتابخانه های ماتریسم رو رو سایت آپلود میکردم...

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

kh1387
جمعه 17 آبان 1387, 21:24 بعد از ظهر
میشه کسی طریقه ضرب رو توضیح بده؟
متشکرم

saba_v
چهارشنبه 12 فروردین 1388, 08:40 قبل از ظهر
سلام
برای ضرب دو ماتریس اسپارس باید ماتریس دومی را ترانهاده اش را بدست آورد و سپس در ماتریس اول ضرب کرد. همان طور که برای جمع دو ماتریس اسپارس باید 2 ماتریس را ترانهاده آنها را بدست آورد و سپس جمع کرد .

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

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

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

soorena
پنجشنبه 28 مهر 1390, 16:44 بعد از ظهر
اگه مطمئن بودم برای پروژه دانشجویی ازشون استفاده نمیشه، کتابخانه های ماتریسم رو رو سایت آپلود میکردم...

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

amir_saniyan
یکشنبه 13 آذر 1390, 18:58 بعد از ظهر
این هم ماتریس اسپارس که خودم نوشتم :)


#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;
}