بخشی از مقاله
چکیده
دراین مقاله برای حل دستگاه معادلات خطی Ax=b با ماتریس ضرایب اسپارس و بزرگ و متقارن A، تجزیه LU با اصلاح تکراری - LUIR - با تجزیه LU با حل مستقیم - LUDS - که هیج گونه داده تکراری ندارد مقایسه می شود با آزمایشهای عددی بررسی می کنیم که استفاده از شیوه ماتریس اسپارس با LUIRممکن است هر دو زمان اجرایی و حافظه مورد نیاز را کاهش دهد. در این کار، ورودیهای جدید را با استفاده از توانهای ماتریس بولین تقلیل می دهیم که با ساختار مطابقت کند و یک روش ذخیره سازی اقتصادی را برای دستگاه جدید توسعه می دهیم که در تجزیه تعداد زیادی ورودی جدید وجود نداشته باشد .استفاده از استراتژی توانهای ماتریس بولین - PBS - که سعی می کند این ترمیم و تبدیل را انجام داده و اسپارس بودن آنرا کنترل کند. و در پایان با استفاده از نتایج عددی نتیجه می گیریم که فرآیند اصلاح تکراری ممکن است بعنوان یک انتخاب موثر در نرم افزار برای حل دستگاههای معادلات اسپارس خطی مورد استفاده قرار گیرد .
دستگاه معادلات خطی زیر را در نظر بگیرید.
Ax b - 1 -
در آن A بزرگ،اسپارس،ونامنفرد از مرتبه n n می باشد.و b و x بردارهای ستونی داده شده از مرتبه n می باشد. روشهای مستقیم معمولاً برای حل دستگاه - 1 - بکار می رود. زیرا آنها اغلب سیستماتیک وپیچیده هستند.یک راه حل برای حل دستگاه - 1 - را مورد بحث قرار میدهیم.این راه حل بکاربردن تجزیه ناقص LU می باشد.در صورتی که L ماتریس پائین مثلثی و U یک ماتریس بالا مثلثی است از این رو دستگاه - 1 - می تواند در دو مرحله با استفاده از جایگذاری پیشرو در Ly b و با استفاده از جایگذاری پسرو در Ux y حل شود.از آنجایی که تجزیه LU ی A بر اساس حذفی گاؤس می باشد.بنابراین، فرایند این تجزیه داده های جدید نامیده می شود.ابتدا عناصر صفر A در طول مراحل حل غیر صفر می شود واین بدان معنی است که ماتریسهای U , L زیاد اسپارس نیستند. از این رو باید ورودیهای جدید را چک کرد تا پراکندگی A مشخص گردد.
به هر حال وقتی که A متقارن است ورودیهای جدید میتوانند با استفاده از حذف یا روش درختی به حداقل برسند1]و[3 هدف ازاین کار حل - - 1 وحفظ وذخیره کردن زمان CPU و فضای حافظه می باشد.در این کار، ورودیهای جدید را با استفاده از توانهای ماتریس بولین تقلیل می دهیم که با ساختار A مطابقت کند و یک روش ذخیره سازی اقتصادی را برای دستگاه جدید توسعه می دهیم که در فاکتور گیری تعداد زیادی ورودی جدید وجود نداشته باشد. بالاخره، ماتریس A درون این ساختار ذخیره ها تجزیه می شود.تجزیه ناقص LU با استفاده از توان ماتریس برای کاهش داده های جدید انتخاب می شود زیرا آن مجاز می کند جوابهای تکراری از x را برای مقادیر متفاوت b بدون فاکتور گیری مجدد بکار ببریم ومحیطی را فراهم می سازد که در آن مرور مرحله به مرحله بکار گیری روش آسانتر باشد.
.2 روش ذخیره
مدلی که در اینجا داده شده است یک روش اجرای جهت دار است که در آن درایه های غیر صفر سطر به سطر ذخیره شده اند با هر سطردرایه های غیر صفر با ترتیب صعودی اندیس ستونی ذخیره شده اند . برای تشخیص درایه های هر سطر لازم است بدانیم که سطر از کجا شروع میشود چطور آن اجزای غیر صفر زیادی را شامل می شود و در چه ستونی درایه های غیر صفر قرار گرفته اند. برای ذخیره کردن ماتریس داده شده A با روش ذخیره غیر فشرده نیاز به سه آرایه - ردیف - تک بعدی IA ,JA ,VA به طولn+1,na,na هست که n تعداد سطر هاو na کل تعداد درایه های غیر صفر در ماتریس A می باشد . آرایهVA شامل اجزای غیرصفر A می باشدکه سطر به سطر ذخیره شده اند.JA
شامل اندیس ستونی می باشد که متناظر با اجزای غیر صفری در آرایش IA,VA و شامل n+1 نشانگر - اشاره گر - می باشد که سطرهارا همانطوریکه در زیر شرح داده شده اند از اجزای غیر صفر در آرایش VA محدود می کند.
