الگوریتم کاتهیل مکی

در جبر خطی عددی، الگوریتم کاتهیل مکی الگوریتمی برای تغییر دادن یک ماتریس خلوت (که کم پشتی متقارن دارد) به یک ماتریس نواری با پهنای باند کوچک است.Recommendations for ship hull surface representation , page 6E. 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

 الگوریتم 
به‌طور خلاصه، اگر ماتریس مد نظر را ماتریس مجاورت متناظر با یک گراف در نظر بگیریم، الگوریتم کاتهیل مکی نودهای گراف را به گونه ای نامگذاری می‌کند که ماتریس مجاورت گراف حاصل نواری باشد. نامگذاری نودها به این صورت است که با نودی که کمترین درجه را دارد آغاز می‌کنیم و با استفاده از یک الگوریتم جستجوی اول سطح در هر مرحله نودی که کمترین درجه را دارد و قبلاً نامگذاری نشده‌است را نامگذاری می‌کنیم. در پایان ماتریس مجاورت را با استفاده از گراف حاصل می‌سازیم که ماتریسی نواری است.

 جستارهای وابسته 
 پهنای باند ماتریس
 ماتریس خلوت

 منابع 

رده:الگوریتم‌های گراف
رده:نظریه ماتریس‌ها
رده:ماتریس‌های تنک