نئی پیش رفت میٹرکس ضرب کو آئیڈیل کے قریب لاتی ہے۔ کوانٹا میگزین

کمپیوٹر سائنس دان ایک مطالبہ کرنے والے گروپ ہیں۔ ان کے لیے، کسی مسئلے کا صحیح جواب حاصل کرنا کافی نہیں ہے - مقصد، تقریباً ہمیشہ، جتنا ممکن ہو مؤثر طریقے سے جواب حاصل کرنا ہے۔

میٹرکس، یا اعداد کی صفوں کو ضرب دینے کا عمل لیں۔ 1812 میں، فرانسیسی ریاضی دان Jacques Philippe Marie Binet نے اصولوں کا بنیادی مجموعہ پیش کیا جو ہم اب بھی طلباء کو پڑھاتے ہیں۔ یہ بالکل ٹھیک کام کرتا ہے، لیکن دوسرے ریاضی دانوں نے اس عمل کو آسان اور تیز کرنے کے طریقے ڈھونڈ لیے ہیں۔ اب کا کام عمل کو تیز کرنا میٹرکس ضرب ریاضی اور کمپیوٹر سائنس کے سنگم پر واقع ہے، جہاں محققین آج تک اس عمل کو بہتر بنا رہے ہیں - حالانکہ حالیہ دہائیوں میں فوائد کافی معمولی رہے ہیں۔ 1987 کے بعد سے، میٹرکس ضرب میں عددی بہتری "چھوٹی اور … حاصل کرنا انتہائی مشکل" رہی ہے۔ فرانسوا لی گالناگویا یونیورسٹی میں کمپیوٹر سائنس دان۔

اب، تین محققین - سنگھوا یونیورسٹی کے رین ڈوان اور رینفی چاؤ اور یونیورسٹی آف کیلیفورنیا، برکلے کے ہانگکسن وو - نے اس بارہماسی مسئلے پر حملہ کرنے کے لیے ایک بڑا قدم آگے بڑھایا ہے۔ ان کا نئے نتائجلی گیل نے کہا، گزشتہ نومبر میں کمپیوٹر سائنس کی فاؤنڈیشنز کانفرنس میں پیش کیا گیا، جو ایک غیر متوقع نئی تکنیک سے نکلا ہے۔ اگرچہ بہتری بذات خود نسبتاً چھوٹی تھی، لیکن لی گال نے اسے "تصوراتی طور پر دوسرے پچھلے لوگوں سے بڑا" قرار دیا۔

یہ تکنیک پہلے سے نامعلوم اور اس وجہ سے ممکنہ بہتری کے غیر استعمال شدہ ذریعہ کو ظاہر کرتی ہے، اور اس نے پہلے ہی پھل پیدا کیے ہیں: دوسرا کاغذجنوری میں شائع ہوا، یہ بتانے کے لیے سب سے پہلے بناتا ہے کہ کس طرح میٹرکس ضرب کو مزید بڑھایا جا سکتا ہے۔

"یہ ایک اہم تکنیکی پیش رفت ہے،" نے کہا ولیم کزمول، ہارورڈ یونیورسٹی میں ایک نظریاتی کمپیوٹر سائنس دان۔ "یہ میٹرکس ضرب میں سب سے بڑی بہتری ہے جو ہم نے ایک دہائی سے زیادہ عرصے میں دیکھی ہے۔"

میٹرکس درج کریں

یہ ایک غیر واضح مسئلہ لگتا ہے، لیکن میٹرکس ضرب ایک بنیادی کمپیوٹیشنل آپریشن ہے۔ یہ الگورتھم کے ایک بڑے تناسب میں شامل ہے جو لوگ ہر روز مختلف کاموں کے لیے استعمال کرتے ہیں، تیز کمپیوٹر گرافکس کی نمائش سے لے کر نیٹ ورک تھیوری میں لاجسٹک مسائل کو حل کرنے تک۔ اور حساب کے دوسرے شعبوں کی طرح، رفتار سب سے اہم ہے۔ یہاں تک کہ معمولی بہتری بھی بالآخر وقت، کمپیوٹیشنل طاقت اور پیسے کی اہم بچت کا باعث بن سکتی ہے۔ لیکن فی الحال، نظریاتی ماہرین بنیادی طور پر یہ جاننے میں دلچسپی رکھتے ہیں کہ یہ عمل کتنا تیز ہو سکتا ہے۔

دو کو ضرب دینے کا روایتی طریقہ n-ب-n میٹرکس — پہلی میٹرکس میں ہر قطار کے نمبروں کو دوسرے میں کالموں کے نمبروں سے ضرب دے کر — کی ضرورت ہوتی ہے n³ الگ الگ ضربیں 2-by-2 میٹرکس کے لیے، اس کا مطلب ہے 2³ یا 8 ضرب۔

1969 میں، ریاضی دان وولکر سٹراسن نے ایک زیادہ پیچیدہ طریقہ کار کا انکشاف کیا جو صرف سات ضرب کے مراحل اور 2 اضافے میں 2 بہ 18 میٹرکس کو ضرب دے سکتا ہے۔ دو سال بعد، کمپیوٹر سائنس دان شموئل ونوگراڈ نے یہ ظاہر کیا کہ سات، درحقیقت، 2-by-2 میٹرکس کے لیے مطلق کم از کم ہے۔

اسٹراسن نے اسی خیال کا استحصال کیا تاکہ یہ ظاہر کیا جا سکے کہ سب کچھ بڑا ہے۔ n-ب-n میٹرک کو بھی اس سے کم میں ضرب کیا جا سکتا ہے۔ n³ قدم اس حکمت عملی کے ایک اہم عنصر میں ایک طریقہ کار شامل ہے جسے سڑنا کہا جاتا ہے - ایک بڑے میٹرکس کو یکے بعد دیگرے چھوٹے ذیلی میٹرکس میں توڑنا، جو 2-by-2 یا 1-by-1 تک چھوٹا ہو سکتا ہے (یہ صرف ایک نمبر ہیں)۔

کے مطابق، ایک دیوہیکل سرنی کو چھوٹے چھوٹے ٹکڑوں میں تقسیم کرنے کا استدلال بہت آسان ہے۔ ورجینیا واسیلوسکا ولیمز، میساچوسٹس انسٹی ٹیوٹ آف ٹیکنالوجی کے کمپیوٹر سائنس دان اور نئے مقالوں میں سے ایک کے شریک مصنف۔ "انسان کے لیے ایک بڑے میٹرکس کو دیکھنا مشکل ہے (کہیں کہ 100-by-100 کی ترتیب پر) اور بہترین ممکنہ الگورتھم کے بارے میں سوچنا،" Vassilevska Williams نے کہا۔ یہاں تک کہ 3 بائی 3 میٹرکس بھی ابھی تک مکمل طور پر حل نہیں ہوئے ہیں۔ "اس کے باوجود، کوئی ایک تیز الگورتھم استعمال کر سکتا ہے جسے کسی نے چھوٹے میٹرکس کے لیے پہلے ہی تیار کر لیا ہے تاکہ بڑے میٹرکس کے لیے بھی تیز رفتار الگورتھم حاصل کیا جا سکے۔"

رفتار کی کلید، محققین نے طے کیا ہے، ضرب کے مراحل کی تعداد کو کم کرنا ہے، اس سے اس کفایت کو کم کرنا n³ (معیاری طریقہ کے لیے) جتنا وہ کر سکتے ہیں۔ سب سے کم ممکنہ قیمت، n², بنیادی طور پر جب تک صرف جواب لکھنے میں وقت لگتا ہے۔ کمپیوٹر سائنس دان اس ایکسپوننٹ کو اومیگا، ω، کے ساتھ کہتے ہیں۔ n^ω کامیابی کے ساتھ دو کو ضرب دینے کے لیے درکار سب سے کم ممکنہ اقدامات n-ب-n میٹرک کے طور پر n بہت بڑا ہوتا ہے. "اس کام کا نقطہ،" ژاؤ نے کہا، جس نے جنوری 2024 کے مقالے کے شریک مصنف بھی تھے، "یہ دیکھنا ہے کہ آپ 2 کے کتنے قریب آ سکتے ہیں، اور کیا اسے نظریہ میں حاصل کیا جا سکتا ہے۔"

ایک لیزر فوکس

1986 میں، اسٹراسن نے ایک اور بڑی پیش رفت کی تھی جب وہ متعارف میٹرکس ضرب کے لیے لیزر طریقہ کیا کہلاتا ہے۔ Strassen نے اسے 2.48 کے اومیگا کے لیے اوپری قدر قائم کرنے کے لیے استعمال کیا۔ اگرچہ یہ طریقہ بڑے میٹرکس ضرب میں صرف ایک قدم ہے، لیکن یہ سب سے اہم میں سے ایک ہے کیونکہ محققین نے اس میں بہتری لانا جاری رکھا ہوا ہے۔

ایک سال بعد، Winograd اور Don Coppersmith نے ایک نیا الگورتھم متعارف کرایا جس نے لیزر کے طریقہ کار کو خوبصورتی سے مکمل کیا۔ ٹولز کا یہ مجموعہ میٹرکس ضرب کو تیز کرنے کے لیے تقریباً تمام بعد کی کوششوں میں نمایاں ہے۔

یہاں یہ سوچنے کا ایک آسان طریقہ ہے کہ یہ مختلف عناصر ایک ساتھ کیسے فٹ ہوتے ہیں۔ آئیے دو بڑے میٹرکس، A اور B کے ساتھ شروع کریں، جنہیں آپ ایک ساتھ ضرب کرنا چاہتے ہیں۔ سب سے پہلے، آپ انہیں بہت سے چھوٹے ذیلی میٹرکس، یا بلاکس میں گلتے ہیں، جیسا کہ انہیں کبھی کبھی کہا جاتا ہے۔ اس کے بعد، آپ کاپرسمتھ اور ونوگراڈ کے الگورتھم کو بلاکس کو ہینڈل کرنے اور بالآخر اسمبل کرنے کے لیے ایک قسم کے ہدایات دستی کے طور پر استعمال کر سکتے ہیں۔ "یہ مجھے بتاتا ہے کہ کیا ضرب لگانا ہے اور کیا شامل کرنا ہے اور کیا اندراجات کہاں جاتے ہیں" پروڈکٹ میٹرکس سی میں، واسیلیوسکا ولیمز نے کہا۔ "یہ صرف A اور B سے C بنانے کا ایک نسخہ ہے۔"

تاہم، ایک کیچ ہے: آپ کبھی کبھی ایسے بلاکس کے ساتھ ختم ہوجاتے ہیں جن میں اندراجات مشترک ہیں۔ ان کو پروڈکٹ میں چھوڑنا ان اندراجات کو دو بار گننے کے مترادف ہوگا، لہذا کسی وقت آپ کو ان نقل شدہ اصطلاحات سے چھٹکارا حاصل کرنا ہوگا، جنہیں اوورلیپس کہتے ہیں۔ محققین یہ کام ان بلاکس کو "قتل" کرکے کرتے ہیں جن میں وہ ہیں - ان کے اجزاء کو صفر کے برابر سیٹ کرکے انہیں حساب سے ہٹانے کے لیے۔

اسی جگہ پر سٹراسن کا لیزر طریقہ کارآمد ہوتا ہے۔ لی گال نے کہا، "لیزر کا طریقہ عام طور پر بہت اچھا کام کرتا ہے اور عام طور پر اوورلیپ کو ہٹانے کے لیے بلاکس کے سب سیٹ کو مارنے کا ایک اچھا طریقہ تلاش کرتا ہے۔" لیزر کے ختم ہوجانے کے بعد، یا تمام اوورلیپس ہوجانے کے بعد، آپ فائنل پروڈکٹ میٹرکس، C بنا سکتے ہیں۔

ان مختلف تکنیکوں کو ایک ساتھ رکھنے کے نتیجے میں دو میٹرکس کو ضرب دینے کے لیے الگورتھم میں مجموعی طور پر - کم از کم تھیوری میں - جان بوجھ کر کنجوس تعداد میں ضرب۔ لیزر کے طریقہ کار کا مقصد عملی ہونا نہیں ہے۔ میٹرکس کو ضرب دینے کے مثالی طریقہ کے بارے میں سوچنے کا یہ صرف ایک طریقہ ہے۔ "ہم کبھی بھی طریقہ [کمپیوٹر پر] نہیں چلاتے،" زو نے کہا۔ "ہم اس کا تجزیہ کرتے ہیں۔"

اور یہی تجزیہ ایک دہائی سے زیادہ عرصے میں اومیگا میں سب سے بڑی بہتری کا باعث بنا۔

ایک نقصان پایا جاتا ہے۔

گزشتہ موسم گرما کے کاغذ، ڈوان، زو اور وو کے ذریعہ، ظاہر ہوا کہ اسٹراسن کے عمل کو اب بھی نمایاں طور پر تیز کیا جاسکتا ہے۔ یہ سب اس تصور کی وجہ سے تھا جسے انہوں نے ایک پوشیدہ نقصان کہا تھا، جو پچھلے تجزیوں کے اندر گہرائی میں دفن ہے - "غیر ارادی طور پر بہت سارے بلاکس کو مارنے کا نتیجہ،" زو نے کہا۔

لیزر کا طریقہ اوورلیپ کے ساتھ بلاکس کو کوڑے کے طور پر لیبل لگا کر کام کرتا ہے، جسے ٹھکانے لگانے کے لیے تیار کیا جاتا ہے۔ دوسرے بلاکس قابل سمجھے جاتے ہیں اور محفوظ کیے جائیں گے۔ تاہم، انتخاب کا عمل کسی حد تک بے ترتیب ہے۔ ردی کی ٹوکری کے طور پر درجہ بندی کردہ بلاک، حقیقت میں، سب کے بعد مفید ثابت ہوسکتا ہے. یہ کوئی سراسر تعجب کی بات نہیں تھی، لیکن ان میں سے بہت سے بے ترتیب انتخابوں کا جائزہ لے کر، ڈوان کی ٹیم نے طے کیا کہ لیزر کا طریقہ منظم طریقے سے بلاکس کو کم کر رہا ہے: زیادہ بلاکس کو محفوظ کیا جانا چاہیے اور کم کو باہر پھینکنا چاہیے۔ اور، جیسا کہ عام طور پر ہوتا ہے، کم فضلہ زیادہ کارکردگی میں ترجمہ کرتا ہے۔

لی گال نے کہا کہ "زیادہ بلاکس کو بغیر اوورلیپ کے رکھنے کے قابل ہونا … ایک تیز میٹرکس ضرب الگورتھم کی طرف جاتا ہے۔"

اس نقصان کے وجود کو ثابت کرنے کے بعد، ڈوان کی ٹیم نے اس طریقے میں ترمیم کی کہ لیزر کے طریقہ کار نے بلاکس کو لیبل کیا، جس سے فضلہ کو کافی حد تک کم کیا گیا۔ نتیجے کے طور پر، انہوں نے اومیگا کے لیے تقریباً 2.371866 پر ایک نئی اپر باؤنڈ سیٹ کی - 2.3728596 کی پچھلی اوپری حد سے بہتری، 2020 میں مقرر کیا گیا ہے۔ بذریعہ جوش المان اور واسیلیوسکا ولیمز۔ یہ ایک معمولی تبدیلی کی طرح لگ سکتا ہے، باؤنڈ کو تقریباً 0.001 تک کم کرتا ہے۔ لیکن یہ 2010 کے بعد سائنسدانوں کی واحد سب سے بڑی بہتری ہے۔ واسیلیوسک ولیمز اور المان کے 2020 کے نتائج، مقابلے کے لحاظ سے، صرف 0.00001 تک اپنے پیشرو سے بہتر ہوئے۔

لیکن جو چیز محققین کے لیے سب سے زیادہ دلچسپ ہے وہ صرف نیا ریکارڈ ہی نہیں ہے - جو زیادہ دیر تک قائم نہیں رہا۔ یہ بھی حقیقت ہے کہ اس مقالے نے بہتری کے لیے ایک نئی راہ کا انکشاف کیا جو اس وقت تک مکمل طور پر کسی کا دھیان نہیں گیا تھا۔ لی گال نے کہا کہ تقریباً چار دہائیوں سے، ہر کوئی ایک ہی لیزر طریقہ پر انحصار کر رہا ہے۔ "پھر انہوں نے پایا کہ، ٹھیک ہے، ہم بہتر کر سکتے ہیں۔"

جنوری 2024 کے مقالے نے اس نئے نقطہ نظر کو بہتر بنایا، جس سے واسیلیوسک ولیمز، زو اور ان کے شریک مصنفین کو پوشیدہ نقصان کو مزید کم کرنے کے قابل بنایا گیا۔ اس سے اومیگا کے اوپری باؤنڈ میں اضافی بہتری آئی، جس سے یہ 2.371552 تک کم ہو گیا۔ مصنفین نے مستطیل کے لیے ضرب کے عمل کو بہتر بنانے کے لیے اسی تکنیک کو بھی عام کیا۔n-ب-m) میٹرکس - ایک طریقہ کار جس میں گراف تھیوری، مشین لرننگ اور دیگر شعبوں میں اطلاق ہوتا ہے۔

ان خطوط پر کچھ مزید پیش رفت یقینی ہے لیکن اس کی حدود ہیں۔ 2015 میں، لی گال اور دو ساتھیوں ثابت ہوا کہ موجودہ نقطہ نظر - Coppersmith-Winograd ترکیب کے ساتھ مل کر لیزر کا طریقہ - 2.3078 سے کم اومیگا حاصل نہیں کر سکتا۔ مزید بہتری لانے کے لیے، لی گیل نے کہا، "آپ کو کاپرسمتھ اور ونوگراڈ کے اصل [طریقہ کار] کو بہتر کرنے کی ضرورت ہے جو 1987 کے بعد سے واقعی تبدیل نہیں ہوا ہے۔". لیکن اب تک، کوئی بھی اس سے بہتر طریقہ نہیں لے کر آیا ہے۔ ہو سکتا ہے ایک بھی نہ ہو۔

"اومیگا کو بہتر بنانا دراصل اس مسئلے کو سمجھنے کا حصہ ہے،" زو نے کہا۔ "اگر ہم مسئلے کو اچھی طرح سمجھ سکتے ہیں، تو ہم اس کے لیے بہتر الگورتھم ڈیزائن کر سکتے ہیں۔ [اور] لوگ اب بھی اس پرانے مسئلے کو سمجھنے کے ابتدائی مراحل میں ہیں۔