— -فایل منابع علمی مقاله-منابع تحقیق-268)

سـپاسـگـزاری
حال که توفیق جمع آوری و نگارش این مجموعه را یافته‏ام، بر خود واجب می‏دانم صمیمانهترین مراتب قدردانی و سپاس خود را خدمت جناب آقای دکتر عبدالعزیز عبدالهی که همیشه برایم استاد علم و اخلاق خواهند بود تقدیم نمایم. همچنین از زحمات جناب آقای دکتر غلامحسین ارجائی و جناب آقای دکتر محمد حسن شیر دره حقیقی کمال تشکر را دارم. از درگاه خداوند متعال سلامتی و بهروزی این عزیزان را مسئلت مینمایم.

توسعه روش تجزیه مرحلهایQR در الگوریتم ژاکوبی بلوکی موازی SVD و کاربردهای آن
به وسیله
قیس مصلحی دهویی
چکیدهجبر خطّی شاخه‌ای از ریاضیات است که به بررسی و مطالعۀ ماتریس‌ها، بردارها، فضاهای برداری (فضاهای خطّی)، تبدیلات خطی، و دستگاه‌های معادلات خطی می‌پردازد. در جبر خطی، الگوریتم SVD یک تجزیه از ماتریس حقیقی یا مختلط با کاربردهای فراوان و مفید در پردازش سیگنال و آمار است. الگوریتم SVD یک تکنیک برای تجزیه یک ماتریس به ضرب سه فاکتور میباشد. روش ژاکوبی یکی از اولین الگوریتمها جهت اجرایی کردن SVD می باشد، که یک ماتریس مستطیل شکل را به یک ماتریس قطری با استفاده از دنبالهای از چرخشهای ابتدایی کاهش میدهد. این روش میتواند مقادیر منفرد را با دقت بالا پیدا کند. لازم به ذکراست که بعضی از روشها جهت یافتن مقادیر منفرد، عملکرد پایینی دارند. بنابراین بایستی به روشهایی با عملکرد بالا روی آورد. روش تجزیه مرحلهای QR یکی از الگوریتمهای عمومی و قابل کاربرد در این زمینه است که با انجام یک پیشپردازش در آن میتوان عملکرد اجرایی بالایی را بهدست آورد.
کلمات کلیدی: تجزیه مقادیر منفرد SVD، الگوریتم ژاکوبی، پیش پردازش QR، پردازش موازی

فهرست مطالب
عنوان صفحه
TOC \o "1-3" \h \z \u چکیده PAGEREF _Toc419026995 \h ‌دفصل اول: کلیات1- کلیات PAGEREF _Toc419026998 \h 31-1- مقدمه PAGEREF _Toc419026999 \h 31-2- کارهای صورت گرفته توسط دیگر محققان PAGEREF _Toc419027000 \h 5فصل دوم:تعاریف و الگوریتم ها2- تعاریف و الگوریتم ها PAGEREF _Toc419027003 \h 82-1- تعاریف پایه PAGEREF _Toc419027004 \h 82-2- تجزیه ماتریس ها بر اساس مقادیر منفرد PAGEREF _Toc419027005 \h 92-2-1- مقادیر منفرد PAGEREF _Toc419027006 \h 92-2-2- تجزیه مقادیر منفرد PAGEREF _Toc419027007 \h 102-2-3- محاسبه دترمینان و معکوس یک ماتریس PAGEREF _Toc419027008 \h 112-4- ترتیب دوره ای الگوریتم ژاکوبی (Cyclic Schemes) PAGEREF _Toc419027009 \h 162-5- طرح بلوکی ژاکوبی با ترتیب دورهای PAGEREF _Toc419027010 \h 172-6- پردازش موازی الگوریتم بلوکی ژاکوبی PAGEREF _Toc419027011 \h 192-6-1- الگوریتم PAGEREF _Toc419027012 \h 202-6-2- الگوریتم PAGEREF _Toc419027013 \h 242-7- ترتیب پویا در الگوریتم بلوکی موازی ژاکوبی PAGEREF _Toc419027014 \h 242-7-1- الگوریتم موازی ژاکوبی – بلوکی با ترتیب دینامیک PAGEREF _Toc419027015 \h 27فصل سوم: بررسی روشهای پیشنهادی3- بررسی روشهای پیشنهادی PAGEREF _Toc419027018 \h 303-1- پیش پردازش های موثر در الگوریتم ژاکوبی PAGEREF _Toc419027019 \h 303-1-1- انواع پیش- پردازش و پس- پردازش الگوریتم ژاکوبی PAGEREF _Toc419027020 \h 313-1-1-1- تجزیهی QR با محورگیری ستونی PAGEREF _Toc419027021 \h 313-1-1-2- تجزیهی اختیاری LQ از عامل R PAGEREF _Toc419027022 \h 323-2- نتایج بررسی اولین گروه از آزمایشها PAGEREF _Toc419027023 \h 333-2-1- نتایج تجربی مربوط به ماتریس ها با توزیع مقادیر منفرد مینیمال چندگانه PAGEREF _Toc419027024 \h 353-2-2- حالت توزیع مقادیر منفرد به صورت دنباله هندسی PAGEREF _Toc419027025 \h 393-3- ساختار عامل R (عامل (L و اثر آن بر سرعت همگرایی پیش-پردازشها PAGEREF _Toc419027026 \h 403-4- بهبود عملکرد پیش-پردازشها با بکارگیری توزیع دادهای بهینه PAGEREF _Toc419027027 \h 46فصل چهارم: بررسی نتایج تجربی4- بررسی نتایج تجربی PAGEREF _Toc419027030 \h 524-1- اجرای گام QRLQ بر روی شبکه ی پردازشی PAGEREF _Toc419027031 \h 524-2- آزمایشهای عددی با مقادیر بهینهی پارامترهای پیش-پردازشی PAGEREF _Toc419027032 \h 554-2-1- وابستگی به توزیع مقادیر منفرد PAGEREF _Toc419027033 \h 56فصل پنجم: نتیجه گیری و پیشنهادات5- نتیجه گیری و پیشنهادات PAGEREF _Toc419027036 \h 635-1- نتیجه گیری PAGEREF _Toc419027037 \h 635-2- پیشنهاد برای کارهای آینده PAGEREF _Toc419027038 \h 64منابع PAGEREF _Toc419027039 \h 65

فهرست جدولها
عنوان صفحه
TOC \h \z \t "Title" \c جدول 3-1- نتایج آزمایش ماتریس هاس خوش – حالت با مقادیر منفرد مینمال چندگانه PAGEREF _Toc419027040 \h 36جدول 3-2- نتایج آزمایش ها برای ماتریس های بد – جالت با مقادیر منفرد مینیمال چندگانه PAGEREF _Toc419027041 \h 39جدول 3-3- پیش-پردازشها برای ماتریسهای خوش-حالت با توزیع مقادیر منفرد به صورت دنباله هندسی PAGEREF _Toc419027042 \h 40جدول 3-4- پیش-پردازشها برای ماتریسهای بد-حالت با توزیع مقادیر منفرد به صورت دنباله هندسی PAGEREF _Toc419027043 \h 40جدول4-1- نتایج سرعت در گام پیش-پردازش مربوط به mode=1و n=4000تعداد p=8 PAGEREF _Toc419027044 \h 54جدول 4-2- نتایج سرعت در گام پیش-پردازش مربوط به mode=3و n=4000 تعداد p=8 PAGEREF _Toc419027045 \h 54جدول 4-3- نتایج سرعت در گام پیش-پردازش مربوط به mode=1و n=8000 تعداد p=16 PAGEREF _Toc419027046 \h 54جدول 4-4- نتایج سرعت در گام پیش-پردازش مربوط به mode=3و n=8000 تعداد p=16 PAGEREF _Toc419027047 \h 54جدول 4-5- نتایج برای ماتریسها از مرتبه n=4000 با k=101 و process grid 2×4 PAGEREF _Toc419027048 \h 58جدول 4-6- نتایج برای ماتریسها از مرتبه n=4000 با k=108 و process grid 2×4 PAGEREF _Toc419027050 \h 59جدول4-7- نتایج برای ماتریسها از مرتبه n=8000 با k=101 و process grid 4×4 PAGEREF _Toc419027052 \h 59جدول4-8- نتایج برای ماتریسها از مرتبه n=8000 با k=108 و process grid 4×4 PAGEREF _Toc419027054 \h 59 فهرست شکلها
عنوان صفحه
TOC \h \z \t "Subtitle" \c شکل 3-1- بخشی از زمان Tp که صرف پیش-پردازش، پس-پردازش وارتباطات نقطه به نقطهای بین پردازندهها در [QRFCP, SVD(R)] با k=10 و توزیع مقادیر منفرد مینیمال چندگانه میشود. PAGEREF _Toc419027056 \h 37شکل 3-2- ساختار یک گراف وزن دارد کامل وقتی که ترتیب پویا غیر موثر است. قسمت اصلی نرم فروبنیوس غیر قطری ماتریس R بر روی اولین بلوک سطری متمرکز میشود، بنابراین تمام یالهای متلاقی با رأس V1 'سنگین' می باشند (خطوط کلفت)، بقیه یالها 'سبک' می باشند (خطوط نازک) PAGEREF _Toc419027057 \h 44شکل3-3- یک مرحله از تجزیه QRF PAGEREF _Toc419027058 \h 47
فصل اولکلیات
1- کلیات1-1- مقدمهجبر خطّی شاخهای از ریاضیّات است که به بررسی و مطالعه ماتریسها، بردارها، فضاهای برداری، تبدیلهای خطی و دستگاههای معادلههای خطّی میپردازد. علاوه بر کاربردهای فراوان جبر خطی در زمینههایی از خود ریاضیات همانند آنالیز تابعی، هندسه تحلیلی و آنالیز عددی، استفادههای وسیعی نیز در فیزیک، مهندسی، علوم طبیعی و علوم اجتماعی پیدا کرده است [19] [16].
برای به کار بردن دانش جبر خطی در علوم تجربی، فیزیک و مهندسی، که همگی لازم به انجام محاسبات عددی در آزمایشها و تحلیل دادهها هستند، نیاز به توسعه شاخهای به نام جبر خطی عددی وجود دارد. جبر خطی عددی دانش مطالعه بر روی الگوریتمهای عددی جهت محاسبات جبر خطی بوده که مهمترین آنها عملیات ماتریسی برروی کامپیوتر است. عملیات ماتریسی پایه و اساس بسیاری از محاسبات مهندسی از قبیل پردازش تصویر، سیگنال، مخابرات، محاسبات مالی، علوم مهندسی مواد، بیولوژی و... است.
یکی از مسائل عمومی عملیات ماتریسی تجزیه ماتریس است. تجزیه ماتریس یک عمل فاکتورگیری از ماتریس به صورت حاصلضرب چند عامل ماتریسی است. تجزیههای ماتریسی مهم وپرکاربرد عبارتند از: تجزیهLU ماتریسی، تجزیه چولسکی ماتریس، تجزیه QR ماتریس، تجزیه EVDماتریس، تجزیه قطبی ماتریس وتجزیه مقادیر منفرد ماتریس یا .SVD
درجبر خطی، الگوریتم SVD یک تجزیه از ماتریس حقیقی یا مختلط است که از ابزارهای قدرتمند باکاربردهای فراوان، مفید و تاثیرگذار در علوم پایه، فنی مهندسی و همچنین در پردازش سیگنال وآمار است. الگوریتم SVD یک تکنیک برای تجزیه یک ماتریس به ضرب سه فاکتور می‌باشد.
الگوریتم ژاکوبی یکی از اولین الگوریتمها جهت اجرایی کردن SVD است. الگوریتم ژاکوبی یک ماتریس مستطیلی را به یک ماتریس قطری با استفاده از دنبالهای از ضرب ماتریسهای چرخشی تبدیل میکند. این روش میتواند مقادیر منفرد را با دقت بالا پیدا کند. لازم به ذکر است به کار بردن این روش به تنهایی خود عملکرد پائینی دارد، بنابراین باید به سمت روشهایی با عملکرد بالاتری روی آورد. روش تجزیه مرحلهای QR یکی از این الگوریتمهای عمومی وکاربردی در این زمینه است که با انجام پیش پردازش QR میتوان عملکرد اجرایی بالایی را به دست آورد. اساس مهمترین روشهای مدرن پیاده سازی الگوریتم SVD، کاهش ماتریس به شکل قطری با استفاده از تبدیلهای متعامد است. یکی از مزیّتهای تجزیه مرحله ای QR، قابلیّت حل مسائل با دقت و همگرایی بالا می باشد [29] و [9] .
روشهای استاندارد SVD، در بستههای LINPACKو LAPACK پیاده سازی شدهاند. در این پایاننامه، ما قصد استفاده از ابزارهای موازی نرم افزار MATLAB را داریم که در ادامه، مزیّتهای آنرا نسبت به نرمافزارهای مشابه جهت موازیسازی و معماری ساختار موازی به اختصار توضیح خواهیم داد.
توسعه روش پیش پردازش مرحلهای QR در الگوریتم ژاکوبی موازی میتواند منجر به پیادهسازی بهینه الگوریتم SVD گردد. این روش ابتکاری میتواند در آنالیز و بهینه سازی دادهها کاربردهای فراوانی داشته باشد.

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

فصل دومتعاریف و الگوریتم ها
2- تعاریف و الگوریتم ها2-1- تعاریف پایهدر این بخش به برخی از مفاهیم پایهای مورد نیاز در محاسبات ماتریسها اشاره شده است [4]:
تعریف 2-1- اگرAϵ نرم فروبینیوس به صورت |A|F نشان داده می‌شود و عبارت است از:
(2-1-1) AF=i=1mj=1naij212تعریف2-2- ماتریس A یک ماتریس متقارن میباشد اگر A=AT.
تعریف2-3- ماتریس A یک ماتریس هرمیتی میباشد اگر A=AH.
قضیه: اگر A یک ماتریس هرمیتی باشد، آنگاه تمام مقادیر ویژه آن حقیقی میباشد. بعلاوه ماتریس متعامد مانند U موجود است به طوری که : D =UAUH یک ماتریس قطری است.
تعریف2-4- به ماتریس هرمیتی A یک ماتریس معین مثبت گویند. هرگاه به ازای هر بردار غیر صفر
x∈Cn داشته باشیم:
xHAx>0تعریف 2-5- به ماتریس هرمیتی A یک ماتریس شبه معین مثبت گویند. هرگاه به ازای هر بردار غیرصفر x∈Cn داشته باشیم:
xHAx≥0قضیه 2-2- فرض کنید A∈Mm,n و B∈Mm,n دو ماتریس باشند. آنگاه مقادیر ویژه غیر صفر ماتریسهای AB و BA یکسان میباشند.
قضیه2-3- برای هر ماتریس A∈Mm,n(C) ماتریس AHA ،یک ماتریس هرمیتی است و دارای مقادیر ویژه حقیقی نامنفی میباشد.
قضیه2-4- فرض کنید A∈Mm,n .آنگاه گزارههای زیر هم ارزند:
الف- ماتریسهای AHA و AAH هرمیتی میباشند، پس با استفاده از ماتریسهای متعامد قطری پذیرند.
ب- مقادیر ویژهAAH حقیقی نامنفیاند، بهطوریکه مقادیر ویژه غیرصفر آنها با مقادیر ویژهی غیر صفر AHA برابرند.
قضیه2-5- اگر AϵRm×n یک ماتریس حقیقی باشد، آنگاه ماتریسهای متعامد
U=u1,⋯,u2ϵRm×m و V=v1,⋯,v2ϵRn×n وجود دارند بهطوری که
D=UTAV=diagσ1,⋯,σpϵRm×n و p=minm,nدر آن اعداد σ1≥σ2≥⋯≥σp≥0 مقادیر منفرد A و برای هر مقدار منفرد σi بردارهای ui و vi به ترتیب بردارهای منفرد چپ و راست A میباشند.
2-2- تجزیه ماتریس ها بر اساس مقادیر منفرد
تعریف 2-6- جهت رسیدن به تجزیهی مقادیر منفرد ماتریس A باید به مطالعهی مقادیر ویژهی ماتریسAAH و بردارهای ویژهی ماتریس AAH بپردازیم.
2-2-1- مقادیر منفردمقادیر منفرد ماتریسA عبارتند از جذر مقادیر ویژهی ماتریس AAH که با σi(A) نمایش میدهیم، به عبارت دیگر
(2-2-1)σiA=λi(AAH)=λi(AHA)و میتوان نوشت :
σ1A≥σ2A≥⋯≥σrA>σr+1A=⋯=σminm,nA=0در جایی که r رتبه ماتریس A می‌باشد.
حال تجزیه مقادیر منفرد یک ماتریس را بیان میکنیم:
2-2-2- تجزیه مقادیر منفرد
یکی از روشهای تجزیه ماتریسها، تجزیه بر اساس مقادیر منفرد است. در این روش یک ماتریس مانند Am×n را می توان به صورت زیر تجزیه کرد:
A=UDVHکه در آن Um×m=[u1 ⋯ um] و Vn×n=[v1 ⋯ vn] ماتریسهای متعامد هستند و بهترتیب ماتریسهای منفرد چپ و راست نامیده میشود و ستونهای ماتریسUm×m از بردارهای ویژه یکا متعامد ماتریسAHA تشکیل میشوند، همچنین Dm×nیک ماتریس مستطیلی قطری با مقادیر نامنفی حقیقی بر روی قطر اصلی است عناصر غیر صفر بر روی قطر ماتریس Dm×n ، مقادیر منفرد ماتریس Am×n است.
به این نمونه فاکتورگیری، تجزیه مقادیر منفرد ماتریس A گفته میشود. ستون های U و V به ترتیب بردارهای منفرد راست و چپ ماتریس A است. هر ماتریس مختلط A با رتبه‌ی r را میتوان به صورت تجزیه فوق نوشت. برای یافتن این ماتریسها به صورت زیر عمل میکنیم:
AAHماتریس با استفاده از ماتریس متعامد Uقطریپذیر است. درنتیجه UΛUH =AAH که U=[u1,…,um] و Λ=diag(λ1,…,λr,o,…,o) و ستونهای ماتریس U در روابط زیر صدق میکند.
(2-2-2)AAH.ui=λiui i≤r AAH.ui=0 i>r اگر قرار دهیم σi=λi و:
(2-2-3)vi=σi-1AHui i≤rآنگاه بردارهای v1,v2,⋯,vr یک پایه یکا متعامد برای AHA است.
حال ما به تکمیل پایه AHA به فضای Cn میپردازیم. جهت این کار هستهی ماتریس AHA را در نظر میگیریم. اگر vr+1,⋯,vn یک پایه یکا متعامد هستهی ماتریس AHA باشد، آنگاه بردارهای v1,⋯,vr,vr+1,⋯,vn یک پایه برای Cn می باشد و قرار دهیم:
V=v1,⋯,vnالگوریتمهای زیادی جهت محاسبهی تجزیه مقادیر منفرد توسط محققان توسعه داده شده است. مشهورترین الگوریتمهای تجزیه مقادیر منفرد استفاده از الگوریتم QR [17]و استفاده از الگوریتم ژاکوبی[12][8] است که به جهت پایداری عددی قابل توجه میباشند. از لحاظ محاسباتی الگوریتم QR دارای سرعت بالاتری نسبت به الگوریتم ژاکوبی کلاسیک می باشد. امّا اخیراً الگوریتم ژاکوبی به دلیل سادگی و امکان پردازش موازی از جذّابیّت بیشتری برخوردار شده است و همچنین جیمز دیمل در[14]نشان داد که الگوریتم ژاکوبی ممکن است دقیقتر از الگوریتم QR هم باشد.
2-2-3- محاسبه دترمینان و معکوس یک ماتریس
از تجزیه مقادیر منفرد یک ماتریس میتوان برای محاسبه دترمینان و معکوس آن ماتریس استفاده نمود. برای یک ماتریس مربعی An×n دترمینان به صورت زیر بهدست میآید:
( 2-2-4) A=±i=1nσiبا توجه به اینکه ماتریسهای U و V متعامد هستند داریم:
A=UDVH=UDVH=±1D±1=±D=±i=1nσiبرای یک ماتریس مربعی با رتبه کامل An×n شبه معکوس ماتریس به صورت زیر تعریف میشود:
A†=UDVH-1=VT-1D-1U-1=VD-1UHکه در آن D-1=diag1σ1,1σ2,⋯,1σn .
2-3- الگوریتم کلاسیک ژاکوبی
در الگوریتم کلاسیک ژاکوبی[1]، ماتریس حقیقی متقارن A از مرتبهی n×n با استفاده از تبدیلات متوالی به شکل:
(2-3-1)Ak+1=JkTAkJk k=0,1,⋯به یک ماتریس قطری متحوّل میشود. در جایی که A0=A و Jk یک ماتریس چرخشی در صفحهی (p,q) با زاویهی چرخش θبه شکل زیر است :
p q

p
q
(2-3-2) Jp,q,θ= 1⋯0⋮⋱⋮0⋯c⋯0⋯‌⋮‌⋯s⋯0⋮0⋮‌⋮0⋯-s⋮‌⋮⋱⋮‌⋯c⋯‌⋮⋱⋮0⋮0⋯ 0⋯0⋯1(در طول این فصل c=cosθ وs=sinθ ). با ضرب ماتریس اصلی در ماتریس چرخشی در مرحله k، عناصر غیر قطری apq(k) (و همچنین aqp(k)) صفر میشود که این تبدیلات، تنها بر روی سطر و ستون p و q تاثیر میگذارد. این چرخش به چرخش ژاکوبی مشهور است و ماتریس J همان ماتریس گیونز میباشد. هدف روش ژاکوبی کلاسیک ساختن دنبالهای از ماتریس Ak و Jk به شکلی است که:
(2-3-3)limk→∞Ak=D و limk→∞J1J2⋯Jk=VDآن در که یک ماتریس قطری بوده و بر روی قطر اصلی آن مقادیر ویژه ماتریس A ، V یک ماتریس متعامد بوده که ستونهای آن بردارهای ویژه ماتریس A میباشند.
گام اصلی در الگوریتم ژاکوبی کلاسیک که به آن زیر مساله (p,q) گفته میشود شامل سه مرحله است.
تعیین زوج (p,q) بهطوری که : 1≤p<q≤n
محاسبهی کسینوس – سینوس (c,s) بهطوری که:
(2-3-4)app(k+1)apq(k+1)aqp(k+1)aqq(k+1)=cs-scTapp(k)apq(k)aqp(k)aqq(k)cs-scقطری باشد.
به روزآوری Ak با Ak+1=JkTAkJk، Jk ماتریس چرخشی معرفی شده در روابط فوق است.
از آنجا که در تبدیلات متعامد نرم فروبنیوس ثابت میماند پس:
(2-3-5)appk2+aqqk2+2apqk2=appk+12+aqqk+12+2apqk+12=app(k+1)2+aqq(k+1)2بعلاوه، اگر نرم فروبنیوس غیر قطری ماتریس A را با off(A) نشان دهیم داریم:
(2-3-6)offA=i=1nj=1j≠inaij2ما مشاهده خواهیم کرد که:
(2-3-7)offAk+12=Ak+1F2-i=1naiik+12=AkF2-i=1naiik2+appk2+aqqk2-appk+12-aqqk+12=offAk2-2apqk2 (2-3-8)
و با استفاده از این روش در هر مرحله از الگوریتم ژاکوبی دنباله به سمت یک ماتریس قطری میگراید. تعداد چرخشهای لازم جهت تبدیل ماتریس به یک ماتریس قطری از لحاظ نظری نامتناهی است، زیرا نمیتوانیم در حالت کلی یک معادلهی چند جملهای در تعداد گام متناهی حل کنیم. [33]به هر حال ما میتوانیم این چرخش را پس از رسیدن به یک دقت مورد نظر قبول به اتمام برسانیم. در الگوریتم ژاکوبی کلاسیک در هر مرحله، آن عنصر غیر قطری ماتریس AK صفر میشود که دارای بزرگترین قدرمطلق است، یعنی:
apq=maxaij,i≠jاگر این عنصر در مختصات (p,q) قرار داشته باشد آنگاه Jk متناظر چرخشی در صفحهی (p,q) با زوایهی انتخابی Ɵ ایجاد میکند که apq(k) به صفر کاهش یابد.
بعد ازتعیین جفت (p,q) به محاسبهی زوج کسینوس – سینوس (c,s) احتیاج است که زیر ماتریس 2×2 زیر را قطری میکند.
(2-3-9)app(k)apq(k)aqp(k)aqq(k)در رابطهی فوق که یک فاکتور گیری (Schur) است میتوان با شرایط گفته شده جهت صفر شدن عناصر غیر قطری جفت (c,s) را بهصورت زیر محاسبه نمود:
(2-3-10)0=app(k+1)=apq(k)c2-s2+app(k)-aqq(k)csاگر apq(k)=0، آنگاه :
(c,s)=(1,0)اگر apq(k)≠0 و app(k)≠aqq(k)، آنگاه:
(2-3-11)2apq(k)aqq(k)-app(k)=2csc2-s2=tan2θبا توجه به :
(2-3-12) tan2θ=2cosθsinθcos2θ-sin2θ , θ≠kπ±π4 , k=0,1,⋯زوایهی چرخشی Ɵ عبارت است از :
(2-3-13)θ=12arctan2apq(k)aqq(k)-app(k)در حقیقت جهت محاسبات عددی نیازی به تعیین زوایه θ نیست و ما علاقه داریم فقط مقادیر s و c را تعیین کنیم. اگر قرار دهیم:
(2-3-14)τ=2apq(k)aqq(k)-app(k) و x=scآنگاه معادلهی فوق را میتوان به صورت زیر نوشت:
(2-3-15)x2+2τx-1=0که دارای دو ریشه است و جهت پایداری توصیه میشود کوچکترین مقدار یا :
(2-3-16)x=sign(τ)τ+1+τ2 استفاده گردد، که:
(2-3-17)c=11+x2 , s=xcدر خاتمه از زیر مساله (p,q) به روز رسانی Ak باAk+1=JkTAkJk صورت میگیرد. همانطور که در قبل گفتیم در این رویه تنها سطر و ستون q,p از ماتریس Ak تاثیر میپذیرد.
الگوریتم وقتی خاتمه پیدا میکند که،off(VTAV)≤tol . بعد از خروج مؤفق VTAV شامل مقادیر ویژه ماتریس A بوده و ماتریس متعامد V ماتریس بردارهای ویژه A است.
تعریف 2-7- به یک بررسی کامل کلیه مقادیر غیر قطری aij جهت صفر شدن در بدنه حلقه تکرار الگوریتم ژاکوبی، یک چرخه میگویند.
هر چرخه در حلقه تکرار شامل N=12n(n-1) به روزآوری داده ها است. اگر A یک ماتریس متقارن و apq بزرگترین عنصر غیر قطری از لحاظ قدر مطلقی باشد آنگاه:
(2-3-18)i=1nj=1j≠inaij2≤n2-napq2و در نتیجه:

دانلود پایان نامه ارشد- مقاله تحقیق

 برای دانلود فایل کامل به سایت منبع مراجعه کنید  : homatez.com

یا برای دیدن قسمت های دیگر این موضوع در سایت ما کلمه کلیدی را وارد کنید :

 

(2-3-19)2apq(k)2=off(Ak)2-off(Ak+1)2از آنجا که:
(2-3-20)off(Ak)2≤2Napq(k)2به این نتیجه میرسیم:
(2-3-21)off(Ak+1)2≤1-1Noff(Ak)2و با قرار دادن A0=A و استفاده از استقراء داریم:
(2-3-22)off(Ak)2≤1-1Nkoff(A0)2که براساس رابطه فوق، الگوریتم ژاکوبی کلاسیک با سرعت خطی همگرا است. اگر k=rN آنگاه :
(2-3-23)off(ArN)2≤1-1NrNoffA02<e-roffA02 نامساوی بالا نشان میدهد که برای r>2ln1ε داریم:
(2-3-24)off(ArN)2<ε2offA02رابطهی فوق یک همگرایی قابل ملاحظهای با سرعت کم برای الگوریتم ژاکوبی کلاسیک را نشان میدهدکه در مراحل توسعهی بعدی این سرعت همگرایی بهبود مییابد. شونهیج[25] نشان داد که برای k به اندازه کافی بزرگ یک ثابت μ موجود است به طوریکه :
(2-3-25)off(ArN)≤μoffAk2که به این رفتار همگرایی مجانبی درجه دوم گویند.
انتخاب زاویهی θ نقش مهمّی در همگرایی الگوریتم ژاکوبی کلاسیک دارد. ویلکینسون [34] با یک آنالیز دقیق نشان داد که انتخاب زاویهی θ در بازهی -π4<θ≤π4 تضمینی برای همگرایی به ماتریس قطری است.
توسعه دقیقی برای پیشگویی تعداد کل چرخههای لازم جهت همگرایی الگوریتم ژاکوبی با یک دقت فرضی دلخواه انجام نشده است. با این حال برنت و لوک [7] با یک استدلال ابتکاری گفتند که تعداد چرخههای لازم متناسب با log(n) است.
2-4- ترتیب دوره ای الگوریتم ژاکوبی (Cyclic Schemes)در الگوریتم ژاکوبی کلاسیک جستجوی بزرگترین عنصر غیر قطری منجر به صرف هزینهی زمانی میشود. از به صرفه بودن الگوریتم میکاهد، زیرا در صورتی که ماتریس اصلی متقارن باشد در هر چرخه تعداد 12n(n-1) جستجو احتیاج است که وقتیn بزرگ باشد باعث کاهش سرعت عملیات میشود.
این اشکال روش الگوریتم ژاکوبی کلاسیک، انگیزهای برای توسعه طرح ترتیب دورهای به وجود آورد. مشهورترین مثالهای طرح ترتیب دورهای الگوریتم ژاکوبی، دوره ای سطری (Row cyclic) و دورهای ستونی (column cyclic) است که به وسیله Forsythe و Henrici در [34]تحلیل و بررسی شده است.
در طرح دورهای سطری ژاکوبی به عنوان مثال میتوانیم تعداد N جفت (p,q) جهت محاسبه را به صورت حرکت روی یک سطر به صورت زیر انتخاب کنیم:
(2-4-1){1,2,1,3,…,1,n;2,3,2,4,…,2,n;…;(n-1,n)}2-5- طرح بلوکی ژاکوبی با ترتیب دورهای
یکی از مهم‌ترین احتیاجهای بهره‌برداری با راندمان بالا در محاسبات کامپیوتری این است که از منابع حافظه‌های غیر‌ضروری اجتناب کنیم. این ایده به استفاده از طرح ژاکوبی بلوکی منجر شده است که جهت کاهش عملیات انتقال داده‌ها مفید می‌باشد.
به خوبی شناخته شده است که استفاده از طرح بلوکی برای سیستم‌ها با تعداد پردازشگر اندک میتواند مفید باشد. [6][5]
الگوریتم‌ عددی ژاکوبی به صورت تکراری مساله 2×2 مقدار ویژه یا مقادیر منفرد را حل می‌کند. الگوریتم بلوکی ژاکوبی مساله مقدار ویژه یا مقادیر منفرد را با اندازه‌ی بزرگتر حل می‌کند. به عنوان مثال شکل بلوکی ماتریس متقارن An×n را به صورت زیر میتوان نوشت :
(2-5-1)A=A11A12A21A22⋯A1l ⋯ ⋮⋮Al1Al2 ⋮⋯All, Ai,j ϵ Rr×rالگوریتم ژاکوبی بلوکی با ترتیب استاتیک و نوع پردازش سریالی، ماتریس A را به صورت بلوکی l×l کهl عامل بلوک است برش داده می‌شود. هسته عملیات شامل عملیات SVD برای یک ماتریس قطعه‌ای 2×2 به صورت:
(2-5-2)Sij=AiiAijAjiAjjاست که برای یک جفت مفروض (i,j) که i,j=0,1,…,l-1 و i≠j ماتریس‌های متعامد Xij و Yij طوری محاسبه می‌شود که:
(2-5-3)Dij=XijHSijYijیک ماتریس بلوکی قطری به شکل:
(2-5-4)Dij=Jii00Jjjاست. به تکرار عمل قطری سازی برای تمام جفتهای (i,j) که i,j=0,1,…,l-1 و i≠j یک چرخه بلوکی گفته می شود. تعداد زیر مساله‌ها برای حل در یک چرخه برای یک ماتریس متقارن برابر L=l(l-1)/2 است.
شرط خروج و اتمام کل فرایند به صورت:
(2-5-5)FA,l=i,j=0,i≠jl-1AijF2<ϵاست ومساله Sij در صورتی بایستی حل شود که :
(2-5-6)FSij,l=AijF2AjiF2≥δدر جایی که، δ=ε⁄L دقت دلخواه معین است.
فرض کنید که یک ترتیب دوره ای، i1,j1,i2,j2,⋯,iL,jLبرای حل زیر‌مساله‌های Sij داده شده است. Ai ، Ui و Vi به ترتیب ستون‌های قطعه‌ای از A، U و V باشند آنگاه الگوریتم ژاکوبی دوطرفه بلوکی با پردازش سریال به صورت زیر است.
U=Im, V=In while FA,l≥ϵ do for k=1 to L do i,j=ik,jk if FSij,l≥δ then ⊳computation of Xij and Yij by SVD of Sij SVDSij→ Xij,Yij ⊳update of block columns Ai,Aj=Ai,Aj.Yij Ui,Uj=Ui,Uj.Xij Vi,Vj=Vi,Vj.Yij for t=0 to l-1 do ⊳update of block rows AitAjt=XijH ∙AitAjt end for end if end forend whileحال اجازه دهید با دقت بیشتری به جزئیات محاسبه‌ی SVD به وسیله الگوریتم سریال ژاکوبی دو طرفه بلوکی بنگریم. نخست، تبدیلات متعامد به وسیله‌ی ماتریس‌های Xij و Yij تغییری در نرم فروبنیوس ماتریس اصلی A ایجاد نمی‌کنند، دوم، F(A,l) که مقدار آن باAijF+AjiF در معادله‌ی فوق تعریف شده است بعد از هر تکرار در یک چرخه بلوکی کاهش می‌یابد.با توجه به تعریف، سرعت همگرایی الگوریتم هم‌ارز سرعت کاهش نرم فروبنیوس غیر‌قطری بلوک‌ها است.
2-6- پردازش موازی الگوریتم بلوکی ژاکوبیمیتوان ماتریسهای A ، U و V را به شکل بلوکی ستونیA=[A1,…,Al] ، U=[U1,…,Ul] و V=[V1,…,Vl] در نظر گرفت. در حالت بلوکی یک ستون شامل یک ماتریس n×r است.
اگر U یک ماتریس بلوکی متعامد با عناصر r×r به شکل
(2-6-1)U= U11U12U21U22 باشد آنگاه میتوان از ماتریس متعامد بلوکی U ، ماتریس ژاکوبی (چرخشی) بلوکی J(i,j,U)=(Zij) تولید کرد. این ماتریس یک ماتریس بلوکی l×l با عناصرr×r است که در همه جا همانی بوده به جز: Zii=U11 ، Zij=U12، Zji=U21 و Zjj=U22 . ساختار ماتریس دوران ژاکوبی در صفحه(i,j) به صورت:
(2-6-2)J=Irr⋮ ⋯⋱O⋯ O⋯ O ⋮ ⋮ ⋮O⋯Zii⋯ Zij⋯O⋮O⋮O ⋯ ⋯⋮Zji⋮O ⋱ ⋮ ⋮⋯ Zjj⋯O ⋯ ⋮O ⋱⋯ ⋮Irrاست . کلید اینکه الگوریتم بلوکی با ترتیب دورهای را سریعتر کنیم این است که بدون برخورد و تداخل در یک معماری مناسب موازی از پردازندهها، آن را به صورت پردازش موازی اجرا کنیم. بهعنوان مثال اگر l=8 ، آنگاه زیر مسالههای (2و1)، (4و3) و (6و5)، (8و7) یک ترتیب غیر تداخلی برای 4 پردازنده است که میتوانیم 4 زیر مساله و به روزآوریهای A ، U و V را در یک زمان مشابه انجام دهیم.
در حالت کلی l می‌توانیم رویه زیر را اجرا کنیم :
2-6-1- الگوریتم فرض کنید که A=A1,…,Al و U=[U1,…,Ul] ، V=[V1,…,Vl] که هر ستون بلوکی از مرتبهی n×r است. فرض کنید که lزوج است و تعداد N=l2 پردازنده PN,….,P1 موجود است بهطوریکه پردازنده‌ی Pi حاوی ستون‌های بلوکی 2i-1 و 2i از A، U و V است.
اگر Pi این الگوریتم را برای i=1 تا N انجام دهد، آنگاه:
A≔J1,2U(1⋯Jk-1,k,UNTAJ1,2,V1⋯Jk-1,k,VNU≔U diagU1,⋯,UNV≔V diag(V1,⋯,VN)که U(i) و V(i) ماتریس‌های متعامد از مرتبه 2r×2r می‌باشد که زیر مساله (2i-1,2i) را حل میکند.
زیر مساله (2i-1,2i) به روش گفته شده در الگوریتم ترتیب دورهای حل می‌شود.
فرض کنید که U(i) و V(i) نتیجه ماتریس‌های متعامد باشد:
A2i-1,A2i≔A2i-1,A2iViU2i-1,U2i≔U2i-1,U2iUiV2i-1,V2i≔V2i-1,V2iViU(i) به بقیه پردازنده‌ها منتقل می‌شود.
جمع‌آوری‌ ماتریسهای متعامد زیر از بقیه پردازندهها :
U1,⋯,Ui-1,Ui+1,⋯,UNحال بهروزآوری :
A2i-1,A2i≔diagU1,⋯,UNA2i,A2i-1در اینجا به هماهنگی بین پردازنده‌ها و تبادل ستونهای بلوکی بین آنها جهت ادامه روند احتیاج است. یعنی در خلال این رویه، ستون‌های بلوکی بین پردازنده‌ها توزیع می‌شود.
برای فهم بهتر فرض کنید که A یک ماتریس به صورت بلوکی 8×8 باشد، l=8 تعداد 28 جفت غیر قطری از اندیسها در هفت مجموعه ژاکوبی (مجموعههای دوران) را به صورت زیر میتوان نوشت:
I. 1,2 3,4 5,6 7,8II. 1,4 2,6 3,8 5,7III. 1,6 4,8 2,7 3,5IV. 1,8 6,7 4,5 2,3V. 1,7 5,8 3,6 2,4VI. 1,5 3,7 2,8 4,6VII. 1,3 2,5 4,7 6,8می‌بینیم که در هر مرحله چهار زیر مساله SVD بدون تداخل حل می‌شود. این نمونه که از چپ به راست و از بالا به پایین بهصورت ردیفی مرتب شده است، یک مثال از ترتیب موازی است. استنتاج این مساله به این صورت است که فرض کنید 8 نفر با هم در مسابقات شطرنج به نحوی شرکت می‌کنند که هر شخص با شخص دیگر دقیقاً یکبار مسابقه می‌دهد. این مسابقهها می‌تواند به صورت چهار مسابقه‌ی همزمان برگزار شود و کل مسابقات در هفت مرحله (تکرار) انجام می‌شود. در هر مرحله (تکرار با مجموعه ژاکوبی) بازیکن‌ها که در اینجا ستون‌های بلوکی هستند به جداول مجاور (پردازنده‌های مجاور) منتقل می‌شوند.
Round I: 12345678Round II: 14263857Round III:16482735و الی آخر ...
ابتدا با مقیم کردن ماتریس A در پردازنده‌های P4,…,P1 به صورت زیر شروع میکنیم:
P1A11A12A21A31A41A51A61A71A81A22A32A42A52A62A72A82 P2A13A14A23A33A43A53A63A73A83A24A34A44A54A64A74A84 P3A15A16A25A35A45A55A65A75A85A26A36A46A56A66A76A86 P4A17A18A27A37A47A57A67A77A87A28A38A48A58A68A78A88با استفاده از الگوریتم پارالل (2-6-1)، زیر مساله‌های (2و1)، (4و3)، (6و5) و (8و7) حل می‌شود.
جهت آماده‌سازی برای زیر مساله‌های مرحله دوم، یعنی (4و1)، (6و2)، (8و3) و (7و5)، ماتریس A را بین پردازنده‌ها به صورت زیر مجدداً بخش می‌کنیم:
P1A11A14A41A21A61A31A81A51A71A44A24A64A34A84A54A74 P2A12A16A42A22A62A32A82A52A72A46A26A66A36A86A56A76 P3A13A18A43A23A63A33A83A53A73A48A28A68A38A88A58A78 P4A15A17A45A25A65A35A85A55A75A47A27A67A37A87A57A77 مشاهده میکنیم که عناصر روی قطر اصلی تا آخر روی قطر اصلی جابهجا میشوند. توجه کنید که حل مساله همزمان (2و1)، (4و3)، (6و5) و (8و7) از لحاظ ریاضی معادل حل مساله های (4و1)، (6و2)، (8و3)، (7و5) در حالت بدون پس و پیش کردن ماتریس A است.
سپس ما الگوریتم (2-6-1) را بهکار می‌بندیم و باز ماتریس A را به روش گفته شده پس و پیش می‌کنیم. آنگاه برای پردازش مجموعه سوم ژاکوبی (مجموعه دوران) تنظیم می‌کنیم به طوری که زیر مساله های (6و1)، (8و4)، (7و2) و (5و3)، الی آخر ...
در حالتی که تعداد N پردازنده داشته باشیم، پس و پیش کردن ستونها به وسیله ماتریس جایگشت P از مرتبه n×n که (n=lr) به راحتی امکان پذیر است، به عبارت دیگر:
P=E1,E4,E2,E6,E3,E8,⋯,Ek-5,Ek,Ek-3,Ek-1که Ei ها ستون‌های بلوکی ماتریس همانی n×n می‌باشد و
In=E1,E2,⋯,El Ei∈Rr×r , n=lrبه طور خاص بعد از هر به کارگیری الگوریتم قبلی ستون‌های بلوکی 2i-1 و 2i از ماتریس PTAP در پردازندهی Pi ذخیره می‌شود. با توجه به این توضیحات، روی هم‌رفته این الگوریتم را خواهیم داشت:

2-6-2- الگوریتم فرض کنید A=[A1,…,Al] و U=[U1,…,Ul] و V=[V1,…,Vl] با V=U=I مفروض باشد. فرض کنید هر ستون بلوکی از مرتبه‌ی n×r و پردازندهی Pi حاوی دو ستون بلوکی 2i-1 و 2i از ماتریس‌های A، U و V برای i=1 تا N=l2 است. فرض کنید eps>0 . الگوریتم زیر ماتریس‌های متعامد U و V را طوری محاسبه می‌کند که:
OffUTAV≤espAFDo While OffA>espAF For rotationset=1 to N-1 Apply Algorithm 3.1 Perform the updates A≔PTAP , U≔UP , and V≔VP where P is given by 3.1. Note that this involves shuffling A, U, and V among the processors.‌2-7- ترتیب پویا در الگوریتم بلوکی موازی ژاکوبیاگر در یک زمان مشخص اقدام به صفر کردن عناصر غیر‌ قطری خاصی از ماتریس به صورت همزمان بکنیم، سرعت کاهش نرم فروبنیوس غیر‌قطری ماتریس افزایش می‌یابد. این ایده توسط م.بکا، گ.اسکاو م.واجترسیک[31] بررسی شده است که به اختصار به شرح آن می‌پردازیم.
در طرح ترتیب دینامیک در هر تکرار مجموعه‌ای از زیر‌مساله‌ها که با حل آنها بیشترین کاهش در نرم فروبنیوس غیر‌قطری رخ می‌دهد، انتخاب می‌شود. حل این مساله هم ارز حل مساله ماکسیمم – وزن تطابق کامل در نظریه گراف می‌باشد.
یک طرحی از الگوریتم حریص برای این منظور ارائه شده است که در هر مرحله بیشترین کاهش ممکن در نرم فروبنیوس ماتریس غیر‌قطری صورت گیرد.
اجازه دهید که تجویز ایستا بر صفر شدن بلوکهای غیر‌قطری را که ویژگیهای واقعی ماتریس را در نظر نمیگیرد را فراموش کنیم. در عوض با یک عامل بلوکی مفروض l ، در هر مرحله تکرار جفت (i,j) را طوری پیدا کنیم که مقدارArsF+AsrF برای r≠s روی تمام بلوکهای ماتریس بیشینه شود. متعاقباً با پیدا کردن این جفت (i,j) به صفر کردن Aij و Aji می‌پردازیم. در این حالت مطمئن هستیم که بعد از صفر کردن آنها بیشترین کاهش در نرم فروبنیوس غیر‌قطری رخ خواهد داد. مفهوم ترتیب پویا در واقع باز تعریف حالت بلوکی برای الگوریتم ژاکوبی عددی می‌باشد. در الگوریتم ژاکوبی عددی یک جستجو برای صفر‌کردن بیشترین مقدار عنصر غیر‌قطری وجود دارد. به‌هر‌حال برای یک ماتریس از مرتبه‌ی n×n یک جستجوی کامل برای یافتن بزرگترین مقدار عنصر غیر‌قطری از پیچیدگی O(n2) برخوردار است. این یک پیچیدگی بالایی است که پس از هر باید به جستجوی بزرگترین عنصر غیر‌قطری پرداخت. همانطور که قبلاً گفته شد در ابتدای سال 1960 ترتیب دوره‌ای سریال تا اکنون بکار برده می‌شود. در [31] نشان داده شد که بکار بردن جستجوی بزرگترین نرم فروبنیوس بلوکهای غیر‌قطری از پیچیدگی قابل قبولی برخوردار است.
می‌توان الگوریتم موازی را همراه با ترتیب پویا نیز به‌کار‌برد. در [3][2] بکا و اُکسا دو طرح موازی برای الگوریتم ژاکوبی بلوکی دو طرفه به کار بردند.
آنها گفتند که با داشتن تعداد P پردازنده می‌توان در حالت موازی تعداد P تکرار را با هم انجام داد. یک راه مناسب برای انجام این کار این است که دو ستون بلوکی ماتریس A به یک پردازنده اختصاص یابد.
آنها فاکتور بلوکی l=2p را انتخاب کردند. در یک مرحله از تکرار، اگر لازم باشد هر پردازنده SVD ماتریس محلی Sij را محاسبه نموده، عمل به روزآوری را با استفاده از Xij و Yij بر روی ستون‌های بلوکی انجام می‌دهد.
ماتریس Xij را به تمام پردازندهها ارسال میکند، تعداد p-1 ماتریس X** دریافت می‌کند، عمل به روزآوری بر روی داده‌های بلوک‌های مربوط با X** تحقق بخشیده می‌شود و در نهایت ستون‌های بلوکی در بین پردازنده‌ها مبادله می‌شوند. در استراتژیهای قبلی توزیع ستون‌های بلوکی همزمان دارای دو هدف بود. نخست اینکه طراحی یک الگوی مناسب برای ترتیب که تمام جفت‌های (i,j) در طول یک چرخه بلوکی مطابقت داشته و همچنین بتوان همزمان عملیات پردازش بر روی آنها را انجام داد. دوم اینکه ارتباط بین پردازنده‌ها از کدام توپولوژی برخوردار بوده و چطور به مبادلات بین پردازنده‌ها عناصر مورد نیاز بین پردازنده‌ها اقدام شود.
هدف‌ ما بررسی این است که بلوک‌های غیر‌قطری برای صفر شدن با هم مسابقه بدهند به صورتی که کدامین بلوک غیر‌قطری با صفر شدن به سرعت همگرایی کل کمک بیشتری می‌کند. در حالت سریال این الگو به راحتی امکان‌پذیر است. فرض کنید که ماتریس W یک ماتریس l×l است که عناصر آن نرم فروبنیوس بلوک‌های غیر‌قطری می‌باشد. براساس معیار خروج که :
(2-6-3)FA,l=i,j=0,i≠jl-1AijF2<ϵاست، با پیدا کردن مجموع عناصر W هم ارز بوده و انتخاب عنصر با مختصات (r,s) ،r≠s و r,s=0,1,…,l-1 که ArsF+AsrF بیشینه مقدار باشد، معادل انتخاب بزرگترین عنصر ماتریس W+WT است، آنگاه در حالت سری یک انتخاب (i,j) با شرط i≠j است بهطوریکه wij ماکسیمال باشد. در حالت موازی وضعیت پیچیده‌تر است. در یک مرحله از تکرار موازی تعداد P تکرار سریال اتفاق می‌افتد. اولاً می‌خواهیم تا حد ممکن بیشترین کاهش در نرم فروبنیوس غیر‌قطری ایجاد شود که این کار را می‌توان با نظریه گراف‌ها بوسیله مساله ماکسیمم -وزن در یک تطابق کامل بیان کرد.
یک تطابق کامل در گراف G(V,E) که V مجموعه رأسها و E مجموعه یالها است، تطابقی است که تمام راسهای گراف منحصراً به یک یال تطابق متعلق باشد. اگر w یک تابع حقیقی وزنی بر روی یالهای گراف G باشد ، آنگاه وزن تطابق مجموع وزن‌های یالهای آن تطابق می‌باشد. یک تطابق را تطابق ماکسیمم – وزن گویند. اگر وزن آن بیشترین وزن در بین تطابق‌های ممکن گراف باشد. همانطور که در CITATION Sch \l 1033 [24] نشان داده شده است وزن ماکسیمم را می‌توان با پیچیدگی زمانی OV∙E+V2∙logV یافت. مرور تاریخی حل مساله را میتوان در منابع CITATION Dem92 \l 1033 [25] و CITATION Rut66 \l 1033 [26] مطالعه کرد. یک گراف کامل وزن‌دار G(V,E)=KL که راسهای آن از 0 تا l-1 شماره‌گذاری شده وE=i,j|i<j و یال(i,j) دارای وزن wij=AijF+AjiF است.
ماکسیمم وزن تطابق کامل گراف با در نظر گرفتن (l=2p) با پیچیدگی O(p3) بدست میآید. وقتی که تقریب جواب مناسب باشد، می‌توان یک الگوریتم حریص ساده به کار برد. فرض کنید که یالها را با ترتیب وزنی نزولی مرتب کنیم. حال این دنباله را از چپ به راست پیموده و یک یال را در صورتی به تطابق اضافه می‌کنیم که اشتراک راسی با هیچکدام از یالهایی که قبلاً اضافه کرده ایم نداشته باشد. پیچیدگی این الگوریتم حریص برابر Op2∙logp است.
الگوریتم موازی برای پردازنده me که me=0,1,…,p-1 را می‌توان به صورت زیر نوشت:
2-7-1- الگوریتم موازی ژاکوبی – بلوکی با ترتیب دینامیک

در رویه AllGhather هر پردازنده ماتریس Xij را به تمام پردازنده‌های دیگر ارسال می‌کند، بهطوری‌که هر پردازنده یک آرایه از p ماتریس را نگه می‌دارد.
رویه ReOrderingComp ، ترتیب مقاصد جدید ستون‌های بلوکی را به صورتی که در یک پردازنده دلخواه قرار دارد را محاسبه می‌کند( dest1 وdest2) و محل جدید آنها را (tag1 و tag2) مشخص می‌سازد، با توجه به ماتریس وزن به روزآوری شده W ، رویههای send وrecive باید از نوع غیر بلوکی باشند تا از هر گونه وقفه و اختلال اجتناب شود. آرگومان tag تطابق ما بین فراخونی‌های send و recive مربوطه را فراهم می‌نماید.

فصل سومبررسی روشهای پیشنهادی
3- بررسی روشهای پیشنهادی3-1- پیش پردازش های موثر در الگوریتم ژاکوبی
در ادامه میخواهیم روشی را معرفی کرده و چگونگی افزایش سرعت الگوریتم ژاکوبی تحت تاثیر آن را بررسی نماییم. پیش از این دیدیم که الگوریتم ژاکوبی تا وقتی ادامه پیدا میکند که نرم فروبنیوس غیر قطری ماتریس اصلی به اندازهی کافی کوچک شود.
اساس روش ارائه شده بر این ایده استوار است که آیا میتوان با پیش پردازشهای مفیدی نرم فروبنیوس ماتریس را بر روی قطر اصلی ماتریس متمرکز نموده و از نرم فروبنیوس عناصر غیر قطری کاسته شده و در نهایت الگوریتم ژاکوبی با سرعت محاسباتی بالاتری انجام پذیرد؟
یک روش برای اینکه در نهایت تعداد تکرارهای کمتری در الگوریتم ژاکوبی داشته باشیم میتواند برمبنای یک پیش پردازش خوش فرم کننده استوار باشد. این خوش فرم کننده پیش پردازشی باید دارای این خصوصیت باشد که نرم فروبنیوس ماتریس A را تا حد امکان بر روی قطر اصلی متمرکز کند. در حالت ایدهال اگر نرم فروبنیوس ماتریس A تماماً بر روی قطر اصلی متمرکز باشد، روش ژاکوبی موازی قطعهای با یک تکرار به جواب میرسد. بنابراین متمرکز کردن نرم فروبنیوس ماتریس بر روی قطر اصلی و در نهایت کاستن تعداد تکرارهای روش ژاکوبی میتواند به عنوان یک هدف بررسی شود.
ارتباط بین عناصر قطر اصلی عامل R در تجزیهی QR ماتریس A (یا عناصر قطر اصلی عامل -L در فاکتورگیری LQ ماتریس A) با مقادیر منفرد ماتریس A توسط استوارت[28] مطالعه شده است. او به صورت تجربی نشان داد که بعد از فاکتورگیری QR با محور ستونی (QRFCP) و به صورت اختیاری فاکتورگیری LQ (LQF) از عامل R با محور ستونی یا بدون آن، قدر مطلق عناصر روی قطر اصلی ماتریس بالا مثلثی R یا پایین مثلثی L در حالت کلی می تواند تقریب مناسبی از مقادیر منفرد ماتریس A باشد.
چونکه مجموع مربعات مقادیر منفرد ماتریس برابر توان دوم نرم فروبنیوس ماتریس A میباشد، این میتواند به این معنا باشد که نرم فروبنیوس ماتریس بر روی قطر اصلی یا نزدیک آن متمرکز شده است.
3-1-1- انواع پیش- پردازش و پس- پردازش الگوریتم ژاکوبی3-1-1-1- تجزیهی QR با محورگیری ستونیهمانطور که در بالا گفته شد، ایده اصلی بکار بردن یک پیش پردازش در الگوریتم ژاکوبی، متمرکز کردن نرم فروبنیوس کل ماتریس تا حد امکان بر روی قطر اصلی ماتریس است. برای این منظور در ابتدا میتوان QRFCP بر روی ماتریس A انجام داد. این گام پیش پردازش یا همان فاکتورگیری QR با محورگیری ستونی را میتوان به صورت زیر انجام داد :
(3-1-1) AP=Q1Rکه P∈Rn×n ماتریس جایگشت، Q ∈Cm×n دارای ستونهای متعامد و R∈Cn×n یک ماتریس بالا مثلثی است.
در گام دوم با استفاده از الگوریتم ژاکوبی SVD ماتریس R محاسبه میشود. فرض کنید که SVDماتریس R به صورت زیر نمایش داده شود:
(3-1-2) R=U1DV1Hکه U1 وV1 ∋ Cn×n به ترتیب بردارهای منفرد راست و چپ ماتریسR و ماتریس قطری ∈Rn×n D شامل n مقدار منفرد به صورت σ1≥σ2≥…≥σn≥0 که مساوی مقادیر منفرد A است.
در آخر، جهت تعیین SVD ماتریس A ، A≡UDVH به گام پس–پردازش احتیاج است. با استفاده از روابط فوق:
(3-1-3)AP=Q1R(3-1-4)R=U1DV1H(3-1-5)AP=Q1U1DV1H(3-1-6)APV1=Q1U1Dکه با در نظر گرفتن روابط زیر:
U=Q1U1, V=PV1خواهیم داشت:
(3-1-7)A= UDVHهمانطور که از روابط فوق دیده میشود گام پس–پردازش اساساً شامل یک توزیع ضرب ماتریسی است. در اینجا میتوان جایگشت سطرهای ماتریس V1 را با جمع آوری در یک پردازنده و تعویض سطرهای آن، این عملیات را بدون ضرب ماتریسی PV1 انجام داد .
3-1-1-2- تجزیهی اختیاری LQ از عامل Rنوع دوم عملیات پیش-پردازشی و پس-پردازشی را مشابه حالت قبلی در گام اول، (QRFCP) انجام میدهیم. در ابتدا یک تجزیهی QR با محور گیری ستونی از ماتریس A میتوان انجام داد.
(3-1-8) AP=Q1Rدر گام دوم، تجزیهی LQ عامل (LQF)R بدون محورگیری ستونی انجام میشود بهطوری که:
(3-1-8)R=LQ2که L∈Cn×n یک ماتریس پایین مثلثی و Q2∈Cn×n یک ماتریس متعامد است. در این مرحله نرم فروبنیوس ماتریس A به مقدار بیشتری روی قطر اصلی متمرکز میشود. ک.وسلیش [15] سپس در مرحلهی سوم با استفاده از الگوریتم ژاکوبی SVD ماتریس L محاسبه می شود، به عبارت دیگر:
(3-1-9)L=U2DV2Hو در نهایت SVD ماتریس اصلی A که A=UDVH در مرحلهی پس–پردازش به صورت زیر محاسبه میشود:
(3-1-10)AP=Q1U2DV2HQ2سپس می توان نوشت:
(3-1-11)AP(Q2HV2)=Q1U2Dحال با قراردادن
(3-1-12) U=Q1U2 , V=P(Q2HV2) داریم:
(3-1-13)A=UDVH مشاهده میشود که در مرحله پس– پردازش دارای دو توزیع ضرب ماتریسی میباشیم.
آشکار است که پیش-پردازش نوع دوم که با یک مرحلهی اضافی LQF گیری از عامل R همراه است، در مقایسه با پیش-پردازش نوع اول از پیچیدگی زمانی و فضایی بالاتری برخوردار است .
در حالت کلی باید ببینیم که انواع پیش-پردازش موجود چقدر در سرعت عملیات تاثیر دارد. آیا بکار بستن الگوریتم ژاکوبی برای یافتن SVD ماتریس R یا L و در ادامه انجام مرحله پس-پردازش مقرون به صرفهتر از به کار بستن الگوریتم ژاکوبی بر روی خود ماتریس اصلی A است؟
جهت فهمیدن تاثیر انواع پیش-پردازشهای خوش فرم کننده بر روی الگوریتم موازی بلوکی ژاکوبی به بررسی بعضی از آزمایشات عددی در حالتهای مختلف مقادیر منفرد پرداختهایم.
3-2- نتایج بررسی اولین گروه از آزمایشهااولین گروه از آزمایشهایی که به بررسی نتایج آن پرداختهایم بر روی یک شبکه از پردازندههای موازی با نام «گیسبرگ» در دانشگاه سالزبورگ انجام شده است. [22] این شبکهی پردازشی که شامل بیست و پنج گره محاسباتی است، در یک آرایه مش 5×5 طرح بندی شده است. گرههای محاسباتی طبق استاندارد (SCI) با پهنای باند 385 MB/S با تاخیر زمانی کمتر از 4μs با یکدیگر در ارتباط بودهاند.
هر گره محاسباتی دارای 2GB حافظهی اصلی و دو عدد پردازشگر با سرعت 2.1GHZ است، که هر کدام از آنها دارای 64KB حافظهی کمکی بوده است. تمام گرههای محاسباتی دارای دقت ماشین ϵM≈1.11×10-16 که به صورت پیش فرض ثابت prec=10-13 تعداد پردازندههای p به صورت متغیر p=4,8,24,40 ، به مرتبه ماتریس مربعی حقیقی A وابسته است. ماتریسهای مورد آزمایش از مرتبه n=2000,4000,6000,8000 بودند.
در گروه اول، به بررسی سه نوع آزمایش انجام شده بر روی الگوریتم موازی ژاکوبی بلوکی مقادیر منفرد پرداختهایم. در نوع اول، از الگوریتم موازی بلوکی ژاکوبی(PTBJA) جهت پیدا کردن تجزیه مقادیر منفرد ماتریس A بدون هیچگونه پیش-پردازش استفاده شده است. نوع دوم، آزمایش تاثیر پیش-پردازش بر روی تجزیه مقادیر منفرد بلوکی ژاکوبی به این صورت بوده که ابتدا تجزیه QR همراه با محورگیری ستونی (QRFCP) ماتریس A محاسبه شده، پس از آن الگوریتم PTBJA بر روی عاملR اجرا شده و عملیات با پس-پردازش گفته شده پایان یافته است. این نوع از آزمایش با [QRFCP,SVDR] نمایش داده شده است. در نهایت نوع سوم آزمایش [QRFCP, LQ, SVD(L)]، ابتدا فاکتورگیری QR با محورگیری ستونی از ماتریس A (QRFCP) ، سپس تجزیه LQ عامل R بدون محورگیری ستونی (LQF) و در ادامه از الگوریتم (PTBJA) برای تجزیه عامل L استفاده شده است.
در تمام آزمایشها عناصر ماتریسهای مورد آزمایش به صورت تصادفی با عدد شرطی k و با توزیع مقادیر منفرد SVs=1=σ1≥σ2≥…≥σn=1k است. همچنین A=YDZT ، در جایی که Y و Z دو ماتریس تصادفی متعامد که عناصر آنها با توزیع نرمال N(0,1) است و D ماتریس قطری با مقادیر منفرد تعیین شده بر روی قطر اصلی آن است.
با توجه به عدد شرطی k، ماتریس خوش–حالت با عدد شرطی k=10 و ماتریسبد-حالت با عدد شرطی k=108 در نظر گرفته شده است. در تمام حالات مقادیر منفرد (SVs) ، در بازه [k-1,1] قرار دارند.
گروه اول آزمایشها، بر روی ماتریسهایی با دو نوع متفاوت توزیع مقادیر منفرد انجام شده است. در توزیع نوع اول، مقادیر منفرد ماتریسهای مورد آزمایش دارای مقادیر منفرد مینیمال چندگانه و به صورت σ1=1 و σ2=σ3=…=σn=k-1 است. در توزیع نوع دوم، مقادیر منفرد ماتریسها به صورت دنبالهای هندسی با σ1=1 و σn=k-11 هستند (به طوریکه تمام مقادیر منفرد دیگر متمایز و در همسایگی σn قرار دارند).مشهور است که محاسبه SVD ماتریسهایی با توزیع مقادیر منفرد مینیمال چندگانه، یا دستهبندی شده به صورت تصاعد هندسی و به طور خاص برای ماتریس های بد- فرم، در مقایسه با حالتی که ماتریس مقادیر منفرد مجزا دارد و همچنین خوش- فرم است پیچیدهتر است. [22]
در محاسبات عددی، از بسته های نرمافزاری استاندارد محاسبات عددی LAPACK و ScaLAPACK استفاده شده است. برای اجرای QRFCP و LQF به ترتیب از دو رویه PDGEQPF و PDGELQF در بسته نرم افزاری ScaLAPACK استفاده شده است.
قالب تمام جداول یکسان بوده و ستون اول مربوط به مرتبهی ماتریس مربعی است. همچنین ستون دوم به تعداد پردازنده استفاده شده در آزمایش اشاره دارد. پس از آن، نتایج آزمایشات، در قالب دو زیر ستون نوع آزمایش مشخص شده است. زیر ستون اول مربوط به تعداد گامهای تکرار موازی الگوریتم ژاکوبی (niter) جهت همگرایی با دقت مفروض است. زیر ستون دوم مربوط به زمان کلی اجرا (Tp) است. بهترین مقادیر TP برای هر مرتبه ماتریس به صورت پر رنگ مشخص شده است.
3-2-1- نتایج تجربی مربوط به ماتریس ها با توزیع مقادیر منفرد مینیمال چندگانه
در ابتدا به ارائه نتایج آزمایش ماتریسهای خوش-حالت با مقادیر منفرد مینیمال چندگانه میپردازیم که در جدول 1 جمع آوری شده است. در ستون آخر نسبت niter و TP محاسبه شده در دو روش نامگذاری شده با [SVD] و [QRFCP, SVD(R)] نشان داه شده است. کاهش مقدار niter با استفاده از QRFCP قابل توجّه است. مقدار niter برای روش [QRFCP, SVD(R)] با افزایش n به آهستگی افزایش مییابد. پس بنابراین با توجه به کاهش مقدار niter در روش [QRFCP, SVD(R)]، به وضوح این پیش-پردازش یک نقش ایده ال در این کاهش داشته و برای این نوع توزیع از ماتریسها مناسب است.
جدول 3-1- نتایج آزمایش ماتریس هاس خوش – حالت با مقادیر منفرد مینمال چندگانهPerformance for l= 2P,prec=10-13 , k=10, multiple minimal SV
n p SVDQRCP,SVD(R)Ratio niter Ratio Tp niterTp(s)niterTp(s)2000 4 170 1778.9 3 91.0 56.7 19.5
4000 8 452 6492.5 4 307.7 113.0 21.1
6000 24 1817 5367.6 6 369.3 302.8 14.5
8000 40 3289 7709.9 7 1273.2 469.0 6.1

به وضوح مشخص است با این مقدار کاهش در تعداد تکرارهای موازی الگوریتم بلوکی ژاکوبی (niter) ، اجرای نوع دوم پیش پردازش یعنی LQF گیری از فاکتور R توصیه نشده است. زیرا پیش پردازش QRFCP به اندازهی کافی niter را کاهش داده است.
یک مشاهدهی مورد توجّه دیگر، وقتی است که از n=4000 به n=6000 حرکت میکنیم و niter در حال افزایش است، مقدار TP با کاهش مواجه میشود.
این نتیجه را میتوان به اینصورت بیان کرد که، برای n=4000 و p=8 ، زیر مسالههای SVD بلوکی 2×2 با مرتبه بلوک 500×500 در هر پردازنده اجرا میشود، در صورتیکه برای n=6000 و p=24 زیر مسالههای SVD بلوکی 2×2 با مرتبه بلوک 250×250 است. با توجه به اینکه پیچیدگی زمانی مساله SVD به صورت O(n3) با توجه به الگوریتم SVD است، پس اگر بعد نصف باشد سرعت اجرای الگوریتم SVD در هر تکرار موازی هشت برابر است. به هر حال چونکه فاکتور بلوکی l =2p است و از l =16 به l =48 افزایش پیدا میکند، تعداد تکرارهای موازی بلوکی ژاکوبی نیز افزایش پیدا میکند[31]. در این حالت تقریباً چهار برابر، از niter=452 به niter=1817 رسیده است. بنابراین زمان کلی اجرای الگوریتم تقریبا نصف شده است. درواقع، همراهی افزایش هزینه مرحله پیش-پردازش و پس-پردازش (شکل 3-1 را مشاهده کنید) و هزینه زمانی ارتباطات نقطهای بین پردازندهها منجر به وقوع این عدد مشاهده شده در کاهش Tp شده است.
توجه داشته باشید مشابه این کاهش Tp با انتقال از n=4000 به n=6000 با حالت دیگر عدد شرطی و توزیع مقادیر منفرد نیز در جداول بعدی قابل مشاهده است.

شکل 3-1- بخشی از زمان Tp که صرف پیش-پردازش، پس-پردازش وارتباطات نقطه به نقطهای بین پردازندهها در [QRFCP, SVD(R)] با k=10 و توزیع مقادیر منفرد مینیمال چندگانه میشود.در مقابل با niter، کاهش Tp از مرتبهی یک بوده و دارای مقدار کمی است. دلیل این رفتار را میتوان با استفاده از شکل 1 نتیجهگیری کرد. برای تمام مرتبههای ماتریس، گام پیش پردازش( QRF همراه با محور گیری ستونی) بیشتر از %30 زمان Tp را به خود اختصاص میدهد و در حالتی که مرتبه ماتریس بیشتر از n=6000 می شود، این مرحله تقریباً %50 زمان Tp را به خود اختصاص میدهد. این نشان میدهد که استفاده از رویه بسته نرمافزاری ScaLAPACK برای QRF همراه با محورگیری ستونی(PDGEQPF)، کارایی مناسبی ندارد. (لااقل برای این شبکه پردازشی مورد آزمایش، مناسب نیست). به عبارت دیگر، با این همه کاهش مقدار در niter کاهش مقدار Tp در مقایسه با آن، قابل ملاحظه نیست، یا لازم است که یک الگوی دیگری از شبکه پردازشی و توزیع ماتریسی بلوکی طراحی شده که سرعت عملیات پیش-پردازش را بالاتر ببرد.
بخشی از زمان Tp در ارتباطات نقطهای بین پردازشگرها شامل عملیات جمع آوری U ، Σ و V از یک پردازنده سپری میشود. برای n=8000 و تعداد پردازنده p=40 این جمع آوری و تبادل دادهای بین پردازندهها بطور ناگهانی یک پرش زمانی ایجاد میکند، بطوریکه تقریباً %50 از زمان Tp را بخود اختصاص میدهد. این امکان وجود دارد که سیستم عامل روش دیگری را برای جمع آوری ستونها که در اینجا از مرتبه 8000 است و ذخیره سازیها ممیزها استفاده کند تا مرحله بهینهتر شود. از طرف دیگر توزیع ضرب ماتریسی مورد احتیاج در مرحله پس–پردازش بصورت بهینه و کارا به کار برده شده است. این زمان برای ماتریس از مرتبه n=8000 تقریباً برابر %7 Tp است.
نتایج این آزمایشها برای ماتریسهای بد-حالت با مقادیر منفرد مینیمال چندگانه در جدول 3-2 آورده شده است. وقتی که با ماتریسهای خوش-حالت مقایسه شود، یک نتیجه این است که برای روش [QRCP, SVDR] تعداد تکرارهای موازی (niter) بستگی زیادی به مقدار n دارد.
الگوی LQF گیری از عامل R به کاهش بیشتر عدد niter کمک می کند، اما دو تجزیهی متوالی از نوع QRFCP و LQF باعث میشود که از لحاظ پیچیدگی زمانی، این نوع کاربرد پیش-پردازش، مناسب نباشد.

جدول 3-2- نتایج آزمایش ها برای ماتریس های بد – جالت با مقادیر منفرد مینیمال چندگانهPerformance for l= 2P, prec=10-13 , k=108, multiple minimal SV
n p SVDQRCP,SVD(R)QRCP,LQ, SVD(L)niterTp(s)niterTp(s)niterTp(s)2000 4 59 832.9 11 163.5 7 153.1
4000 8 191 3308.8 26 547.9 15 609.8
6000 24 819 2791.8 72 632.6 47 842.9
8000 40 1512 5169.6 125 1811.0 79 1782.5
3-2-2- حالت توزیع مقادیر منفرد به صورت دنباله هندسیدر آزمایشهای بعدی حالت توزیع مقادیر منفرد به صورت دنباله هندسی در بازهی [k-1,1] با σ1=1 و σn=k-1 است. به طوری که مقادیر منفرد متمایز و در همسایگی σn قرار دارند. نتایج برای ماتریسهای خوش- حالت در جدول 3-2 آورده شده است. به طوری که مشاهده میشود، روشهای [QRFCP, SVD(R)] و [QRFCP, LQ, SVD(L)] قادر نیستند باعث کاهش زمان عمومی Tp اجرای الگوریتم موازی شوند، زیرا تعداد تکرارهای موازی niter که کاهش پیدا میکند تقریباً 10 الی 20 درصد است که برای پایین آوردن زمان کلی Tp کافی نیست. در جدول 3-4 نتایج آزمایشها برای ماتریسهای بد حالت آورده شده است. استفاده از [QRFCP, SVD(R)]، باعث کاهش تقریبی 5 تا 30 درصدی تعداد تکرارهای موازی niter شده است. که کاهش قابل توجهی نیست. برای n=6000 و n=8000، زمان اجرای موازی مناسبتر از زمانی است که SVD ماتریس بدون پیش–پردازش محاسبه میشود. بنابراین به کار گرفتن[QRFCP, LQ, SVD(L)] به این احتیاج دارد که تعداد تکرارهای موازی niter بیشتر کاهش پیدا کند. در نهایت در مقایسه با SVDماتریس A کاهش تقریبی 40 الی 50 درصدی در زمان Tp به وجود آورده است.
وقتیکه نتایج جدولهای 3-3 و 3-4 را با هم مقایسه میکنیم مشاهدهمیشود که روش [QRFCP, LQ, SVD(L)] در کاهش niter و Tp ماتریسهای بد-حالت موفقیت آمیزتر از ماتریسهای خوش-حالت است. چونکه در هر دو حالت مقادیر منفرد به تدریج از 1 به k-1 کاهش پیدا میکند و یک تفاوت آنچنانی ناگهانی بین مقادیر منفرد پیش نمیآید.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *