الگوریتم کاتهیل مکی
در جبر خطی عددی، الگوریتم کاتهیل مکی الگوریتمی برای تغییر دادن یک ماتریس خلوت (که کم پشتی متقارن دارد) به یک ماتریس نواری با پهنای باند کوچک است.[۱][۲][۳]
الگوریتم[ویرایش]
به‌طور خلاصه، اگر ماتریس مد نظر را ماتریس مجاورت متناظر با یک گراف در نظر بگیریم، الگوریتم کاتهیل مکی نودهای گراف را به گونه ای نامگذاری می‌کند که ماتریس مجاورت گراف حاصل نواری باشد. نامگذاری نودها به این صورت است که با نودی که کمترین درجه را دارد آغاز می‌کنیم و با استفاده از یک الگوریتم جستجوی اول سطح در هر مرحله نودی که کمترین درجه را دارد و قبلاً نامگذاری نشده‌است را نامگذاری می‌کنیم. در پایان ماتریس مجاورت را با استفاده از گراف حاصل می‌سازیم که ماتریسی نواری است.
جستارهای وابسته[ویرایش]
- پهنای باند ماتریس
- ماتریس خلوت
منابع[ویرایش]
- ↑ Recommendations for ship hull surface representation, page 6
- ↑ E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.
- ↑ J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981