فهرست مطالب

چکیده………………………………………………………………………………… ‌د

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

فصل اول: کلیات

جبر خطّی شاخه­ای از ریاضیّات است که به بررسی و مطالعه ماتریس­ها، بردارها، فضاهای برداری، تبدیل­های­ خطی و دستگاه­های معادله­های خطّی می­پردازد. علاوه بر کاربردهای فراوان جبر خطی در زمینه­هایی از خود ریاضیات همانند آنالیز تابعی، هندسه تحلیلی و آنالیز عددی، استفاده­های وسیعی نیز در فیزیک، مهندسی، علوم طبیعی و علوم اجتماعی پیدا کرده است [19] [16].برای به کار بردن دانش جبر خطی در علوم تجربی، فیزیک و مهندسی، که همگی لازم به انجام محاسبات عددی در آزمایش­ها و تحلیل داده­ها هستند، نیاز به توسعه شاخه­ای به نام جبر خطی عددی وجود دارد. جبر خطی عددی دانش مطالعه بر روی الگوریتم­های عددی جهت محاسبات جبر خطی بوده که مهم­ترین آنها عملیات ماتریسی برروی کامپیوتر است. عملیات ماتریسی پایه و اساس بسیاری از محاسبات مهندسی از قبیل پردازش تصویر، سیگنال، مخابرات، محاسبات مالی، علوم مهندسی مواد، بیولوژی و… است.یکی از مسائل عمومی عملیات ماتریسی تجزیه ماتریس[1] است. تجزیه ماتریس یک عمل فاکتورگیری[2] از ماتریس به صورت حاصلضرب چند عامل ماتریسی است. تجزیه­های ماتریسی مهم وپرکاربرد عبارتند از:  تجزیهLU ماتریسی[3]، تجزیه چولسکی ماتریس[4]، تجزیه QR ماتریس[5]، تجزیه  EVDماتریس[6]، تجزیه قطبی ماتریس[7] وتجزیه مقادیر منفرد ماتریس[8] یا  .درجبر خطی، الگوریتم SVD یک تجزیه از ماتریس حقیقی یا مختلط است که از ابزارهای قدرتمند باکاربردهای فراوان، مفید و تاثیرگذار در علوم پایه، فنی مهندسی و همچنین در پردازش سیگنال وآمار است. الگوریتم SVD یک تکنیک برای تجزیه یک ماتریس به ضرب سه فاکتور می‌باشد.الگوریتم ژاکوبی یکی از اولین الگوریتم­ها جهت اجرایی کردن SVD است. الگوریتم ژاکوبی یک ماتریس مستطیلی را به یک ماتریس قطری با استفاده از دنباله­ای از ضرب ماتریس­های چرخشی[9] تبدیل می­کند. این روش می­تواند مقادیر منفرد را با دقت بالا پیدا کند. لازم به ذکر است به کار بردن این روش به تنهایی خود عملکرد پائینی دارد، بنابراین باید به سمت روش­هایی با عملکرد بالاتری روی آورد. روش تجزیه مرحله­ای QR یکی از این الگوریتم­های عمومی وکاربردی در این زمینه است که با انجام پیش­ پردازش QR می­توان عملکرد اجرایی بالایی را به دست آورد. اساس مهم­ترین روش­های مدرن پیاده سازی الگوریتم SVD، کاهش ماتریس به شکل قطری با استفاده از تبدیل­های متعامد است. یکی از مزیّت­های تجزیه مرحله ای QR، قابلیّت حل مسائل با دقت و همگرایی بالا می باشد [29] و [9] .روش­های استاندارد SVD، در بسته­های   LINPACKو LAPACK پیاده سازی شده­اند. در این پایان­نامه، ما قصد استفاده از ابزارهای موازی نرم افزار MATLAB را داریم که در ادامه، مزیّت­های آن­را نسبت به نرم­افزارهای مشابه جهت موازی­سازی و معماری ساختار موازی به اختصار توضیح خواهیم داد.توسعه روش پیش پردازش مرحله­ای QR در الگوریتم ژاکوبی موازی می­تواند منجر به پیاده­سازی بهینه الگوریتم SVD گردد. این روش ابتکاری می­تواند در آنالیز و بهینه سازی داده­ها کاربردهای فراوانی داشته باشد.

1-2- کارهای صورت گرفته توسط دیگر محققان

الگوریتم ژاکوبی بلوکی موازی با یک ترتیب چرخه‌ای استاتیک اقدام به انتخاب زیر مساله‌های  SVDبرای حل شدن می­کند و از قبل، ترتیب حل زیر مساله‌ها مشخص شده است. این نظریه چرخه‌ای استاتیک دارای یک اشکال اساسی است، زیرا با توجه به خصوصیات خود ماتریس اقدام به صفر کردن عناصر خود ماتریس نمی‌کند. بنابراین این ایده که اگر در یک زمان مشخص اقدام به صفر کردن عناصر غیر‌قطری خاصی از ماتریس به صورت همزمان بکنیم، سرعت کاهش نرم فروبنیوس غیر‌قطری ماتریس افزایش می‌یابد. این ایده توسط م.بکا[10]، گ.اسکا[11]و م.واجترسیک[12] در[31]  بررسی شده است.گابریل اکسا و مارین واجترسیک در [22] یک روشی برای الگوریتم موازی ژاکوبی با استفاده از پیشینه­ی کاربرد این نوع پیش پردازش در الگوریتم سریال معرفی کردند که آنرا بررسی می­نماییم.یک روش برای اینکه در نهایت تعداد تکرارهای موازی کمتری در الگوریتم ژاکوبی موازی بلوکی داشته باشیم می­تواند برمبنای یک پیش پردازش خوش فرم کننده استوار باشد. این خوش فرم کننده پیش پردازشی باید دارای این خصوصیت باشد که نرم فروبنیوس ماتریس A را تا حد امکان بر روی قطر اصلی متمرکز کند. در حالت ایده­آل، اگر نرم فروبنیوس ماتریس A تماماً بر روی قطر اصلی متمرکز باشد، روش ژاکوبی موازی بلوکی با یک تکرار موازی به جواب می رسد. بنابراین متمرکز کردن نرم فروبنیوس ماتریس بر روی قطر اصلی و در نهایت کاستن تعداد تکرارهای موازی روش ژاکوبی موازی بلوکی می­تواند به عنوان یک هدف بررسی شود.ارتباط بین عناصر قطر اصلی عامل R در تجزیه­ی QR ماتریس A (یا عناصر قطر اصلی عامل -L در فاکتورگیری LQ ماتریس A) با مقادیر منفرد ماتریس A توسط استوارت در [27] مطالعه شده است. او به صورت تجربی نشان داده­که بعد از تجزیه­ی QR با لولا گیری ستونی (QRFCP) و به صورت اختیاری فاکتورگیری LQ (LQF) از عامل R با محورگیری ستونی یا بدون آن، قدر مطلق عناصر روی قطر اصلی ماتریس بالا مثلثی R یا پایین مثلثی L در حالت کلی می تواند تقریب مناسبی از مقادیر منفرد ماتریس A باشد.

1- کلیات………………………………………………………………………………. 3

1-1- مقدمه…………………………………………………………………………….. 3

1-2- کارهای صورت گرفته توسط دیگر محققان……………………………………. 5

 فصل دوم:تعاریف و الگوریتم ها

در این بخش به برخی از مفاهیم پایه­ای مورد نیاز در محاسبات ماتریس­ها اشاره شده است [4]:تعریف 2-1- اگر  نرم فروبینیوس[1] به صورت  نشان داده می‌شود و عبارت است از:(2-1-1)    تعریف2-2- ماتريس  يك ماتريس متقارن مي­باشد اگر .تعریف2-3- ماتريس  يك ماتريس هرمیتی مي­باشد اگر .     قضیه: اگر  يك ماتريس هرميتی باشد، آنگاه تمام مقادير ويژه آن حقيقي مي­باشد. بعلاوه ماتريس متعامد مانند  موجود است به طوری که :  يك ماتريس قطري است.تعریف2-4- به ماتريس هرميتی  يك ماتريس معين مثبت گويند. هرگاه به ازاي هر بردار غير صفر    داشته باشيم:تعریف 2-5- به ماتريس هرميتی  يك ماتريس شبه معين مثبت گويند. هرگاه به ازاي هر بردار غيرصفر  x   داشته باشيم:قضیه 2-2- فرض کنید و  دو ماتریس باشند. آنگاه مقادیر ویژه غیر صفر ماتريس­هاي AB و BA یکسان می­باشند.قضیه2-3- براي هر ماتريس   ماتريس  ،يك ماتريس هرميتی است و داراي مقادير ويژه حقيقي نامنفي مي­باشد.قضیه2-4- فرض كنيد  .آنگاه گزاره­هاي زير هم ارزند:الف- ماتريس­هاي  و  هرميتی مي­باشند، پس با استفاده از ماتريس­هاي متعامد[2] قطري پذيرند.ب- مقادير ويژه  حقيقي نامنفي­اند، به­طوری­که مقادير ويژه غيرصفر آن­ها با مقادير ويژه­ي غير صفر  برابرند.قضیه2-5- اگر  یک ماتریس حقیقی باشد، آنگاه ماتریس­های متعامدوجود دارند به­طوری کهدر آن اعداد  مقادیر منفرد  و برای هر مقدار منفرد  بردارهای   به ترتیب بردارهای منفرد چپ و راست  می­باشند.

2-2- تجزيه ماتریس ها بر اساس مقادير منفرد

تعریف 2-6- جهت رسيدن به تجزيه­ي مقادير منفرد ماتريس  بايد به مطالعه­ی مقادير ويژه­ي ماتريس  و بردارهای ویژه­ی ماتریس  بپردازيم.

2-2-1- مقادير منفرد[3]

مقادير منفرد ماتريس  عبارتند از جذر مقادير ويژه­ي ماتريس   كه با  نمايش مي­دهيم، به عبارت دیگر    و می­توان نوشت :در جایی که  رتبه ماتریس  می‌باشد.حال تجزيه مقادير منفرد یک ماتريس را بیان می­کنیم:

2-2-2- تجزيه مقادير منفرد

یکی از روش­های تجزیه ماتریس­ها، تجزیه بر اساس مقادیر منفرد است. در این روش یک ماتریس مانند   را می توان به صورت زیر تجزیه کرد:که در آن  و   ماتریس­های متعامد هستند و به­ترتیب  ماتریس­های منفرد چپ و راست نامیده می­شود و ستون­های ماتریس  از بردارهای ویژه یکا متعامد ماتریس  تشکیل می­شوند، همچنین

یک ماتریس مستطیلی قطری با مقادیر نامنفی حقیقیبر روی قطر اصلی است عناصر غیر صفر بر روی قطر ماتریس  ، مقادیر منفرد ماتریس   است.به اين نمونه فاكتورگيري، تجزيه مقادير منفرد ماتريس  گفته مي­شود. ستون هاي  و  به ترتيب بردارهاي منفرد راست و چپ ماتريس  است. هر ماتريس مختلط  با رتبه‌ي r را مي­توان به صورت تجزيه فوق نوشت. برای یافتن این ماتریس­ها به صورت زیر عمل می­کنیم:

  1. با استفاده از ماتريس متعامد   قطري­پذير است. درنتیجه كه  و  و ستون­هاي ماتريس  در روابط زير صدق مي­كند.(2-2-2)  اگر قرار دهیم  و:(2-2-3)    آنگاه بردارهای  یک پایه یکا متعامد برای  است.حال ما به تكميل پايه به فضاي  مي­پردازيم. جهت اين كار هسته­ي ماتريس  را در نظر می­گیریم. اگر  يك پايه يكا متعامد هسته­ي ماتريس  باشد، آنگاه بردارهاي  يك پايه براي  می باشد و قرار دهيم:الگوریتم­های زیادی جهت محاسبه­ی تجزیه مقادیر منفرد توسط محققان توسعه داده شده است. مشهورترین الگوریتم­های تجزیه مقادیر منفرد استفاده از الگوریتم QR  [17]و استفاده از الگوریتم ژاکوبی[12][8] است که به جهت پایداری عددی قابل توجه می­باشند. از لحاظ محاسباتی الگوریتم  دارای سرعت بالاتری نسبت به الگوریتم ژاکوبی کلاسیک می باشد. امّا اخیراً الگوریتم ژاکوبی به دلیل سادگی و امکان پردازش موازی از جذّابیّت بیشتری برخوردار شده است و هم­چنین جیمز دیمل در[14]نشان داد که الگوریتم ژاکوبی ممکن است دقیق­تر از الگوریتم  هم باشد.

و با استفاده از این روش در هر مرحله از الگوریتم ژاکوبی دنباله به سمت یک ماتریس قطری می­گراید. تعداد چرخش­های لازم جهت تبدیل ماتریس به یک ماتریس قطری از لحاظ نظری نامتناهی است، زیرا نمی­توانیم در حالت کلی یک معادله­ی چند جمله­ای در تعداد گام متناهی حل کنیم. [33]به هر حال ما می­توانیم این چرخش را پس از رسیدن به یک دقت مورد نظر قبول به اتمام برسانیم. در الگوریتم ژاکوبی کلاسیک در هر مرحله، آن عنصر غیر قطری ماتریس  صفر می­شود که دارای بزرگترین قدرمطلق است، یعنی:

2- تعاریف و الگوریتم ها……………………………………………………………. 8

2-1- تعاریف پایه……………………………………………………………………… 8

2-2- تجزيه ماتریس ها بر اساس مقادير منفرد…………………………………. 9

2-2-1- مقادير منفرد………………………………………………………………. 9

2-2-2- تجزيه مقادير منفرد………………………………………………………… 10

2-2-3- محاسبه دترمینان و معکوس یک ماتریس……………………………….. 11

2-4- ترتیب دوره ای الگوریتم ژاکوبی (Cyclic Schemes)………………………..16

2-5- طرح بلوکی ژاکوبی با ترتیب دورهای………………………………………. 17

2-6- پردازش موازی الگوریتم بلوکی ژاکوبی…………………………………….. 19

2-6-1- الگوریتم…………………………………………………………………….. 20

2-6-2- الگوریتم……………………………………………………………………. 24

2-7- ترتیب پویا در الگوریتم بلوکی موازی ژاکوبی……………………………….. 24

2-7-1- الگوریتم موازی ژاکوبی – بلوکی با ترتیب دینامیک…………………….. 27

 فصل سوم: بررسی روشهای پیشنهادی

در ادامه می­خواهیم روشی را معرفی کرده و چگونگی افزایش سرعت الگوریتم ژاکوبی تحت تاثیر آن را بررسی نماییم. پیش از این دیدیم که الگوریتم ژاکوبی تا وقتی ادامه پیدا می­کند که نرم فروبنیوس غیر قطری ماتریس اصلی به اندازه­ی کافی کوچک شود.اساس روش ارائه شده بر این ایده استوار است که آیا می­توان با پیش پردازش­های مفیدی نرم فروبنیوس ماتریس را بر روی قطر اصلی ماتریس متمرکز نموده و از نرم فروبنیوس عناصر غیر قطری کاسته شده و در نهایت الگوریتم ژاکوبی با سرعت محاسباتی بالاتری انجام پذیرد؟

یک روش برای اینکه در نهایت تعداد تکرارهای کمتری در الگوریتم ژاکوبی داشته باشیم می­تواند برمبنای یک پیش پردازش خوش فرم کننده استوار باشد. این خوش فرم کننده پیش پردازشی باید دارای این خصوصیت باشد که نرم فروبنیوس ماتریس  را تا حد امکان بر روی قطر اصلی متمرکز کند. در حالت ایده­ال اگر نرم فروبنیوس ماتریس  تماماً بر روی قطر اصلی متمرکز باشد، روش ژاکوبی موازی قطعه­ای با یک تکرار به جواب می­رسد. بنابراین متمرکز کردن نرم فروبنیوس ماتریس بر روی قطر اصلی و در نهایت کاستن تعداد تکرارهای روش ژاکوبی می­تواند به عنوان یک هدف بررسی شود.ارتباط بین عناصر قطر اصلی عامل  در تجزیه­ی  ماتریس  (یا عناصر قطر اصلی عامل –  در فاکتورگیری  ماتریس ) با مقادیر منفرد ماتریس  توسط استوارت[28] مطالعه شده است. او به صورت تجربی نشان داد که بعد از فاکتورگیری  با محور ستونی  و به صورت اختیاری فاکتورگیری    از عامل  با محور ستونی یا بدون آن، قدر مطلق عناصر روی قطر اصلی ماتریس بالا مثلثی  یا پایین مثلثی  در حالت کلی می تواند تقریب مناسبی از مقادیر منفرد ماتریس  باشد.چون­که مجموع مربعات مقادیر منفرد ماتریس برابر توان دوم نرم فروبنیوس ماتریس  می­باشد، این می­تواند به این معنا باشد که نرم فروبنیوس ماتریس بر روی قطر اصلی یا نزدیک آن متمرکز شده است.

3-1-1-1- تجزیه­ی  با محورگیری ستونی

همانطور که در بالا گفته شد، ایده اصلی  بکار بردن یک پیش پردازش در الگوریتم ژاکوبی، متمرکز کردن نرم فروبنیوس کل ماتریس تا حد امکان بر روی قطر اصلی ماتریس است. برای این منظور در ابتدا می­توان  بر روی ماتریس A انجام داد. این گام پیش پردازش یا همان فاکتورگیری  با محورگیری ستونی را می­توان به صورت زیر انجام داد :  که  ماتریس جایگشت،  دارای ستون­های متعامد و  یک ماتریس بالا مثلثی است.در گام دوم با استفاده از الگوریتم ژاکوبی  ماتریس  محاسبه می­شود. فرض کنید که ماتریس  به صورت زیر نمایش داده شود:

که    و      به ترتیب بردارهای منفرد راست و چپ ماتریس  و ماتریس قطری    شامل  مقدار منفرد به صورت  که مساوی مقادیر منفرد  است.در آخر، جهت تعیین  ماتریس  ،   به گام پس–پردازش احتیاج است. با استفاده از روابط فوق:همانطور که از روابط فوق دیده می­شود گام پس–پردازش اساساً شامل یک توزیع ضرب ماتریسی است. در اینجا می­توان جایگشت سطرهای ماتریس  را  با جمع آوری در یک پردازنده و تعویض سطرهای آن، این عملیات را بدون ضرب ماتریسی   انجام داد .

 3- بررسی روشهای پیشنهادی…………………………………………………… 30

3-1- پیش پردازش های موثر در الگوریتم ژاکوبی……………………………….. 30

3-1-1- انواع پیش- پردازش و پس- پردازش الگوریتم ژاکوبی…………………… 31

3-1-1-1- تجزیهی  با محورگیری ستونی………………………………………….. 31

3-1-1-2- تجزیهی اختیاری  از عامل ……………………………………………….. 32

3-2- نتایج بررسی اولین گروه از آزمایشها…………………………………………. 33

3-2-1- نتایج تجربی مربوط به ماتریس ها با توزیع مقادیر منفرد مینیمال چندگانه. 36

3-2-2- حالت توزیع مقادیر منفرد به صورت دنباله هندسی……………………….. 39

3-3- ساختار عامل  (عامل (  و اثر آن بر سرعت همگرایی پیش-پردازشها……… 40

3-4- بهبود عملکرد پیش-پردازشها با بکارگیری توزیع دادهای بهینه…………….. 46

 فصل چهارم: بررسی نتایج تجربی

همانطور که در فصل قبل اشاره شد، جهت بالا بردن سرعت گام پیش-پردازش، به توزیع داده­ای متفاوتی احتیاج داریم. گفتیم که این توزیع داده­ای باید از یک توزیع سطری  به توزیع پردازنده­ها در شبکه پردازشی به صورت  که  تغییر پیدا کند. همچنین گفتیم که علاوه بر انتخاب این پارامتر شبکه­ای پردازنده­ها عرض بلوک  نیز از اهمیت زیادی برخوردار است.جهت شناسایی مقادیر بهینه برای این پارامترها به بررسی آزمایش­های انجام شده بر شبکه پردازشی پرداخته­ایم.اجرای گام  بر روی شبکه­ی پردازشی با عنوان woodcrestcluster در دانشگاه ارلانجن نورنبرگ آلمان انجام شده است. شبکه­ی woodcrestcluster شامل 217 گره محاسباتی است. هر کدام از گره­های محاسباتی دارای دو پردازنده­ از نوع  (شامل چهار هسته که در دو پردازنده­ی دو هسته­ای قرار دارد است که قابلیت اجرا با سرعت  گیگا هرتز دارد. هر پردازنده­ی دو هسته­ای  دارای 4 مگابایت حافظه­ی درونی اشتراکی [1] است. هر گره محاسباتی همچنین دارای 8 گیگابایت حافظه­ی اصلی و 160 گیگابایت دیسک سخت محلی است. پهنای باند ارتباطی گره­های محاسباتی با سرعت 10 گیگا بیت بر ثانیه است. جهت انجام آزمایش بر روی ماتریس­هایی از مرتبه­ی  و  تعداد  و  پردازنده استفاده شده، به نحوی که در خلال انجام آزمایش­ها نسبت    ثابت است. این مقدار ثابت برای نسبت  به این جهت در نظر گرفته شده که نسبت استفاده از حافظه­ی درونی[2] به عرض بلوک برای همه حالت­ها یکسان باشد.برای هر تعداد پردازنده­ی ، تمام مقادیر ممکن  و  برای شبکه­ی پردازشی   که ، آزمایش شده است.  همچنین به طور خاص شبکه پردازشی  مربوط به توزیع ستونی– بلوکی که در آزمایش­های  فصل قبل برای قسمت تکراری الگوریتم  استفاده شد، در اینجا نیز بررسی ­می­شود.برای انتخاب اندازه­ی بلوک ی ، از اطلاعاتی که در فصل قبل بررسی شد می­توان استفاده کرد. توسعه دهنده­گان دیگر در [10] سفارش مقدار کوچک برای  در معماری شبکه پردازشی موازی خود داده­اند که به طور ویژه، مقدار بهینه  تشخیص داده شده است. در این آزمایش­ها از مقادیر ،  استفاده شده است.عناصر و درایه­های ماتریس در تمام آزمایش­ها به صورت تصادفی با تجویز مقدار عدد شرطی مشخص  و توزیع مقادیر منفرد  تولید شده­است. در این آزمایش­ها دو توزیع مقادیر منفرد بکار رفته است. در نخستین توزیع مقادیر منفرد ( )، ماتریس دارای مقادیر منفرد مینیمال چندگانه با توزیع  و   و در حالت دوم )، مقادیر منفرد به صورت دنباله­ی هندسی بصورت  و  (به طوری که تمام مقادیر منفرد متمایز بوده و در اطراف  قرار دارند) توزیع شده­اند.تجزیه­های  و  با استفاده از رویه­های کتابخانه  به ترتیب با عناوین  و  محاسبه شده است. بنابراین زمان عمومی اجرای گام پیش-پردازشی موازی، برابر مجموع دو زمان جزیی اجرای دو رویه فوق است. در تمام جداول، کوچکترین زمان اجرای موازی به صورت پر رنگ نمایش داده شده­است. در جداول 4-1 و 4-2 نتایج این آزمایش­ها را برای حالت ، ،  و  آورده شده­است. جداول 4-3 و 4-4 شامل نتایج آزمایش­ها

4- بررسی نتایج تجربی………………………………………………………………. 52

4-1- اجرای گام  بر روی شبکه ی پردازشی……………………………………….. 52

4-2- آزمایشهای عددی با مقادیر بهینهی پارامترهای پیش-پردازشی…………… 55

4-2-1- وابستگی به توزیع مقادیر منفرد……………………………………………… 56

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

فصل پنجم: نتیجه گیری و پیشنهادات

گام پیش پردازش در الگوریتم ژاکوبی استفاده از مقادیر بهینه در اندازه­ی بلوکی nb و توزیع چرخه­ای بهینه بر روی شبکه­ی پردازشی r×c با r,c≥1 که p=rc تعداد پردازنده­ها است، مورد نیاز می­باشد. بطور تجربی دریافته­ایم که مقادیر مطلوب برای خوشه­ای از گره­های محاسباتی، اندازه­ی بلوکی nb=100 و r≤c و r=max که p=rc است. این نتایج با نتایج به دست آمده در [26] با یک معماری متفاوت شبکه­ی پردازشی همخوانی دارد.با پارامترهای مطلوب برای پیش پردازش، آزمایشات عددی برای 6 توزیع متفاوت sv و 2 عدد شرطی انجام شدند. این آزمایشات را می­توان به دو گروه تقسیم نمود. در گروه اول، 4 گونه از الگوریتم ژاکوبی با درجه­بندی پویا تست شدند: بدون هیچ پیش پردازش، با پیش پردازش مستمل بر الگوریتم QRF با CP و با پیش پردازش QRF با CP و بدون آن و  بهره­گیری از LQF از فاکتور R. برای ماتریس­های با مقادیر منفرد مینیمال (ماکسیمال) چندگانه، استفاده از پارامترهای بهینه در گام پیش پردازش (الگوریتم QRF بدون CP با بهره­گیری LQF فاکتور (R می­تواند عملکرد بهتر یا قابل مقایسه­تری نسبت به تابع PDGESVDدر ScaLAPACK پیدا کند. برای توزیع­های دیگر sv، حتی QRFCP همراه با LQF گیری از فاکتور R منجر به کاهش چشمگیر nit نشد، تا جایی که پیش پردازش الگوریتم ژاکوبی با ترتیب پویا تقریباً 1.2 تا 1.3 برابر کندتر از روش PDGESVDدر ScaLAPACK بود.

5-2- پیشنهاد برای کارهای آینده

الگوریتم پیشنهادی برای ماتریس­های با ابعاد بزرگ بسیار کارآمد بوده و سرعت محاسبه مقادیر منفرد را به طور قابل توجهی افزایش می­دهد. اما همان­گونه که اشاره شد اگرچه این الگوریتم در مورد ماتریس­های کوچک نیز عملکرد بهتری نسبت به واحد محاسبه مرکزی کامپیوتر دارد، اما با توجه به افزوده شدن سخت افزاری مانند هسته پردازشی گرافیکی و فراخوانی متغیرها به حافظه آن به عنوان عیب، نمود بیشتری پیدا می­کند. به عبارت دیگر  trade-off بین سخت­افزار به کار رفته و حجم ماتریس وجود دارد که باید درنظر گرفته شود. به­عنوان کار آینده پیشنهاد می­گردد، الگوریتمی طراحی شود که بتواند به صورت خودکار حجم محاسبات را تخمین زده و نیاز یا عدم نیاز به انتقال محاسبات به واحد پردازش گرافیکی را تشخیص دهد. ضمن این که با هر دو واحد پردازشی سازگار باشد و هر قسمت از محاسبات را که لازم باشد به صورت هوشمند به واحد محاسبات موازی انتقال دهد.

5- نتیجه گیری و پیشنهادات………………………………………………………. 65

5-1- نتیجه گیری……………………………………………………………………. 65

5-2- پیشنهاد برای کارهای آینده………………………………………………….. 66

منابع………………………………………………………………………………….. 67

 

ABSTRACT

Linear algebra is the branch of mathematics concerning vector spaces and linear mappings between such spaces. It includes the study of lines planes, and subspaces, but is also concerned with properties common to all vector spaces. The singular value decomposition (SVD) is a factorization of a real or complex matrix. It has many useful application signal processing and statistics. Formally, the singular value decomposition (SVD) is a decomposition of a matrix in three factor.  Jacobi SVD method is a useful method to calculate SVD of a matrix. jacobi algorithm is one of the earliest method to calculate SVD. jacobi algorithm changes a rectangular matrix in to a diagonal matrix using a sequence of rotation matrices. This method can calculate singular values with high accuracy. Mention should be made that using this method perse can leads to a low performance. Using QR pre-Processing can result in a high performance.



بلافاصله بعد از پرداخت به ایمیلی که در مرحله بعد وارد میکنید ارسال میشود.


فایل pdf غیر قابل ویرایش

قیمت25000تومان

خرید فایل word

قیمت35000تومان