2025-11-27T11:04:19.442540

A non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications

Dumas, Pernet, Sedoglavic

The quest for non-commutative matrix multiplication algorithms in small dimensions has seen a lot of recent improvements recently. In particular, the number of scalar multiplications required to multiply two $4\times4$ matrices was first reduced in \cite{Fawzi:2022aa} from 49 (two recursion levels of Strassen's algorithm) to 47 but only in characteristic 2 or more recently to 48 in \cite{alphaevolve} but over complex numbers. We propose an algorithm in 48 multiplications with only rational coefficients, hence removing the complex number requirement. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers. We also produce a straight line program of this algorithm, reducing the leading constant in the complexity, as well as an alternative basis variant of it, leading to an algorithm running in $7 n^{2+\frac{\log_2 3}{2}} +o\left(n^{2+\frac{log_2 3}{2}}\right)$ operations over any ring containing an inverse of 2.

academic

৪×৪ ম্যাট্রিক্স গুণনের জন্য ৪৮টি অ-জটিল গুণনের একটি অ-পরিবর্তনশীল অ্যালগরিদম

মৌলিক তথ্য

পেপার আইডি: 2506.13242
শিরোনাম: A non-commutative algorithm for multiplying 4×4 matrices using 48 non-complex multiplications
লেখক: Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic
প্রতিষ্ঠান: Univ. Grenoble Alpes (Dumas & Pernet), Univ. Lille (Sedoglavic)
শ্রেণীবিভাগ: cs.SC (প্রতীকী গণনা)
প্রকাশনার সময়: নভেম্বর ২৭, ২০২৫ (arXiv প্রাক-প্রিন্ট)
পেপার লিঙ্ক: https://arxiv.org/abs/2506.13242

সারসংক্ষেপ

এই পেপারটি ৪৮টি স্কেলার গুণন ব্যবহার করে ৪×৪ ম্যাট্রিক্স গুণনের জন্য একটি অ-পরিবর্তনশীল অ্যালগরিদম উপস্থাপন করে, যা শুধুমাত্র মূলদ সংখ্যা সহগ ব্যবহার করে, জটিল সংখ্যার প্রয়োজন নেই। এটি AlphaEvolve11 দ্বারা প্রস্তাবিত জটিল ক্ষেত্রের অ্যালগরিদমের একটি উন্নতি, সমদূরবর্তী রূপান্তর (isotropy) এর মাধ্যমে এটিকে মূলদ ক্ষেত্রে প্রজেক্ট করে। নিবন্ধটি সরল-রেখা প্রোগ্রাম (straight-line program) বাস্তবায়নও প্রদান করে এবং একটি বিকল্প ভিত্তি রূপান্তর দেয় যা ২-এর বিপরীত সহ যেকোনো বলয়ে $7n^{2+\frac{\log_2 3}{2}} + o(n^{2+\frac{\log_2 3}{2}})$ গণনা জটিলতা অর্জন করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

১. মূল সমস্যা: ছোট মাত্রার ম্যাট্রিক্স গুণনের জন্য সর্বোত্তম অ-পরিবর্তনশীল অ্যালগরিদম খুঁজে বের করা, বিশেষত প্রয়োজনীয় স্কেলার গুণনের সংখ্যা হ্রাস করা। ম্যাট্রিক্স গুণন কম্পিউটার বিজ্ঞান এবং সংখ্যাসূচক গণনায় একটি মৌলিক ক্রিয়াকলাপ, যার দক্ষতা অসংখ্য প্রয়োগের কর্মক্ষমতা সরাসরি প্রভাবিত করে।

२. গুরুত্ব:

ম্যাট্রিক্স গুণনের সময় জটিলতা রৈখিক বীজগণিত গণনা, যন্ত্র শিক্ষা, বৈজ্ঞানিক গণনা ইত্যাদি ক্ষেত্রের দক্ষতা সরাসরি প্রভাবিত করে
Strassen অ্যালগরিদম (১৯৬৯) প্রথমবারের মতো জটিলতা $O(n^3)$ থেকে $O(n^{2.81})$ এ হ্রাস করেছিল, দ্রুত ম্যাট্রিক্স গুণনের গবেষণা শুরু করেছিল
ছোট মাত্রার ম্যাট্রিক্স গুণন অ্যালগরিদম বড় ম্যাট্রিক্সে পুনরাবৃত্তিমূলকভাবে প্রয়োগ করা যায়, যার ব্যবহারিক প্রয়োগ মূল্য রয়েছে

३. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:

Strassen অ্যালগরিদম ৪×৪ ম্যাট্রিক্সে ৪৯টি গুণন প্রয়োজন (দুটি স্তরের পুনরাবৃত্তি)
Fawzi ইত্যাদি 5 বৈশিষ্ট্য ২ এর ক্ষেত্রে ৪৭টি গুণন অর্জন করেছেন
AlphaEvolve 11 বড় ভাষা মডেল এবং বিবর্তনীয় কোডিং এজেন্ট ব্যবহার করে ৪৮টি গুণনের অ্যালগরিদম খুঁজে পেয়েছে, কিন্তু জটিল সংখ্যা সহগ প্রয়োজন
জটিল সংখ্যা সহগ নির্দিষ্ট বলয় (যেমন পূর্ণসংখ্যা বলয়, সীমিত ক্ষেত্র) এ অ্যালগরিদমের প্রয়োগ সীমিত করে

४. গবেষণা প্রেরণা:

জটিল সংখ্যার প্রয়োজনীয়তা দূর করা, অ্যালগরিদমকে আরও বিস্তৃত বীজগণিত কাঠামোতে প্রয়োগযোগ্য করা
টেনসর বিয়োজনের তত্ত্বে সমরূপতা (সমদূরবর্তী গোষ্ঠী ক্রিয়া) ব্যবহার করে অ্যালগরিদম পদ্ধতিগতভাবে রূপান্তরিত করা
ব্যবহারিক সরল-রেখা প্রোগ্রাম বাস্তবায়ন প্রদান করা, ধ্রুবক পদ অপ্টিমাইজ করা

মূল অবদান

१. প্রধান তাত্ত্বিক অবদান: AlphaEvolve অ্যালগরিদমের সমদূরবর্তী কক্ষপথে (isotropy orbit) মূলদ সংখ্যা বিন্দু বিদ্যমান প্রমাণ করা, ৪৮টি গুণন সহ বিশুদ্ধ মূলদ সহগ অ্যালগরিদম প্রস্তাব করা

२. পদ্ধতিগত অবদান: টেনসর বিয়োজনের সমদূরবর্তী গোষ্ঠী তত্ত্ব পদ্ধতিগতভাবে প্রয়োগ করা, সমদূরবর্তী রূপান্তরের মাধ্যমে (সমীকরণ ২৪) জটিল ক্ষেত্রের অ্যালগরিদমকে মূলদ ক্ষেত্রে প্রজেক্ট করা

३. ব্যবহারিক অবদান:

সম্পূর্ণ সরল-রেখা প্রোগ্রাম বাস্তবায়ন প্রদান করা (তালিকা ১-४), মোট ३४१টি ক্রিয়াকলাপ
তাত্ত্বিক জটিলতা সীমা $11.65625n^{2.792} - 10.65625n^2$
বিকল্প ভিত্তি রূপান্তর প্রদান করা, শুধুমাত্র ६টি ক্রিয়াকলাপ প্রয়োজন (१+२+३), জটিলতা $7n^{2.792}$

४. সর্বজনীনতা: অ্যালগরিদম ২-এর বিপরীত সহ যেকোনো বলয়ে প্রয়োগযোগ্য, প্রয়োগের পরিসীমা প্রসারিত করা

५. খোলা উৎস বাস্তবায়ন: সমস্ত ম্যাট্রিক্স এবং কোড PLinOpt লাইব্রেরিতে জনসাধারণের জন্য উপলব্ধ

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

ইনপুট: দুটি ४×४ ম্যাট্রিক্স $A = (a_{ij})$ এবং $B = (b_{ij})$ , উপাদান $\frac{1}{2}$ সহ বলয় $R$ থেকে
আউটপুট: পণ্য ম্যাট্রিক্স $C = A \cdot B = (c_{ij})$
সীমাবদ্ধতা: স্কেলার গুণনের সংখ্যা ন্যূনতম করা, শুধুমাত্র মূলদ সংখ্যা সহগ ব্যবহার করা (জটিল সংখ্যা এড়ানো)

তাত্ত্বিক কাঠামো: টেনসর বিয়োজন প্রতিনিধিত্ব

१. দ্বিরৈখিক ম্যাপিংয়ের টেনসর প্রতিনিধিত্ব

ম্যাট্রিক্স গুণনকে দ্বিরৈখিক ম্যাপিং হিসাবে প্রতিনিধিত্ব করা যায়: $\beta_{mm}: R^{m \times k} \times R^{k \times n} \rightarrow R^{m \times n}, \quad (A, B) \mapsto A \cdot B$

এই ম্যাপিং টেনসর স্থান $(R^{m \times k})^* \otimes (R^{k \times n})^* \otimes R^{m \times n}$ এ টেনসর বিয়োজন হিসাবে এনকোড করা হয়: $T = \sum_{i=1}^r M_i \otimes N_i \otimes O_i$

যেখানে:

$r$ হল টেনসর র‍্যাঙ্ক (tensor rank), প্রয়োজনীয় স্কেলার গুণনের সংখ্যার সাথে সামঞ্জস্যপূর্ণ
প্রতিটি $(M_i, N_i, O_i)$ হল র‍্যাঙ্ক-এক টেনসর
ত্রিরৈখিক প্রতিনিধিত্ব $\text{Trace}(O_i^T \cdot M_i \cdot N_i)$ হিসাবে

२. Strassen অ্যালগরিদমের টেনসর প্রতিনিধিত্ব

Strassen এর २×२ ম্যাট্রিক্স গুণন অ্যালগরিদম (७টি গুণন) টেনসর র‍্যাঙ্ক ७ এর বিয়োজনের সাথে সামঞ্জস্যপূর্ণ, প্রকার $X^2Y^2Z^2 + 6XYZ$ ।

३. সমদূরবর্তী গোষ্ঠী ক্রিয়া (Isotropy Group Action)

উপপাদ্য २.१: ম্যাট্রিক্স গুণন টেনসরের সমদূরবর্তী গোষ্ঠী: $\text{psl}_{\pm}(R^m) \times \text{psl}_{\pm}(R^k) \times \text{psl}_{\pm}(R^n) \rtimes S_3$

সংজ্ঞা २.२: সমদূরবর্তী $g = (U \times V \times W)$ র‍্যাঙ্ক-এক টেনসর $A \otimes B \otimes C$ এ ক্রিয়া: $(U^{-T} \cdot A \cdot V^T) \otimes (V^{-T} \cdot B \cdot W^T) \otimes (W^{-T} \cdot C \cdot U^T)$

এটি টেনসর র‍্যাঙ্ক অপরিবর্তিত রাখে, কিন্তু সহগ পরিবর্তন করে।

মূল অ্যালগরিদম নির্মাণ

মূল সমদূরবর্তী রূপান্তর

এই পেপারের মূল উদ্ভাবন নির্দিষ্ট সমদূরবর্তী রূপান্তর খুঁজে বের করা (সমীকরণ २४): $\begin{bmatrix} I & 0 & 0 & I \\ 0 & 1 & I & 0 \\ 0 & -I & -1 & 0 \\ -1 & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} I & 0 & 0 & 1 \\ 0 & -I & -I & 0 \\ 0 & -I & I & 0 \\ -I & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

যেখানে $I$ হল কাল্পনিক একক।

মূলদ সহগ টেনসর বিয়োজন

উপরোক্ত সমদূরবর্তী প্রয়োগ করার পর, ४८টি র‍্যাঙ্ক-এক টেনসরের বিয়োজন পাওয়া যায় (সমীকরণ २५-७२), প্রতিটি ফর্ম: $m_i = \left(\sum_{j,k} \alpha_{jk}^{(i)} a_{jk}\right) \otimes \left(\sum_{j,k} \beta_{jk}^{(i)} b_{jk}\right) \otimes \left(\sum_{j,k} \gamma_{jk}^{(i)} c_{jk}\right)$

মূল বৈশিষ্ট্য:

সমস্ত সহগ $\alpha, \beta, \gamma \in \{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$ (মূলদ সংখ্যা)
টেনসর প্রকার $16X^2Y^2Z^2 + 32XYZ$ (१६টি র‍্যাঙ্ক २×२×२, ३२টি র‍্যাঙ্ক १×१×१)
হর শুধুমাত্র २, ४, ८ এর শক্তি অন্তর্ভুক্ত করে

উদাহরণ: প্রথম গুণন পদ

$m_1 = \frac{1}{4}\left(\sum_{i,j} (-1)^{i+j+1} a_{ij}\right) \otimes (b_{31} + b_{41}) \otimes \left(\sum c_{terms}\right)$

LRP ম্যাট্রিক্স প্রতিনিধিত্ব

অ্যালগরিদম তিনটি ম্যাট্রিক্স $(L, R, P)$ দ্বারা সংক্ষিপ্তভাবে প্রতিনিধিত্ব করা যায়:

$L \in R^{48 \times 16}$ : $A$ এর উপাদান থেকে ४८টি বাম অপারেন্ডে রৈখিক রূপান্তর
$R \in R^{48 \times 16}$ : $B$ এর উপাদান থেকে ४८টি ডান অপারেন্ডে রৈখিক রূপান্তর
$P \in R^{16 \times 48}$ : ४८টি পণ্য থেকে $C$ এর উপাদানে রৈখিক রূপান্তর

গণনা প্রবাহ: $\text{vec}(C) = P \cdot (L \cdot \text{vec}(A) \odot R \cdot \text{vec}(B))$

যেখানে $\odot$ উপাদান-অনুযায়ী গুণন (Hadamard গুণ) নির্দেশ করে।

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. সমরূপতার পদ্ধতিগত ব্যবহার: পরীক্ষামূলক অনুসন্ধানের পরিবর্তে, স্থিতিশীল উপগোষ্ঠী $(C_2 \times D_4) \rtimes C_2$ এবং তাত্ত্বিক নির্দেশিত অনুমান ব্যবহার করে সমদূরবর্তী রূপান্তর খুঁজে বের করা

२. জটিল থেকে মূলদ সংখ্যায় প্রজেকশন: উচ্চ-মাত্রার জটিল স্থানে পাওয়া অ্যালগরিদম মূলদ সংখ্যা উপস্থানে প্রজেক্ট করা যায় প্রমাণ করা, এটি একটি অ-তুচ্ছ ফলাফল

३. সরল-রেখা প্রোগ্রাম অপ্টিমাইজেশন:

PLinOpt সরঞ্জাম ব্যবহার করে অপ্টিমাইজড সরল-রেখা প্রোগ্রাম স্বয়ংক্রিয়ভাবে উৎপন্ন করা
কার্নেল বিয়োজন (kernel decomposition) ব্যবহার করে ক্রিয়াকলাপের সংখ্যা হ্রাস করা
এমনকি $R$ ম্যাট্রিক্স সহগ সহজ হলেও, সর্বোত্তম SLP অ-তুচ্ছ গুণন প্রয়োজন হতে পারে

४. বিকল্প ভিত্তি পদ্ধতি: ভিত্তি রূপান্তরের মাধ্যমে আরও সরলীকরণ, ক্রিয়াকলাপ ३३६টিতে হ্রাস করা (মূল ३४१টির তুলনায়)

পরীক্ষামূলক সেটআপ

বাস্তবায়ন সরঞ্জাম

PLinOpt লাইব্রেরি: রৈখিক এবং দ্বিরৈখিক প্রোগ্রাম অপ্টিমাইজেশন পরিচালনা করে এমন C++ রুটিনের সংগ্রহ
কোড স্কেল: প্রায় ८.०९ kSLOC (হাজার লাইন উৎস কোড)
খোলা উৎস: সমস্ত ম্যাট্রিক্স এবং কোড GitHub এ জনসাধারণের জন্য উপলব্ধ

ডেটা ফাইল

অ্যালগরিদমের বিভিন্ন প্রতিনিধিত্ব হিসাবে সংরক্ষিত:

4x4x4_48_rational_L.sms, _R.sms, _P.sms: মান LRP প্রতিনিধিত্ব
4x4x4_48_rational-ALT_*.sms: বিকল্প ভিত্তি প্রতিনিধিত্ব
4x4x4_48_rational-CoB_*.sms: ভিত্তি রূপান্তর ম্যাট্রিক্স

মূল্যায়ন মেট্রিক্স

१. টেনসর র‍্যাঙ্ক: প্রয়োজনীয় স্কেলার গুণনের সংখ্যা (४८) २. মোট ক্রিয়াকলাপ: যোগ এবং স্থানান্তর ক্রিয়াকলাপের মোট সংখ্যা ३. অ্যাসিম্পটোটিক জটিলতা: $O(n^{\log_4 3}) \approx O(n^{2.792})$ ४. ধ্রুবক পদ: প্রধান ধ্রুবক এবং নিম্ন-ক্রম পদ সহগ

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

মান সরল-রেখা প্রোগ্রাম (তালিকা १-४)

ক্রিয়াকলাপ বিয়োজন:

$L$ ম্যাট্রিক্স: १०४টি যোগ
$R$ ম্যাট্রিক্স: ८४টি যোগ + १টি গুণন (বাইনারি স্থানান্তর)
$P$ ম্যাট্রিক্স: ११९টি যোগ + ३३টি গুণন (বাইনারি স্থানান্তর)
মোট: ३४१টি ক্রিয়াকলাপ

জটিলতা সীমা: $\left(1 + \frac{341}{48-16}\right)n^{2+\log_4 3} - \frac{341}{32}n^2 \approx 11.65625n^{2.792} - 10.65625n^2$

বিকল্প ভিত্তি রূপান্তর (পরিশিষ্ট C)

ক্রিয়াকলাপ বিয়োজন:

$L_{alt}$ : १টি যোগ
$R_{alt}$ : २টি যোগ
$P_{alt}$ : ३টি যোগ
মোট: ६টি ক্রিয়াকলাপ

ভিত্তি রূপান্তর খরচ:

CoB_L: १०३টি যোগ
CoB_R: ७९টি যোগ + ५টি গুণন
CoB_P: ११६টি যোগ + ३३টি গুণন
মোট: ३३६টি ক্রিয়াকলাপ

জটিলতা সীমা: $7n^{2.792} + \frac{336}{31}(n^{\log_4 47} - n^2) = 7n^{2.792} + o(n^{2.792})$

বিদ্যমান পদ্ধতির সাথে তুলনা

পদ্ধতি	গুণনের সংখ্যা	সহগ ক্ষেত্র	প্রযোজ্য বলয়	জটিলতা ধ্রুবক
Strassen (२ স্তর)	४९	মূলদ সংখ্যা	যেকোনো	-
Fawzi ইত্যাদি 5	४७	মূলদ সংখ্যা	বৈশিষ্ট্য २	-
AlphaEvolve 11	४८	জটিল সংখ্যা	জটিল ক্ষেত্র	-
এই পেপার (মান)	४८	মূলদ সংখ্যা	$\frac{1}{2}$ সহ বলয়	११.६६
এই পেপার (বিকল্প ভিত্তি)	४८	মূলদ সংখ্যা	$\frac{1}{2}$ সহ বলয়	७.००

মূল আবিষ্কার

१. অস্তিত্ব প্রমাণ: AlphaEvolve অ্যালগরিদমের সমদূরবর্তী কক্ষপথে সত্যিই মূলদ সংখ্যা বিন্দু বিদ্যমান প্রমাণ করা, এটি স্পষ্ট নয়

२. সহগ সরলতা: সমস্ত সহগ $\{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$ , বাস্তবায়ন সহজ

३. অপ্টিমাইজেশন প্যারাডক্স: যদিও $R$ ম্যাট্রিক্স সহগ শুধুমাত্র $\{-1, 0, 1\}$ , সর্বোত্তম সরল-রেখা প্রোগ্রাম এখনও অ-তুচ্ছ গুণন প্রয়োজন (কার্নেল বিয়োজনের কারণে)

४. বিকল্প ভিত্তি সুবিধা: ভিত্তি রূপান্তরের মাধ্যমে প্রধান ধ্রুবক ११.६६ থেকে ७.०० এ হ্রাস করা যায়, খরচ $o(n^{2.792})$ ভিত্তি রূপান্তর

१. AlphaEvolve এর জটিল সংখ্যা অ্যালগরিদম সফলভাবে মূলদ সংখ্যা অ্যালগরিদমে রূপান্তরিত, ४८টি গুণন বজায় রেখে २. সমদূরবর্তী গোষ্ঠী ক্রিয়া অ্যালগরিদম স্থান পদ্ধতিগতভাবে অন্বেষণের জন্য কার্যকর সরঞ্জাম ३. দুটি বাস্তবায়ন প্রদান: মান সংস্করণ (३४१ ক্রিয়াকলাপ) এবং বিকল্প ভিত্তি সংস্করণ (६+३३६ ক্রিয়াকলাপ) ४. অ্যালগরিদম $\frac{1}{2}$ সহ যেকোনো বলয়ে প্রয়োগযোগ্য, প্রয়োগের পরিসীমা প্রসারিত করে

সীমাবদ্ধতা

१. বলয়ের সীমাবদ্ধতা: २ বিপরীত প্রয়োজন, বৈশিষ্ট্য २ এর ক্ষেত্রে প্রয়োগযোগ্য নয় २. বড় ধ্রুবক পদ: মান সংস্করণ ধ্রুবক ११.६६ বড়, শুধুমাত্র যথেষ্ট বড় ম্যাট্রিক্সে সুবিধা আছে ३. সংখ্যাগত স্থিতিশীলতা অজানা: এখনও २ এর মতো সংখ্যাগত নির্ভুলতা বিশ্লেষণ সম্পন্ন হয়নি ४. অ-গঠনমূলক: সমদূরবর্তী রূপান্তরের আবিষ্কার এখনও "শিক্ষিত অনুমান" এর উপর নির্ভর করে, সম্পূর্ণভাবে স্বয়ংক্রিয় নয়

ভবিষ্যত দিকনির্দেশনা

१. ३×४×७ অ্যালগরিদম: যমজ পেপার ३ AlphaEvolve এর অন্য জটিল অ্যালগরিদম পরিচালনা করে २. সংখ্যাগত বিশ্লেষণ: এই অ্যালগরিদমের ত্রুটি প্রসার এবং শর্ত সংখ্যা গবেষণা ३. স্বয়ংক্রিয় আবিষ্কার: সমদূরবর্তী রূপান্তর স্বয়ংক্রিয়ভাবে অনুসন্ধানের জন্য পদ্ধতিগত পদ্ধতি উন্নয়ন ४. অন্যান্য মাত্রা: ५×५, ३×३×३ ইত্যাদি ক্ষেত্রে একই পদ্ধতি প্রয়োগ ५. ব্যবহারিক কর্মক্ষমতা: প্রকৃত হার্ডওয়্যারে কর্মক্ষমতা পরীক্ষা, ক্যাশে, সমান্তরালতা ইত্যাদি বিবেচনা

গভীর মূল্যায়ন

সুবিধা

१. উল্লেখযোগ্য তাত্ত্বিক অবদান

গুরুত্বপূর্ণ ফাঁক পূরণ: AlphaEvolve অ্যালগরিদমের জটিল সংখ্যা সহগ সীমাবদ্ধতা এই ব্যবহারিক সমস্যা সমাধান করা
পদ্ধতিগত উদ্ভাবন: সমদূরবর্তী গোষ্ঠী তত্ত্ব পদ্ধতিগতভাবে প্রয়োগ, জটিল থেকে মূলদ সংখ্যায় তাত্ত্বিক পথ প্রদান
গাণিতিক কঠোরতা: Landsberg এর টেনসর জ্যামিতি তত্ত্বের উপর ভিত্তি করে, দৃঢ় বীজগণিত জ্যামিতি ভিত্তি

२. উচ্চ ব্যবহারিক মূল্য

সম্পূর্ণ বাস্তবায়ন: সরল-রেখা প্রোগ্রাম এবং LRP ম্যাট্রিক্স প্রদান, সরাসরি ব্যবহার করা যায়
খোলা উৎস পুনরুৎপাদনযোগ্য: সমস্ত ডেটা এবং কোড PLinOpt লাইব্রেরিতে জনসাধারণের জন্য উপলব্ধ
বিস্তৃত প্রয়োগযোগ্যতা: মূলদ সহগ অ্যালগরিদমকে পূর্ণসংখ্যা, মূলদ সংখ্যা, সীমিত ক্ষেত্র (বিজোড় বৈশিষ্ট্য) ইত্যাদিতে ব্যবহার করা যায়

३. পর্যাপ্ত প্রযুক্তিগত বিবরণ

সম্পূর্ণ অ্যালগরিদম প্রদর্শন: সমীকরণ २५-७२ সমস্ত ४८টি গুণন পদ বিস্তারিত তালিকাভুক্ত করে
বহুবিধ প্রতিনিধিত্ব: ত্রিরৈখিক ফর্ম, LRP ম্যাট্রিক্স, সরল-রেখা প্রোগ্রাম ইত্যাদি বিভিন্ন প্রতিনিধিত্ব প্রদান
অপ্টিমাইজেশন কৌশল: কার্নেল বিয়োজন এবং বিকল্প ভিত্তি ইত্যাদি অপ্টিমাইজেশন কৌশল প্রদর্শন

४. স্পষ্ট লেখা

পর্যাপ্ত পটভূমি পরিচয়: Strassen অ্যালগরিদম থেকে টেনসর বিয়োজন তত্ত্ব পর্যন্ত ধাপে ধাপে প্রবর্তন
সমৃদ্ধ উদাহরণ: উদাহরণ २.१ সমদূরবর্তী কীভাবে জটিল সংখ্যা প্রবর্তন করে তা প্রদর্শন করে
পদ্ধতিগত প্রতীক: সংজ্ঞা স্পষ্ট, প্রতীক সামঞ্জস্যপূর্ণ

অপূর্ণতা

१. পদ্ধতির সীমাবদ্ধতা

সমদূরবর্তী রূপান্তরের আবিষ্কার: "শিক্ষিত অনুমান" ব্যবহার স্বীকার করে, পদ্ধতিগত অনুসন্ধান পদ্ধতি অভাব
স্থিতিশীল উপগোষ্ঠী নির্ভরতা: ইতিমধ্যে পরিচিত স্থিতিশীল উপগোষ্ঠী $(C_2 \times D_4) \rtimes C_2$ প্রয়োজন, নতুন সমস্যায় প্রয়োগ করা কঠিন হতে পারে
বৈশিষ্ট্য সীমাবদ্ধতা: বৈশিষ্ট্য २ এর ক্ষেত্রে প্রয়োগযোগ্য নয় (Fawzi এর ४७-গুণন অ্যালগরিদম বরং প্রয়োগযোগ্য)

२. পরীক্ষামূলক বিশ্লেষণ অপূর্ণ

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

३. তাত্ত্বিক গভীরতা

অস্তিত্ব প্রমাণ অসম্পূর্ণ: শুধুমাত্র একটি মূলদ বিন্দু প্রদর্শন করে, এর অনন্যতা বা সর্বোত্তমতা প্রমাণ করা হয়নি
কক্ষপথ কাঠামো অন্বেষণ অভাব: মূলদ বিন্দু কক্ষপথে অবস্থান, সংখ্যা ইত্যাদি সমস্যা আলোচনা করা হয়নি
নিম্ন সীমা অন্তর্ভুক্ত নয়: ४×४ ম্যাট্রিক্স গুণনের তাত্ত্বিক নিম্ন সীমা আলোচনা করা হয়নি (<४८ সম্ভব কিনা?)

४. অভিব্যক্তি বিবরণ

জটিল প্রতীক: বিস্তৃত সাবস্ক্রিপ্ট এবং টেনসর স্বরলিপি অ-বিশেষজ্ঞদের জন্য অ-বন্ধুত্বপূর্ণ হতে পারে
কোড পাঠযোগ্যতা: সরল-রেখা প্রোগ্রাম (তালিকা १-४) মন্তব্য অভাব
ম্যাট্রিক্স প্রদর্শন: পরিশিষ্ট B এর বড় ম্যাট্রিক্স সরাসরি বোঝা কঠিন

প্রভাব

ক্ষেত্রে অবদান

१. তত্ত্ব এবং অনুশীলন সেতু: AI আবিষ্কৃত অ্যালগরিদম গণিত তত্ত্বে রূপান্তরিত করে ব্যবহারযোগ্য ফর্মে २. পদ্ধতিগত প্রদর্শন: অ্যালগরিদম অপ্টিমাইজেশনে সমদূরবর্তী গোষ্ঠী তত্ত্বের ব্যবহারিক প্রয়োগ প্রদর্শন ३. পরবর্তী গবেষণা অনুপ্রেরণা: অন্যান্য AI আবিষ্কৃত জটিল অ্যালগরিদম পরিচালনার জন্য টেমপ্লেট প্রদান

ব্যবহারিক মূল্য

१. মধ্যম: বড় ধ্রুবক পদ (११.६६) এর কারণে, শুধুমাত্র বড় স্কেল ম্যাট্রিক্সে ( $n > 100$ ) সুবিধা আছে २. নির্দিষ্ট ক্ষেত্র: নির্ভুল মূলদ সংখ্যা গণনা প্রয়োজন এমন প্রতীকী গণনা সিস্টেমে উচ্চতর মূল্য ३. শিক্ষামূলক তাৎপর্য: টেনসর বিয়োজন এবং সমদূরবর্তী গোষ্ঠী তত্ত্ব প্রয়োগের চমৎকার কেস স্টাডি

পুনরুৎপাদনযোগ্যতা

চমৎকার: সম্পূর্ণ ম্যাট্রিক্স, কোড এবং সরঞ্জাম শৃঙ্খল জনসাধারণের জন্য উপলব্ধ
ব্যবহারযোগ্যতা: PLinOpt লাইব্রেরি স্বয়ংক্রিয়ভাবে সরল-রেখা প্রোগ্রাম উৎপন্ন করার সরঞ্জাম প্রদান করে
সম্পূর্ণ ডকুমেন্টেশন: পরিশিষ্ট সমস্ত ডেটা ফাইল অবস্থান বিস্তারিত তালিকাভুক্ত করে

প্রয়োগের দৃশ্য

আদর্শ প্রয়োগ দৃশ্য

१. প্রতীকী গণনা সিস্টেম: Maple, Mathematica ইত্যাদিতে নির্ভুল ম্যাট্রিক্স ক্রিয়াকলাপ २. সীমিত ক্ষেত্র গণনা: বিজোড় বৈশিষ্ট্য সীমিত ক্ষেত্রে রৈখিক বীজগণিত ३. বড় স্কেল ম্যাট্রিক্স: পুনরাবৃত্তিমূলক প্রয়োগের মাধ্যমে $n \geq 128$ ম্যাট্রিক্সে ४. তাত্ত্বিক গবেষণা: দ্রুত অ্যালগরিদম এবং টেনসর র‍্যাঙ্ক গবেষণার সরঞ্জাম

অপ্রয়োগযোগ্য দৃশ্য

१. ছোট ম্যাট্রিক্স: একক ४×४ ম্যাট্রিক্সের জন্য, নিষ্পাপ অ্যালগরিদম (६४ গুণন) ছোট ধ্রুবক পদের কারণে দ্রুত হতে পারে २. ভাসমান বিন্দু গণনা: সংখ্যাগত স্থিতিশীলতা অজানা, ঐতিহ্যবাহী অ্যালগরিদমের চেয়ে কম স্থিতিশীল হতে পারে ३. বৈশিষ্ট্য २ ক্ষেত্র: Fawzi এর ४७-গুণন অ্যালগরিদম আরও ভাল ४. হার্ডওয়্যার ত্বরণ: আধুনিক GPU অপ্টিমাইজড ম্যাট্রিক্স গুণন দ্রুত হতে পারে

রেফারেন্স

মূল উদ্ধৃতি

१. १३ Strassen (१९६९): "Gaussian elimination is not optimal" - দ্রুত ম্যাট্রিক্স গুণনের ভিত্তিপ্রস্তর কাজ २. ६,७ de Groote (१९७८): সমদূরবর্তী গোষ্ঠী তত্ত্বের মূল পেপার ३. ११ Novikov ইত্যাদি (२०२५): AlphaEvolve - এই পেপার উন্নত মূল জটিল অ্যালগরিদম ४. १० Landsberg (२०१६): "Geometry and complexity theory" - তাত্ত্বিক ভিত্তি ५. २ Dumas ইত্যাদি (२०२४): Strassen অ্যালগরিদমের সংখ্যাগত নির্ভুলতা বিশ্লেষণ

সামগ্রিক মূল্যায়ন

এটি একটি উচ্চ মানের তাত্ত্বিক কম্পিউটার বিজ্ঞান পেপার, যা সফলভাবে AI আবিষ্কৃত জটিল ক্ষেত্রের অ্যালগরিদমকে মূলদ ক্ষেত্রের অ্যালগরিদমে রূপান্তরিত করে, উল্লেখযোগ্য তাত্ত্বিক তাৎপর্য এবং নির্দিষ্ট ব্যবহারিক মূল্য রয়েছে। পেপারের প্রধান সুবিধা:

१. ব্যবহারিক সমস্যা সমাধান: AlphaEvolve এর জটিল সংখ্যা সহগ সীমাবদ্ধতা সমাধান করা २. পদ্ধতি কঠোর: পরিপক্ক টেনসর বিয়োজন এবং সমদূরবর্তী গোষ্ঠী তত্ত্যের উপর ভিত্তি করে ३. বাস্তবায়ন সম্পূর্ণ: পুনরুৎপাদনযোগ্য খোলা উৎস বাস্তবায়ন প্রদান করা

প্রধান অপূর্ণতা: १. সমদূরবর্তী রূপান্তরের আবিষ্কার এখনও মানব অনুমানের প্রয়োজন २. প্রকৃত কর্মক্ষমতা এবং সংখ্যাগত স্থিতিশীলতা বিশ্লেষণ অভাব ३. বড় ধ্রুবক পদ ব্যবহারিক প্রয়োগ সীমিত করে

সুপারিশ সূচক: ⭐⭐⭐⭐ (५ এর মধ্যে ४)
প্রতীকী গণনা, টেনসর বিয়োজন, দ্রুত অ্যালগরিদমে আগ্রহী গবেষকদের জন্য পড়ার যোগ্য। ব্যবহারিক প্রয়োগের জন্য, নির্দিষ্ট পরিস্থিতিতে ঐতিহ্যবাহী পদ্ধতির চেয়ে উন্নত কিনা তা মূল্যায়ন করা প্রয়োজন।