নতুন ব্রেকথ্রু ম্যাট্রিক্স গুণকে আদর্শের কাছাকাছি নিয়ে আসে | কোয়ান্টা ম্যাগাজিন

কম্পিউটার বিজ্ঞানীরা একটি দাবিদার দল। তাদের জন্য, একটি সমস্যার সঠিক উত্তর পাওয়ার জন্য এটি যথেষ্ট নয় - লক্ষ্য, প্রায় সবসময়, যথাসম্ভব দক্ষতার সাথে উত্তর পাওয়া।

ম্যাট্রিক্স বা সংখ্যার বিন্যাসকে গুণ করার কাজটি নিন। 1812 সালে, ফরাসি গণিতবিদ জ্যাক ফিলিপ মেরি বিনেট প্রাথমিক নিয়মের সেট নিয়ে এসেছিলেন যা আমরা এখনও শিক্ষার্থীদের শেখাই। এটি পুরোপুরি ভাল কাজ করে, তবে অন্যান্য গণিতবিদরা প্রক্রিয়াটিকে সহজ এবং দ্রুত করার উপায় খুঁজে পেয়েছেন। এখন কাজ প্রক্রিয়া দ্রুত করা ম্যাট্রিক্স গুণনের বিষয়টি গণিত এবং কম্পিউটার বিজ্ঞানের সংযোগস্থলে অবস্থিত, যেখানে গবেষকরা এই প্রক্রিয়াটিকে আজও উন্নত করে চলেছেন — যদিও সাম্প্রতিক দশকগুলিতে লাভগুলি মোটামুটি শালীন হয়েছে। 1987 সাল থেকে, ম্যাট্রিক্স গুণের সংখ্যাগত উন্নতি হয়েছে "ছোট এবং ... প্রাপ্ত করা অত্যন্ত কঠিন," বলেন ফ্রাঁসোয়া লে গ্যাল, নাগোয়া বিশ্ববিদ্যালয়ের একজন কম্পিউটার বিজ্ঞানী।

এখন, তিন গবেষক - সিংহুয়া বিশ্ববিদ্যালয়ের রণ ডুয়ান এবং রেনফেই ঝু এবং ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়ের হংক্সুন উ, বার্কলে - এই বহুবর্ষজীবী সমস্যাটিকে আক্রমণ করার জন্য একটি বড় পদক্ষেপ নিয়েছেন। তাদের নতুন ফলাফল, গত নভেম্বরে কম্পিউটার সায়েন্স কনফারেন্সের ফাউন্ডেশনে উপস্থাপিত, একটি অপ্রত্যাশিত নতুন কৌশল থেকে উদ্ভূত, লে গ্যাল বলেছেন। যদিও উন্নতি নিজেই তুলনামূলকভাবে ছোট ছিল, লে গ্যাল এটিকে "অন্য পূর্ববর্তীগুলির তুলনায় ধারণাগতভাবে বড়" বলে অভিহিত করেছেন।

কৌশলটি পূর্বে অজানা এবং সেইজন্য সম্ভাব্য উন্নতির অব্যবহৃত উত্স প্রকাশ করে এবং এটি ইতিমধ্যেই ফল দিয়েছে: একটি দ্বিতীয় কাগজ, জানুয়ারীতে প্রকাশিত, ম্যাট্রিক্স গুনকে আরও কীভাবে বাড়ানো যায় তা দেখানোর জন্য প্রথমটির উপর ভিত্তি করে তৈরি করা হয়েছে।

"এটি একটি বড় প্রযুক্তিগত অগ্রগতি," বলেন উইলিয়াম কুজমাউল, হার্ভার্ড বিশ্ববিদ্যালয়ের একজন তাত্ত্বিক কম্পিউটার বিজ্ঞানী। "এটি ম্যাট্রিক্স গুণনের সবচেয়ে বড় উন্নতি যা আমরা এক দশকেরও বেশি সময়ে দেখেছি।"

ম্যাট্রিক্স লিখুন

এটি একটি অস্পষ্ট সমস্যা বলে মনে হতে পারে, কিন্তু ম্যাট্রিক্স গুণন একটি মৌলিক গণনামূলক অপারেশন। তীক্ষ্ণ কম্পিউটার গ্রাফিক্স প্রদর্শন থেকে শুরু করে নেটওয়ার্ক তত্ত্বে লজিস্টিক সমস্যা সমাধান পর্যন্ত বিভিন্ন কাজের জন্য লোকেরা প্রতিদিন যে অ্যালগরিদমগুলি ব্যবহার করে তার একটি বৃহৎ অনুপাতের মধ্যে এটি অন্তর্ভুক্ত। এবং গণনার অন্যান্য ক্ষেত্রগুলির মতো, গতি সর্বাধিক। এমনকি সামান্য উন্নতিও শেষ পর্যন্ত সময়, গণনীয় শক্তি এবং অর্থের উল্লেখযোগ্য সঞ্চয় ঘটাতে পারে। কিন্তু আপাতত, তাত্ত্বিকরা মূলত এই প্রক্রিয়াটি কতটা দ্রুত হতে পারে তা বের করতে আগ্রহী।

দুই গুণ করার প্রচলিত পদ্ধতি n-দ্বারা-n ম্যাট্রিক্স — প্রথম ম্যাট্রিক্সের প্রতিটি সারির সংখ্যাকে দ্বিতীয় কলামের সংখ্যা দিয়ে গুণ করে — প্রয়োজন n³ পৃথক গুণ। 2-বাই-2 ম্যাট্রিসের জন্য, এর মানে 2³ বা 8 গুণ।

1969 সালে, গণিতবিদ ভলকার স্ট্রাসেন একটি আরও জটিল পদ্ধতি প্রকাশ করেছিলেন যা 2-বাই-2 ম্যাট্রিক্সকে মাত্র সাতটি গুণক ধাপে এবং 18 টি যোগে গুণ করতে পারে। দুই বছর পরে, কম্পিউটার বিজ্ঞানী শ্মুয়েল উইনোগ্রাড দেখিয়েছিলেন যে সাতটি প্রকৃতপক্ষে 2-বাই-2 ম্যাট্রিসের জন্য পরম সর্বনিম্ন।

স্ট্রাসেন সেই একই ধারণাকে কাজে লাগিয়ে সব বড় দেখানোর জন্য n-দ্বারা-n ম্যাট্রিকেও এর থেকে কম সময়ে গুণ করা যেতে পারে n³ পদক্ষেপ এই কৌশলটির একটি মূল উপাদানের মধ্যে রয়েছে পচন নামক একটি পদ্ধতি - একটি বড় ম্যাট্রিক্সকে ক্রমাগত ছোট সাবমেট্রিসে ভেঙে ফেলা, যা 2-বাই-2 বা এমনকি 1-বাই-1 (এগুলি কেবলমাত্র একক সংখ্যা) হিসাবে ছোট হতে পারে।

একটি দৈত্যাকার অ্যারেকে ছোট ছোট টুকরোগুলিতে ভাগ করার যুক্তিটি বেশ সহজ, অনুসারে ভার্জিনিয়া ভ্যাসিলিভস্কা উইলিয়ামস, ম্যাসাচুসেটস ইনস্টিটিউট অফ টেকনোলজির একজন কম্পিউটার বিজ্ঞানী এবং একটি নতুন গবেষণাপত্রের সহ-লেখক। "একজন মানুষের পক্ষে একটি বড় ম্যাট্রিক্সের দিকে তাকানো কঠিন (বলুন, 100-বাই-100 এর ক্রম অনুসারে) এবং সম্ভাব্য সেরা অ্যালগরিদম সম্পর্কে চিন্তা করা," ভ্যাসিলিভস্কা উইলিয়ামস বলেছেন। এমনকি 3-বাই-3 ম্যাট্রিক্স এখনও পুরোপুরি সমাধান করা হয়নি। "তবুও, কেউ একটি দ্রুত অ্যালগরিদম ব্যবহার করতে পারে যা ইতিমধ্যেই ছোট ম্যাট্রিসের জন্য তৈরি করা হয়েছে যাতে বড় ম্যাট্রিক্সের জন্য দ্রুত অ্যালগরিদম পাওয়া যায়।"

গতির মূল চাবিকাঠি, গবেষকরা নির্ধারণ করেছেন, গুণন ধাপের সংখ্যা হ্রাস করা, যে সূচকটিকে কমিয়ে দেওয়া n³ (স্ট্যান্ডার্ড পদ্ধতির জন্য) যতটা তারা পারে। সর্বনিম্ন সম্ভাব্য মান, n², মূলত উত্তর লিখতে যতক্ষণ লাগে ততক্ষণ। কম্পিউটার বিজ্ঞানীরা সেই সূচকটিকে ওমেগা, ω, সহ হিসাবে উল্লেখ করেন n^ω সফলভাবে দুই গুণ করার জন্য প্রয়োজন সবচেয়ে কম সম্ভাব্য পদক্ষেপ n-দ্বারা-n হিসাবে matrices n খুব বড় হয়। "এই কাজের মূল বিষয়," ঝো বলেছেন, যিনি জানুয়ারী 2024 সালের কাগজের সহ-লেখকও ছিলেন, "আপনি 2 এর কতটা কাছাকাছি আসতে পারেন এবং তা তত্ত্বে এটি অর্জন করা যায় কিনা তা দেখতে হবে।"

একটি লেজার ফোকাস

1986 সালে, স্ট্রসেন আরেকটি বড় সাফল্য অর্জন করেছিলেন যখন তিনি উপস্থাপিত ম্যাট্রিক্স গুণনের জন্য লেজার পদ্ধতি কি বলা হয়। স্ট্রসেন এটিকে 2.48 এর ওমেগার জন্য একটি উচ্চ মান স্থাপন করতে ব্যবহার করেছিলেন। যদিও পদ্ধতিটি বৃহৎ ম্যাট্রিক্স গুণের মাত্র একটি ধাপ, এটি সবচেয়ে গুরুত্বপূর্ণ কারণ গবেষকরা এটির উন্নতি অব্যাহত রেখেছেন।

এক বছর পরে, উইনোগ্রাড এবং ডন কপারস্মিথ একটি নতুন অ্যালগরিদম প্রবর্তন করেন যা লেজার পদ্ধতির সুন্দর পরিপূরক। সরঞ্জামগুলির এই সংমিশ্রণটি ম্যাট্রিক্স গুণনের গতি বাড়ানোর জন্য পরবর্তী সমস্ত প্রচেষ্টায় বৈশিষ্ট্যযুক্ত হয়েছে।

কিভাবে এই বিভিন্ন উপাদান একসাথে মাপসই সম্পর্কে চিন্তা করার একটি সরলীকৃত উপায় এখানে. আসুন দুটি বড় ম্যাট্রিক্স, A এবং B দিয়ে শুরু করি, যেগুলিকে আপনি একসাথে গুণ করতে চান। প্রথমত, আপনি সেগুলিকে অনেকগুলি ছোট সাবমেট্রিসে, বা ব্লকগুলিতে পচিয়ে দেন, যেমনটি কখনও কখনও বলা হয়। এর পরে, আপনি ব্লকগুলি পরিচালনা এবং শেষ পর্যন্ত একত্রিত করার জন্য এক ধরণের নির্দেশিকা ম্যানুয়াল হিসাবে পরিবেশন করতে কপারস্মিথ এবং উইনোগ্রাডের অ্যালগরিদম ব্যবহার করতে পারেন। "এটি আমাকে বলে যে কী গুণ করতে হবে এবং কী যোগ করতে হবে এবং কী এন্ট্রি কোথায় যাবে" পণ্য ম্যাট্রিক্স সি-তে, ভ্যাসিলেভস্কা উইলিয়ামস বলেছেন। "এটি A এবং B থেকে C তৈরি করার একটি রেসিপি মাত্র।"

তবে একটি ধরা আছে: আপনি মাঝে মাঝে এমন ব্লকগুলি দিয়ে শেষ করেন যেগুলিতে এন্ট্রি মিল রয়েছে। প্রোডাক্টে এগুলি ছেড়ে দেওয়া সেই এন্ট্রিগুলিকে দুবার গণনা করার সমান হবে, তাই কিছু সময়ে আপনাকে সেই ডুপ্লিকেট করা পদগুলি থেকে পরিত্রাণ পেতে হবে, যাকে ওভারল্যাপ বলা হয়। গবেষকরা তারা যে ব্লকগুলিতে আছেন তা "হত্যা" করে - তাদের উপাদানগুলিকে গণনা থেকে সরিয়ে দেওয়ার জন্য শূন্যের সমান সেট করে৷

সেখানেই স্ট্রসেনের লেজার পদ্ধতি অবশেষে কার্যকর হয়। "লেজার পদ্ধতি সাধারণত খুব ভাল কাজ করে এবং সাধারণত ওভারল্যাপ অপসারণের জন্য ব্লকের একটি উপসেট মেরে ফেলার একটি ভাল উপায় খুঁজে পায়," লে গল বলেন। লেজারটি মুছে ফেলার পরে, বা "পুড়ে যায়", সমস্ত ওভারল্যাপ, আপনি চূড়ান্ত পণ্য ম্যাট্রিক্স তৈরি করতে পারেন, সি।

এই বিভিন্ন কৌশলগুলিকে একসাথে রাখার ফলে সামগ্রিকভাবে ইচ্ছাকৃতভাবে কৃপণ সংখ্যার সাথে দুটি ম্যাট্রিক্সকে গুণ করার জন্য একটি অ্যালগরিদম তৈরি হয় - অন্তত তত্ত্বে। লেজার পদ্ধতি ব্যবহারিক হতে উদ্দেশ্য নয়; এটি ম্যাট্রিক্স গুণ করার আদর্শ উপায় সম্পর্কে চিন্তা করার একটি উপায়। "আমরা কখনই [কম্পিউটারে] পদ্ধতি চালাই না," ঝো বলেন। "আমরা এটি বিশ্লেষণ করি।"

এবং সেই বিশ্লেষণই এক দশকেরও বেশি সময়ের মধ্যে ওমেগাতে সবচেয়ে বড় উন্নতির দিকে পরিচালিত করেছে।

একটি ক্ষতি পাওয়া গেছে

গত গ্রীষ্মের কাগজ, ডুয়ান, ঝাউ এবং উ দ্বারা, দেখিয়েছে যে স্ট্রসেনের প্রক্রিয়া এখনও উল্লেখযোগ্যভাবে ত্বরান্বিত হতে পারে। এটি একটি ধারণার কারণে যে তারা একটি লুকানো ক্ষতি বলে অভিহিত করেছিল, যা পূর্ববর্তী বিশ্লেষণগুলির মধ্যে গভীরভাবে সমাহিত ছিল - "অনিচ্ছাকৃতভাবে অনেকগুলি ব্লক মেরে ফেলার ফল," ঝু বলেছেন।

লেজার পদ্ধতি আবর্জনা হিসাবে ওভারল্যাপ সহ ব্লক লেবেল করে কাজ করে, নিষ্পত্তির জন্য স্লেট করা হয়; অন্যান্য ব্লক যোগ্য বলে মনে করা হয় এবং সংরক্ষণ করা হবে। তবে নির্বাচন প্রক্রিয়া কিছুটা এলোমেলো। আবর্জনা হিসাবে রেট করা একটি ব্লক, আসলে, সর্বোপরি কার্যকর হতে পারে। এটি মোটেও আশ্চর্যজনক ছিল না, তবে এই র্যান্ডম পছন্দগুলির অনেকগুলি পরীক্ষা করে, ডুয়ানের দল নির্ধারণ করেছে যে লেজার পদ্ধতিটি পদ্ধতিগতভাবে ব্লকগুলিকে অবমূল্যায়ন করছে: আরও ব্লক সংরক্ষণ করা উচিত এবং কম ফেলে দেওয়া উচিত। এবং, সাধারণত যেমন হয়, কম বর্জ্য বৃহত্তর দক্ষতায় অনুবাদ করে।

"ওভারল্যাপ ছাড়াই আরও ব্লক রাখতে সক্ষম হওয়া এইভাবে … একটি দ্রুত ম্যাট্রিক্স গুণন অ্যালগরিদমের দিকে পরিচালিত করে," লে গ্যাল বলেছিলেন।

এই ক্ষতির অস্তিত্ব প্রমাণ করার পরে, ডুয়ানের দল লেজার পদ্ধতিতে ব্লক লেবেল করার উপায়টি পরিবর্তন করেছে, বর্জ্যকে উল্লেখযোগ্যভাবে হ্রাস করেছে। ফলস্বরূপ, তারা প্রায় 2.371866-এ ওমেগার জন্য একটি নতুন আপার বাউন্ড সেট করেছে - 2.3728596 এর আগের উপরের সীমার তুলনায় একটি উন্নতি, 2020 এ সেট করা হয়েছে জোশ আলমান এবং ভ্যাসিলিভস্কা উইলিয়ামস দ্বারা। এটি একটি শালীন পরিবর্তনের মত মনে হতে পারে, যা প্রায় 0.001 দ্বারা আবদ্ধ কমিয়ে দেয়। কিন্তু এটি 2010 সাল থেকে বিজ্ঞানীদের একক বৃহত্তম উন্নতি। ভ্যাসিলেভস্কা উইলিয়ামস এবং আলম্যানের 2020 ফলাফল, তুলনা করে, শুধুমাত্র 0.00001 দ্বারা পূর্বসূরির তুলনায় উন্নতি করেছে।

কিন্তু গবেষকদের জন্য সবচেয়ে উত্তেজনাপূর্ণ জিনিসটি শুধু নতুন রেকর্ড নয় - যা দীর্ঘস্থায়ী হয়নি। এটিও সত্য যে কাগজটি উন্নতির জন্য একটি নতুন উপায় প্রকাশ করেছে যা ততক্ষণ পর্যন্ত সম্পূর্ণ অলক্ষিত ছিল। প্রায় চার দশক ধরে, সবাই একই লেজার পদ্ধতির উপর নির্ভর করছে, লে গ্যাল বলেছেন। "তারপর তারা খুঁজে পেয়েছিল যে, ভাল, আমরা আরও ভাল করতে পারি।"

জানুয়ারী 2024 কাগজটি এই নতুন পদ্ধতিকে পরিমার্জিত করেছে, ভাসিলেভস্কা উইলিয়ামস, ঝো এবং তাদের সহ-লেখকদের লুকানো ক্ষতি আরও কমাতে সক্ষম করেছে। এটি ওমেগার উপরের সীমার একটি অতিরিক্ত উন্নতির দিকে পরিচালিত করে, এটিকে 2.371552 এ হ্রাস করে। লেখকরা আয়তক্ষেত্রাকার (n-দ্বারা-m) ম্যাট্রিক্স - একটি পদ্ধতি যা গ্রাফ তত্ত্ব, মেশিন লার্নিং এবং অন্যান্য ক্ষেত্রে প্রয়োগ করে।

এই লাইনগুলির সাথে আরও কিছু অগ্রগতি সবই নিশ্চিত, তবে সীমা রয়েছে। 2015 সালে, Le Gall এবং দুই সহযোগী প্রতিপন্ন যে বর্তমান পদ্ধতি - কপারস্মিথ-উইনোগ্রাড রেসিপির সাথে মিলিত লেজার পদ্ধতি - 2.3078 এর নিচে একটি ওমেগা দিতে পারে না। আরও উন্নতি করতে, লে গ্যাল বলেছিলেন, "আপনাকে কপারস্মিথ এবং উইনোগ্রাডের আসল [পন্থা] উন্নত করতে হবে যা 1987 সাল থেকে সত্যিই পরিবর্তিত হয়নি. " কিন্তু এখনও পর্যন্ত, কেউ এর চেয়ে ভাল উপায় নিয়ে আসেনি। এমনকি একটি নাও হতে পারে।

"ওমেগা উন্নত করা আসলে এই সমস্যাটি বোঝার অংশ," ঝো বলেছেন। "যদি আমরা সমস্যাটি ভালভাবে বুঝতে পারি, তাহলে আমরা এটির জন্য আরও ভাল অ্যালগরিদম ডিজাইন করতে পারি। [এবং] লোকেরা এখনও এই প্রাচীন সমস্যাটি বোঝার খুব প্রাথমিক পর্যায়ে রয়েছে।"