Band matrix
ریاضی میں، خاص طور پر میٹرکس تھیوری میں، بینڈ میٹرکس یا بینڈڈ میٹرکس ایک چھوٹا میٹرکس ہوتا ہے جس کی غیر صفر اندراجات ایک اخترن بینڈ تک محدود ہوتی ہیں، جس میں مرکزی اخترن اور دونوں طرف صفر یا اس سے زیادہ اخترن ہوتے ہیں۔ بینڈ میٹرکس بینڈوڈتھ رسمی طور پر، ایک این × این میٹرکس اے = (آئی، جے) پر غور کریں۔ اگر تمام میٹرکس عناصر ایک ترچھا سرحدی بینڈ کے باہر صفر ہیں جس کی حد کا تعین مستقل k1 اور k2 سے ہوتا ہے: تو مقدار k1 اور k2 کو بالترتیب اور کہا جاتا ہے۔ میٹرکس کا زیادہ سے زیادہ k1 اور k2 ہے ؛ دوسرے لفظوں میں، یہ نمبر k اس طرح ہے کہ اگر۔ مثال کے طور پر k1 = k2 = 0 کے ساتھ ایک بینڈ میٹرکس ایک اخترن میٹرکس ہے۔ k1 = k2 = 1 کے ساتھ ایک بینڈ میٹرکس ایک سہ رخی میٹرکس ہے۔ مثلث میٹرکس k1 = 0 کے لیے، k2 = n−1، ایک اوپری مثلث میٹرکس کی تعریف اسی طرح حاصل کرتا ہے، k1 = n−1 کے لیے، k2 = 0 ایک نچلا مثلث میٹرکس حاصل کرتا ہے۔ بینڈوتھ محدود ہونے پر بالائی اور نچلے ہیسنبرگ میٹرکس ٹوپلٹز میٹرکس ہوتے ہیں۔ بلاک ڈائیگنل میٹرکس شفٹ میٹرکس اور شیر میٹرکس اردن میں میٹرکس نارمل فارم ایک اسکائی لائن میٹرکس، جسے "متغیر بینڈ میٹرکس" بھی کہا جاتا ہے، بینڈ میٹرکس کی عمومی شکل لیمر میٹرکس کے الٹا مستقل سہ رخی میٹرکس ہوتے ہیں، اور اس طرح بینڈ میٹرکس ہوتے ہیں۔ عددی تجزیے میں، محدود عنصر یا محدود فرق کے مسائل سے میٹرکس کو اکثر بینڈ کیا جاتا ہے۔ اس طرح کے میٹرکس کو مسئلہ متغیرات کے درمیان جوڑے کی وضاحت کے طور پر دیکھا جا سکتا ہے۔ بینڈڈ پراپرٹی اس حقیقت سے مطابقت رکھتی ہے کہ متغیرات من مانی طور پر بڑے فاصلے پر جوڑے نہیں ہوتے ہیں۔ اس طرح کے میٹرکس کو مزید تقسیم کیا جا سکتا ہے۔ مثال کے طور پر، بینڈڈ میٹرکس موجود ہیں جہاں بینڈ کا ہر عنصر غیر صفر ہوتا ہے۔ یہ اکثر اس وقت پیدا ہوتے ہیں جب یک جہتی مسائل کو نظر انداز کیا جاتا ہے۔ اعلی طول و عرض میں مسائل بھی بینڈڈ میٹرکس کا باعث بنتے ہیں، ایسی صورت میں بینڈ خود بھی کم ہوتا ہے۔ مثال کے طور پر، مربع ڈومین پر ایک جزوی تفریق مساوات (مرکزی اختلافات کا استعمال کرتے ہوئے) میٹرکس طول و عرض کے مربع جڑ کے برابر بینڈوتھ کے ساتھ ایک میٹرکس حاصل کرے گی، لیکن بینڈ کے اندر صرف 5 اخترن غیر صفر ہوتے ہیں۔ بدقسمتی سے، اس طرح کے میٹرکس پر گوسیائی خاتمے (یا مساوی طور پر ایل یو سڑنا) کا اطلاق کرنے کے نتیجے میں بینڈ بہت سے غیر صفر عناصر سے بھر جاتا ہے۔ بینڈ اسٹوریج بینڈ میٹرکس عام طور پر بینڈ میں ڈائیگنلز کو محفوظ کرکے محفوظ کیے جاتے ہیں ؛ باقی مضمر طور پر صفر ہوتے ہیں۔ مثال کے طور پر، ایک سہ رخی میٹرکس میں بینڈوتھ 1 ہوتا ہے۔ 6-بائی-6 میٹرکس کو 6-بائی-3 میٹرکس کے طور پر محفوظ کیا جاتا ہے جب میٹرکس سمیٹرک ہوتا ہے تو مزید بچت ممکن ہوتی ہے۔ مثال کے طور پر، 2 کی اوپری بینڈوتھ کے ساتھ ایک سمیٹرک 6-بائی-6 میٹرکس پر غور کریں: یہ میٹرکس 6-بائی-3 میٹرکس کے طور پر محفوظ کیا جاتا ہے: سپارس میٹرکس کی بینڈ شکل کمپیوٹیشنل نقطہ نظر سے، بینڈ میٹرکس کے ساتھ کام کرنا ہمیشہ اسی طرح کے جہتی مربع میٹرکس کے ساتھ کام کرنے کو ترجیح دیتا ہے۔ ایک بینڈ میٹرکس کو پیچیدگی میں ایک آئتاکار میٹرکس سے تشبیہ دی جا سکتی ہے جس کی صف کا طول و عرض بینڈ میٹرکس کی بینڈوڈتھ کے برابر ہوتا ہے۔ اس طرح ضرب جیسی کارروائیوں کو انجام دینے میں شامل کام نمایاں طور پر گر جاتا ہے، جس کی وجہ سے اکثر حساب کتاب کے وقت اور پیچیدگی کے لحاظ سے بہت زیادہ بچت ہوتی ہے۔ چونکہ غیر معمولی میٹرکس گھنے میٹرکس کے مقابلے میں زیادہ موثر حساب کتاب کے ساتھ ساتھ کمپیوٹر اسٹوریج کے زیادہ موثر استعمال کے لیے خود کو قرض دیتے ہیں، اس لیے میٹرکس میں تغیرات، یا اس طرح کی دیگر مساوات یا مماثلت کی تبدیلیوں کو لاگو کرکے بینڈوتھ کو کم سے کم کرنے (یا براہ راست بھرنے کو کم سے کم کرنے) کے طریقے تلاش کرنے پر بہت زیادہ تحقیق کی گئی ہے۔ کاتھل-میککی الگورتھم کو ایک غیر معمولی سمیٹرک میٹرکس کی بینڈوتھ کو کم کرنے کے لیے استعمال کیا جا سکتا ہے۔ تاہم، ایسے میٹرکس ہیں جن کے لیے ریورس کیتھل-میککی الگورتھم بہتر کارکردگی کا مظاہرہ کرتا ہے۔ بہت سے دوسرے طریقے استعمال میں ہیں۔ قطاروں اور کالموں کی تغیرات کے ذریعے کم سے کم بینڈوڈتھ والے میٹرکس کی نمائندگی تلاش کرنے کا مسئلہ این پی-ہارڈ ہے۔ ڈائیگنل میٹرکس گراف بینڈوڈتھ نوٹس حوالہ جات بھی دیکھیں۔ ۔ ۔ ۔ ۔ بیرونی لنکس لیپک اور بینڈ میٹرکس سے متعلق معلومات بینڈڈ میٹرکس اور دیگر اسپارس میٹرکس فارمیٹس پر ایک سبق اسپارس میٹرکس