عنوان                                                                                                                صفحه

چکیده ‌د

 

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

1- کلیات.. 3

1-1- مقدمه. 3

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

 

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

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

 

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

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- نتایج تجربی مربوط به ماتریس ها با توزیع مقادیر منفرد مینیمال چندگانه. 35

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

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

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

 

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

 

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

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

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

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

 

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

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

5-1- نتیجه گیری.. 63

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

منابع. 65

 

 

 

فهرست جدول­ها

عنوان                                                                                                                صفحه

جدول 3-1- نتایج آزمایش ماتریس هاس خوش – حالت با مقادیر منفرد مینمال چندگانه. 36

جدول 3-2- نتایج آزمایش ها برای ماتریس های بد – جالت با مقادیر منفرد مینیمال چندگانه  39

جدول 3-3- پیش-پردازشها برای ماتریسهای خوش-حالت با توزیع مقادیر منفرد به صورت دنباله هندسی   40

جدول 3-4- پیش-پردازشها برای ماتریسهای بد-حالت با توزیع مقادیر منفرد به صورت دنباله هندسی   40

جدول4-1- نتایج سرعت در گام پیش-پردازش مربوط به و  تعداد    54

جدول 4-2- نتایج سرعت در گام پیش-پردازش مربوط به و   تعداد . 54

جدول 4-3- نتایج سرعت در گام پیش-پردازش مربوط به و   تعداد . 54

جدول 4-4- نتایج سرعت در گام پیش-پردازش مربوط به و   تعداد . 54

جدول 4-5- نتایج برای ماتریسها از مرتبه 4000 با  و process grid . 58

جدول 4-6- نتایج برای ماتریسها از مرتبه 4000 با  و process grid . 59

جدول4-7- نتایج برای ماتریسها از مرتبه 8000 با  و process grid . 59

جدول4-8- نتایج برای ماتریسها از مرتبه 8000 با  و process grid . 59

 فهرست شکل­ها

عنوان                                                                                                                صفحه

شکل  3-1- بخشی از زمان  که صرف پیش-پردازش، پس-پردازش وارتباطات نقطه به نقطه­ای بین پردازنده­ها در  با  و توزیع مقادیر منفرد مینیمال چندگانه می­ شود. 37

شکل  3-2- ساختار یک گراف وزن دارد کامل وقتی که ترتیب پویا غیر موثر است. قسمت اصلی نرم فروبنیوس غیر قطری ماتریس  بر روی اولین بلوک سطری متمرکز می­ شود، بنابراین تمام یالهای متلاقی با رأس  ‘سنگین’ می باشند (خطوط کلفت)، بقیه یالها ‘سبک’ می باشند (خطوط نازک) 44

شکل3-3- یک مرحله از تجزیه . 47

 

 

فصل اول

1- کلیات

1-1- مقدمه

جبر خطّی شاخه­ای از ریاضیّات است که به بررسی و مطالعه ماتریس­ها، بردارها، فضاهای برداری، تبدیل­های­ خطی و دستگاه­های معادله­های خطّی می ­پردازد. علاوه بر کاربردهای فراوان جبر خطی در زمینه­هایی از خود ریاضیات همانند آنالیز تابعی، هندسه تحلیلی و آنالیز عددی، استفاده­های وسیعی نیز در فیزیک، مهندسی، علوم طبیعی و علوم اجتماعی پیدا کرده است [19] [16].

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

یکی از مسائل عمومی عملیات ماتریسی تجزیه ماتریس[1] است. تجزیه ماتریس یک عمل فاکتورگیری[2] از ماتریس به صورت حاصلضرب چند عامل ماتریسی است. تجزیه­های ماتریسی مهم وپرکاربرد عبارتند از:  تجزیهLU ماتریسی[3]، تجزیه چولسکی ماتریس[4]، تجزیه QR ماتریس[5]، تجزیه  EVDماتریس[6]، تجزیه قطبی ماتریس[7] وتجزیه مقادیر منفرد ماتریس[8] یا  .SVD

درجبر خطی، الگوریتم SVD یک تجزیه از ماتریس حقیقی یا مختلط است که از ابزارهای قدرتمند باکاربردهای فراوان، مفید و تاثیرگذار در علوم پایه، فنی مهندسی و همچنین در پردازش سیگنال وآمار است. الگوریتم SVD یک تکنیک برای تجزیه یک ماتریس به ضرب سه فاکتور می‌باشد.

الگوریتم ژاکوبی یکی از اولین الگوریتم­ها جهت اجرایی کردن SVD است. الگوریتم ژاکوبی یک ماتریس مستطیلی را به یک ماتریس قطری با بهره گرفتن از دنباله­ای از ضرب ماتریس­های چرخشی[9] تبدیل می­ کند. این روش می ­تواند مقادیر منفرد را با دقت بالا پیدا کند. لازم به ذکر است به کار بردن این روش به تنهایی خود عملکرد پائینی دارد، بنابراین باید به سمت روش­هایی با عملکرد بالاتری روی آورد. روش تجزیه مرحله­ ای QR یکی از این
الگوریتم­های عمومی وکاربردی در این زمینه است که با انجام پیش­ پردازش QR می­توان عملکرد اجرایی بالایی را به دست آورد. اساس مهم­ترین روش­های مدرن پیاده سازی الگوریتم SVD، کاهش ماتریس به شکل قطری با بهره گرفتن از تبدیل­های متعامد است. یکی از مزیّت­های تجزیه مرحله ای QR، قابلیّت حل مسائل با دقت و همگرایی بالا می باشد [29] و [9] .

روش­های استاندارد SVD، در بسته­های   LINPACKو LAPACK پیاده سازی شده ­اند. در این پایان نامه ، ما قصد استفاده از ابزارهای موازی نرم افزار MATLAB را داریم که در ادامه، مزیّت­های آن­را نسبت به نرم­افزارهای مشابه جهت موازی­سازی و معماری ساختار موازی به اختصار توضیح خواهیم داد.

توسعه روش پیش پردازش مرحله­ ای QR در الگوریتم ژاکوبی موازی می ­تواند منجر به پیاده­سازی بهینه الگوریتم SVD گردد. این روش ابتکاری می ­تواند در آنالیز و بهینه سازی داده ­ها کاربردهای فراوانی داشته باشد.

 

[1] Matrix decomposition

[2] Factorization

[3] Lu deomposition