چکیدهجبر خطّی شاخهای از ریاضیات است که به بررسی و مطالعۀ ماتریسها، بردارها، فضاهای برداری (فضاهای خطّی)، تبدیلات خطی، و دستگاههای معادلات خطی میپردازد. در جبر خطی، الگوریتم SVD یک تجزیه از ماتریس حقیقی یا مختلط با کاربردهای فراوان و مفید در پردازش سیگنال و آمار است. الگوریتم SVD یک تکنیک برای تجزیه یک ماتریس به ضرب سه فاکتور میباشد. روشژاکوبی یکی از اولین الگوریتمها جهت اجرایی کردن SVD می باشد، که یک ماتریس مستطیل شکل را به یک ماتریس قطری با استفاده از دنبالهای از چرخشهای ابتدایی کاهش میدهد. این روش میتواند مقادیر منفرد را با دقت بالا پیدا کند. لازم به ذکراست که بعضی از روشها جهت یافتن مقادیر منفرد، عملکرد پایینی دارند. بنابراین بایستی به روشهایی با عملکرد بالا روی آورد. روش تجزیه مرحلهای QR یکی از الگوریتمهای عمومی و قابل کاربرد در این زمینه است که با انجام یک پیشپردازش در آن میتوان عملکرد اجرایی بالایی را بهدست آورد.کلمات کلیدی: تجزیه مقادیر منفرد SVD، الگوریتم ژاکوبی، پیش پردازش QR، پردازش موازیفهرست مطالبعنوان صفحهچکیدهد فصل اول: کلیات1- کلیات.. 31-1- مقدمه. 31-2- کارهای صورت گرفته توسط دیگر محققان. 5 فصل دوم:تعاریف و الگوریتم ها2- تعاریف و الگوریتم ها82-1- تعاریف پایه. 82-2- تجزيه ماتریس ها بر اساس مقادير منفرد. 92-2-1- مقادير منفرد. 92-2-2- تجزيه مقادير منفرد. 102-2-3- محاسبه دترمینان و معکوس یک ماتریس... 112-4- ترتیب دوره ای الگوریتم ژاکوبی (Cyclic Schemes)162-5- طرح بلوکی ژاکوبی با ترتیب دورهای.. 172-6- پردازش موازی الگوریتم بلوکی ژاکوبی.. 192-6-1- الگوریتم. 202-6-2- الگوریتم. 242-7- ترتیب پویا در الگوریتم بلوکی موازی ژاکوبی.. 242-7-1- الگوریتم موازی ژاکوبی – بلوکی با ترتیب دینامیک.. 27 فصل سوم: بررسی روشهای پیشنهادی3- بررسی روشهای پیشنهادی.. 303-1- پیش پردازش های موثر در الگوریتم ژاکوبی.. 303-1-1- انواع پیش- پردازش و پس- پردازش الگوریتم ژاکوبی.. 313-1-1-1- تجزیهی با محورگیری ستونی.. 313-1-1-2- تجزیهی اختیاری از عامل .. 323-2- نتایج بررسی اولین گروه از آزمایشها333-2-1- نتایج تجربی مربوط به ماتریس ها با توزیع مقادیر منفرد مینیمال چندگانه. 353-2-2- حالت توزیع مقادیر منفرد به صورت دنباله هندسی.. 393-3- ساختار عامل (عامل ( و اثر آن بر سرعت همگرایی پیش-پردازشها403-4- بهبود عملکرد پیش-پردازشها با بکارگیری توزیع دادهای بهینه. 46 فصل چهارم: بررسی نتایج تجربی4- بررسی نتایج تجربی.. 524-1- اجرای گام بر روی شبکه ی پردازشی.. 524-2- آزمایشهای عددی با مقادیر بهینهی پارامترهای پیش-پردازشی.. 554-2-1- وابستگی به توزیع مقادیر منفرد. 56 فصل پنجم: نتیجه گیری و پیشنهادات5- نتیجه گیری و پیشنهادات.. 635-1- نتیجه گیری.. 635-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-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 باشد.