الگوریتمی برای ضرب n ماتریس در هم - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

الگوریتمی برای ضرب n ماتریس در هم

0 امتیاز
سلام من دنبال یک الگوریتم سریع برای ضرب n تا ماتریس A2,A1,... هستم کسی میتونه کمک کنه ؟
سوال شده آذر 5, 1392  بوسیله ی shab (امتیاز 194)   8 22 30
دوباره تگ گذاری شد بهمن 22, 1392 بوسیله ی BlueBlade

1 پاسخ

+4 امتیاز
 
بهترین پاسخ
من الگوریتم آماده ای سراغ ندارم ولی میتونم چند تا پیشنهاد بهتون بدم.

1.ماتریسها رو به ترتیبی ضرب کنید که اونهایی که ابعاد بزرگتر دارند و نتیجه کوچکتر میدهند زودتر ضرب بشوند.

2x4*4x4*4x8 دو جور ضرب میشه, (2x4*4x4) * 4x8 و 2x4*(4x4 * 4x8) که اولی سرعت بیشتری داره و کمک میکنه حافظه زودتر آزاد بشه.

2.اطلاعاتت رو طوری بچین و ضرب کن(پشت سر هم و به ترتیب) که کامپایلر به طور خودکار از SSE یا AVX یا IS های مشابه استفاده کنه.

البته سیستم های جدید با استفاده از gather-scatter خودشون تا حدی به این کار کمک میکنند که باعث میشه برنامه نویس کمتر نگران این موضوع باشه.
پاسخ داده شده آذر 6, 1392 بوسیله ی FastCode (امتیاز 602)   1 2 11
ویرایش شده آذر 7, 1392 بوسیله ی FastCode
+1 برای این راه حل (-_^)
n  تا ماتریس داره ... چجوری اونهایی که ابعاد بزرگ تر و  نتیجه کوچیک تر دارند را بتونه تشخیص بده و اول زودتر ضرب کنه ؟؟؟
اینجوری که سرعت برنامه خیلی کند میشه
کاملاً مشخصه، در ضرب ماتریس ها تعداد سطرهای ماتریس نتیجه برابر است با تعداد سطرهای ماتریس اول و تعداد ستونها برابر است با تعداد ستونهای ماتریس دوم. توجه به این نکته هم ضروری است که تعداد ستونهای ماتریس اول باید با تعداد سطرهای ماتریس دوم برابر باشد. با توجه به این دو نکته می توانید ماتریسهایی را تشخیص دهید که ابعاد بزرگی دارند و نتیجه کوچک می دهند. اگر هم دنبال کد در این خصوص هستید پیشنهاد می کنم که یک تاپیک مجزا ایجاد کنید.
...