Thuật toán tính đa thức dual stable Grothendieck

Đa thức dual Grothendieck \(g_\lambda(x_1,\dots,x_n)\) xuất phát từ các reverse plane partition (RPP) với quy tắc trọng số đo bằng số cột thay vì số ô. Cách tiếp cận tổ hợp kinh điển thường giải recurrence trên cặp \((\text{Partition}, \text{Powers})\): theo dõi hình Young 2D trên dàn poset dày đặc và duy trì bảng băm rời rạc cho từng đơn thức — mô hình sớm chạm trần hiệu năng vì kiểm tra bao hàm 2D tốn kém và bùng nổ hoán vị biến trên heap.

Bài viết này trình bày bước chuyển tư duy cốt lõi sang cặp biểu diễn \((\text{Col-Profile}, \mathrm{orb})\): nén hình dạng 2D thành dãy chiều cao cột (đóng gói trong bitfield u64) và tận dụng tính đối xứng để gom các đơn thức về một đại diện quỹ đạo duy nhất \(\mathrm{orb}\). Cầu nối quyết định gồm hai trục tương hỗ: ma trận thưa \(K_\lambda\) điều phối bước chuyển shape từ \(\nu\) sang \(\mu\) sinh ra số gia bậc nguyên \(d = \operatorname{inc}(a,b)\), và bảng tra tĩnh OrbitLUT tiếp nhận \(d\) để chuyển dịch quỹ đạo \(\mathrm{orb}\) tương ứng trong \(O(1)\).

Đặc biệt, toàn bộ kiến trúc được phân tách thành hai pha triệt để: ngay ở giai đoạn chuẩn bị (prepare), ta sinh sẵn toàn bộ không gian \(\mathrm{orb}\) kèm bảng tra tĩnh OrbitLUT đồng thời dựng ma trận chuyển tiếp transducer sang dạng thưa (CSR). Nhờ đó, giai đoạn tính toán (runtime) bỏ qua hoàn toàn việc sinh powers hay duyệt lại đồ thị, thu gọn về chuỗi Transfer–SpMV — phép nhân ma trận thưa với vector hiệu năng cao trên các mảng bộ nhớ phẳng liên tục.

1. Bài toán gốc: trọng số nhìn theo cột

Với \(\lambda=(1,1)\), hai số 1 có thể nằm trong hai ô nhưng vẫn chỉ chiếm một cột. Vì vậy RPP đó đóng góp \(x_1\), không phải \(x_1^2\). Với hai giá trị \(1,2\), ta được

\[ g_{(1,1)}(x_1,x_2)=x_1+x_1x_2+x_2. \]

Trực giác cần giữ lại là: mỗi cột chỉ báo “có” hoặc “không có” giá trị \(k\). Hình bên phải quét năm RPP của \(\lambda=(2,1)\) theo đúng quy tắc này.

2. Ý tưởng 1: Đi theo từng lớp giá trị thay vì cả bảng

Thay vì sinh toàn bộ bảng số cùng lúc, ta có thể xây dựng RPP dần dần bằng cách thêm lần lượt các ô mang giá trị \(1\), rồi đến \(2\), rồi đến \(k\).

Cơ sở hình học: Theo luật điền số của RPP (tăng yếu theo hàng và cột), các giá trị nhỏ luôn dồn về góc trên-trái (top-left). Do đó, với mọi ngưỡng \(k\), tập hợp các ô có giá trị \(\le k\) luôn tạo thành một Young diagram hợp lệ. Điều này cho phép ta mô hình hóa quá trình điền bảng thành một chuỗi mở rộng các partition lồng nhau: \(\varnothing \subseteq \mu^{(1)} \subseteq \mu^{(2)} \subseteq \cdots \subseteq \lambda\). Nói cách khác, bài toán chuyển từ sinh từng RPP hoàn chỉnh sang tìm các đường đi phát triển partition trên dàn Young (Young lattice).

Tại mỗi bước chuyển \(\nu \subseteq \mu\), các ô mới thêm \(\mu / \nu\) mang cùng giá trị \(k\). Theo định nghĩa, số mũ của \(x_k\) chính là số cột của \(\mu / \nu\). Gọi số cột này là \(c(\nu,\mu)\), ta thu được hệ thức truy hồi nền tảng:

\[ g_\mu(x_1,\dots,x_k) = \sum_{\nu \subseteq \mu} g_\nu(x_1,\dots,x_{k-1}) \cdot x_k^{c(\nu,\mu)}, \qquad g_\varnothing = 1. \]

Đây là bước đổi tư duy đầu tiên: từ một tập lớn các đối tượng hoàn chỉnh sang một chuỗi chuyển trạng thái nhỏ hơn. Tuy nhiên, hai nút thắt lớn nhất của thuật toán bắt đầu lộ diện tại đây:

1. [P1] Đồ thị chuyển trạng thái cực dày (dense transitions): Khác với đa thức Schur (phần thêm vào \(\mu/\nu\) bị chặn thành horizontal strip), skew shape \(\mu/\nu\) trong dual Grothendieck là tùy ý — một cột có thể thêm bao nhiêu ô cũng được. Do đó, một nhánh chuyển tiếp có thể “nhảy cóc” qua nhiều tầng trên dàn Young, nối từ một partition nhỏ \(\nu\) lên một partition \(\mu\) lớn hơn rất nhiều. Vì mọi cặp thỏa mãn \(\nu \subseteq \mu\) đều tạo thành một cạnh (edge) hợp lệ mang skew shape \(\mu/\nu\), số cặp có cận trên \(\mathcal{O}(|P(\lambda)|^2)\). Nếu duyệt tường minh, chi phí chuyển trạng thái phụ thuộc số cặp bao hàm này; đây chưa phải cận dưới cho mọi cách áp dụng recurrence.

   Ghi chú lý thuyết thứ tự: Đồ thị chuyển trạng thái ở đây thực chất chính là bao đóng bắc cầu (transitive closure / poset order) của dàn Young, chứa toàn bộ các cặp so sánh được \(\nu \subseteq \mu\), thay vì chỉ đi theo các cạnh liền kề (covering relations) của biểu đồ Hasse thông thường.

2. [P2] Nghẽn biểu diễn đa thức (polynomial payload): Tại mỗi nút trạng thái, giá trị lưu trữ không phải là một số nguyên mà là cả một đa thức nhiều biến. Chi phí nhân \(x_k^c\), băm (hash) và cộng gộp hàng loạt đơn thức thưa ở mỗi nhánh chuyển tiếp sẽ nhanh chóng làm tràn bộ nhớ và nghẽn CPU.

Các bước phát triển trong symfuncrs tiếp cận hai bài toán này theo hai hướng thực dụng:

• [Sol1] Giảm nhẹ chi phí đồ thị dày (cho P1): Trong các backend transfer, số cặp so sánh \(L(\lambda) = |\{(a,b): a \le b\}|\) là cố định theo poset, việc chuẩn bị operator không đổi số cạnh lý thuyết mà quản lý chúng hiệu quả hơn: gom các nhánh chuyển tiếp vào một ma trận chuyển trạng thái được dựng sẵn một lần (prepare) rồi tái sử dụng qua các biến, đồng thời áp dụng phân tầng frontier để chỉ quét những trạng thái thực sự active ở từng lớp.
• [Sol2] Thu gọn biểu diễn đa thức (cho P2): Tận dụng tính đối xứng để gom các đơn thức có cùng hoán vị số mũ vào các khóa quỹ đạo (orbit key). Nhờ đó, việc tích lũy hệ số được chuyển từ thao tác băm/tra cứu bảng (HashMap) sang phép nhân ma trận thưa với vector (SpMV) trên mảng nhớ liên tục, giúp giảm đáng kể chi phí cấp phát và quản lý bộ nhớ.

Góc nhìn bản chất: Toán học vs. Kỹ thuật hệ thống

1. Với [P2] (Nghẽn biểu diễn đa thức): Giải quyết cốt lõi bằng TOÁN ĐỐI XỨNG
   • Bản chất toán học: Đa thức \(g_\lambda\) là đa thức đối xứng (symmetric polynomial). Nhờ tính đối xứng này, mọi đơn thức thuộc cùng một quỹ đạo hoán vị số mũ (orbit of exponent partition) đều có chung một hệ số nguyên duy nhất.
   • Kỹ thuật code: Hiện thực hóa tính chất toán học trên thành mảng phẳng, bảng tra tĩnh OrbitLUT và phép nhân SpMV.
2. Với [P1] (Đồ thị chuyển trạng thái dày): Phân biệt quan hệ với cách tính tổng
   • Cấu trúc toán học: Số cặp so sánh \(L(\lambda) = |\{(a, b) : a \le b\}|\) cố định theo shape, nhưng không bắt buộc thuật toán lưu hoặc duyệt từng cặp. Phân tích operator thành các lượt quét cột cho phép tính cùng tổng bằng \(O(wP)\) phép toán trên payload mỗi lớp, với \(w\) là số cột và \(P\) là số profile.
   • Kỹ thuật code: Dùng cấu trúc dữ liệu ma trận thưa (CSR), tách phase dựng sẵn (prepare) một lần và lọc tập hoạt động (active frontier) trong lúc chạy để tránh duyệt lãng phí.

Phép quét cột này được hiện thực trong backend nghiên cứu Fiber-Zeta: ở mỗi nhóm trạng thái chỉ khác chiều cao một cột, dùng tổng tiền tố để cộng các nguồn thấp hơn. Giảm số lượt điều phối không bảo đảm giảm tương ứng thời gian chạy, vì mỗi lượt vẫn xử lý payload đa thức. Các thử nghiệm với payload thường và payload quỹ đạo chưa cho cơ sở thay backend mặc định trên toàn bộ miền đã đo.

3. Bước 2: Column profile

Thông thường, một phân hoạch \(\lambda = (\lambda_1, \lambda_2, \dots)\) được biểu diễn theo độ dài các hàng (\(\lambda_1 \ge \lambda_2 \ge \dots\)). Tuy nhiên, trong đa thức dual Grothendieck (qua định nghĩa RPP), số mũ của biến \(x_k\) được đo bằng số cột có chứa giá trị \(k\). Vì vậy, thuật toán đổi góc nhìn sang chiều cao từng cột (tương ứng với partition liên hợp \(\lambda'\)).

Sự chuyển dịch từ hàng sang cột này đem lại hai lợi thế then chốt:

1. Gắn trọng số tức thì: Cứ mỗi cột có thêm ô mới của lớp \(k\) (chiều cao cột tăng) là ta nhân thêm \(x_k\).
2. Khử phụ thuộc toàn cục: Điều kiện “tạo thành một Young diagram hợp lệ” quy về đúng một luật cục bộ từ trái sang phải: cột sau không được cao hơn cột liền trước (\(b_j \le b_{j-1}\)).

Để máy tính kiểm tra điều kiện bao hàm \(\nu\subseteq\mu\) và đếm số cột dàn trải hiệu quả, ta mã hóa hai partition thành hai dãy chiều cao cột (profile):

\[ a=(a_1,\ldots,a_w),\qquad b=(b_1,\ldots,b_w). \]

Khi đó, quan hệ \(\nu\subseteq\mu\) quy về so sánh từng tọa độ:

\[ a_j \le b_j \quad (\forall j = 1, \dots, w), \]

còn số cột dàn trải chính là số tọa độ tăng:

\[ \operatorname{inc}(a,b) = \#\{j: b_j > a_j\}. \]

4. Bước 3: Weighted transducer quét từng cột

Từ một partition nguồn \(a\), thay vì phải thử toàn bộ không gian để tìm partition đích \(b\), ta dùng một weighted transducer để sinh trực tiếp mọi nhánh chuyển tiếp \(a\to b\) hợp lệ.

Ở mỗi cột \(j\), máy chỉ nhớ chiều cao đích trước đó, chọn \(b_j\) thỏa mãn \(a_j \le b_j \le b_{j-1}\), rồi nhân \(y\) nếu cột tăng và nhân \(1\) nếu cột giữ nguyên. Toàn bộ quá trình quét này sinh ra các nhánh chuyển tiếp trên lattice, mỗi nhánh gắn liền với trọng số tích lũy \(y^{\operatorname{inc}(a,b)}\).

Ví dụ từ \(a=(2,0,0)\), Transducer sinh ra đúng 10 nhánh chuyển tiếp hợp lệ nằm trong \(\lambda=(3,2,1)\) (thỏa mãn \(b \subseteq \lambda\)). Trong đó, nhánh chuyển tiếp dẫn tới \(b=(3,2,1)\) có cả ba cột đều tăng nên mang trọng số \(y^3\) (sẽ thay \(y=x_k\) khi tính đa thức).

5. Bước 4: Từ các nhánh chuyển tiếp đến operator tái sử dụng

Transducer được áp dụng trên tập profile con của \(\lambda\) (các \(a \subseteq \lambda\)). Thay vì khám phá lại cùng cấu trúc ở mỗi biến, ta gom mọi nhánh chuyển tiếp thành một operator:

\[ K_\lambda(y)[b,a]= \begin{cases} y^{\operatorname{inc}(a,b)},&a\subseteq b,\\ 0,&\text{ngược lại.} \end{cases} \]

Ma trận \(K_\lambda(y)\) hé lộ hai đặc tính cấu trúc mấu chốt:

1. Tam giác dưới & đường chéo bằng 1: Vì nhánh chuyển tiếp chỉ đi từ profile con sang profile cha (\(a \subseteq b \implies \text{hàng } b \ge \text{cột } a\)), toàn bộ tam giác trên bằng 0. Đường chéo chính luôn là \(1\) (\(a \to a\) không thêm ô nào nên \(y^0 = 1\)). Cấu trúc tam giác dưới này khớp hoàn hảo với phép nhân ma trận - vector cột \(\mathbf{V}_k = K_\lambda(x_k) \mathbf{V}_{k-1}\) và định dạng CSR trong thực tế (mỗi hàng đại diện cho một slice đích nhận dữ liệu từ các cột nguồn phía trước).
2. Mỗi hàng thu thập toàn bộ nguồn dẫn về đích: Bấm vào hàng đích \(b = (3,2,1)\): bạn sẽ thấy hàng này gom các nhánh từ các nguồn con đổ về; ngược lại, bấm vào cột nguồn \(a = (2,0,0)\) sẽ thấy đúng 10 nhánh chuyển tiếp phân tỏa ra các đích — trùng khớp với 10 nhánh mà Transducer đã quét ở Figure 5!

Vai trò cốt lõi: Ma trận \(K_\lambda\) giảm tải cho [P1] bằng cách gom các nhánh chuyển tiếp dày đặc vào một toán tử dựng sẵn một lần; cấu trúc này đồng thời tạo khung để phép nén đa thức của [P2] có thể thực thi qua SpMV ở bước sau.

Đây là lần tách quan trọng đầu tiên: cấu trúc các nhánh chuyển tiếp thuộc về \(\lambda\) và được chuẩn bị trước (prepare) một lần duy nhất, còn khi duyệt qua các lớp biến \(x_k\), ta chỉ việc tái sử dụng ma trận này và thế \(y = x_k\). Payload vẫn gồm nhiều đơn thức thưa phải băm và cộng gộp, nên nút thắt tiếp theo nằm ở cách biểu diễn hệ số.

6. Bước 5: Nén đối xứng (Symmetric / Orbit Compression)

Sau khi ma trận chuyển tiếp \(K_\lambda(y)\) đóng băng toàn bộ cấu trúc đồ thị dày của [P1], nút thắt lớn còn lại là [P2]: Bùng nổ đơn thức (Monomial Combinatorial Explosion).

Bản chất giải pháp cho [P2]: Lưu đa thức bằng HashMap<Powers, i64> chịu sự lãng phí kép: khóa Powers (64 bytes) thừa thãi nhiều ô 0, trong khi các đơn thức hoán vị cùng hệ số lại bị nhân bản thành hàng trăm bucket rời rạc trên Heap. Hướng đi hiệu quả không phải là cố gắng tối ưu bảng băm, mà đến từ việc tận dụng trực tiếp tính đối xứng của hàm toán học để nén toàn bộ quỹ đạo hoán vị về một phân hoạch đại diện duy nhất.

Bản chất toán học: Nhóm hoán vị \(S_n\) và Quỹ đạo số mũ

Đa thức dual Grothendieck \(g_\lambda(x_1, \dots, x_n)\) là một đa thức đối xứng (symmetric polynomial). Giá trị của nó hoàn toàn bất biến dưới mọi phép hoán vị (đổi chỗ) các biến:

\[ g_\lambda(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)}) = g_\lambda(x_1, x_2, \dots, x_n). \]

Từ tính chất này, ta có một định lý then chốt: Mọi đơn thức có cùng bộ số mũ (chỉ khác thứ tự hoán vị) bắt buộc phải có chung một hệ số nguyên duy nhất.

Ví dụ với 3 biến \((x_1, x_2, x_3)\), xét 6 đơn thức có bộ số mũ là hoán vị của \((2, 1, 0)\):

\[ x_1^2 x_2^1 x_3^0, \quad x_1^1 x_2^2 x_3^0, \quad x_1^2 x_3^1 x_2^0, \quad x_1^0 x_2^2 x_3^1, \quad x_1^1 x_3^2 x_2^0, \quad x_1^0 x_2^1 x_3^2. \]

Tất cả 6 đơn thức này lập thành một quỹ đạo (orbit) dưới tác động của nhóm đối xứng \(S_3\). Trong đa thức kết quả, nếu \(x_1^2 x_2\) có hệ số là \(+c\), thì cả 5 đơn thức còn lại chắc chắn cũng mang đúng hệ số \(+c\).

Cơ chế nén: Gom về Khóa quỹ đạo (Orbit Key)

Thay vì theo dõi từng đơn thức riêng lẻ, thuật toán chuẩn hóa toàn bộ các đơn thức trong cùng một quỹ đạo về một đại diện duy nhất: dãy số mũ khác không sắp xếp giảm dần (Integer Partition).

Tất cả 6 đơn thức trên được gom vào đúng một Khóa quỹ đạo (Orbit Key):

\[ \mathrm{orb} = (2, 1). \]

Về mặt đại số, đây chính là việc đổi cơ sở biểu diễn sang hàm đối xứng đơn thức (monomial symmetric functions \(m_{\mathrm{orb}}\)):

\[ g_\lambda(x_1, \dots, x_n) = \sum_{\mathrm{orb}} c_{\mathrm{orb}} \cdot m_{\mathrm{orb}}(x_1, \dots, x_n) \]

với \(m_{\mathrm{orb}} = \sum_{\alpha \in \operatorname{Perm}(\mathrm{orb})} x_1^{\alpha_1} \dots x_n^{\alpha_n}\). Tại mỗi nút profile, thay vì phải duy trì hàng trăm cặp (key, value) trong HashMap, bộ nhớ chỉ cần lưu đúng một hệ số nguyên \(c_{\mathrm{orb}}\) đại diện cho toàn bộ quỹ đạo \(\mathrm{orb}\).

Tỷ lệ nén dữ liệu thực tế

Trong khi số lượng đơn thức riêng lẻ bùng nổ theo cấp số tổ hợp của số biến \(n\), số lượng phân hoạch nguyên (số orbit key) lại tăng rất chậm:

Số biến (\(n\))	Số đơn thức rời rạc (chưa nén)	Số Khóa quỹ đạo (đã nén)	Tỷ lệ thu gọn dung lượng
\(n = 4\)	Vài trăm đơn thức	~15 orbit	~20×
\(n = 8\)	Hàng chục ngàn	~50 orbit	~500×
\(n = 16\)	Hàng triệu	~100 – 200 orbit	~10.000×

7. OrbitLUT: Bảng tra tĩnh và quy tắc chuyển trạng thái \(O(1)\)

Ưu điểm quyết định của nén quỹ đạo không chỉ dừng lại ở việc tiết kiệm RAM, mà nằm ở tính tất định tuyệt đối của quy tắc chuyển trạng thái:

Khi nhân thêm biến \(x_k^d\) (với \(d = \operatorname{inc}(a, b)\) là số cột tăng giữa hai profile), một quỹ đạo \(\mathrm{orb}\) chỉ đơn giản là hấp thụ thêm một phần tử số mũ \(d\) vào phân hoạch:

\[ \mathrm{orb} \xrightarrow{\;\text{nhân thêm } x_k^d\;} \operatorname{insert\_sorted}(d) \longrightarrow \mathrm{orb}'. \]

Ví dụ: \((2, 1)\) nhận thêm \(x_k^3 \implies \operatorname{insert\_sorted}((2,1), 3) = (3, 2, 1)\).

Quy tắc chuyển dịch này hoàn toàn độc lập với vị trí biến \(k\) hay giá trị của biến. Nó khẳng định rằng trạng thái quỹ đạo mới chỉ phụ thuộc duy nhất vào cặp \((\mathrm{src\_orb}, d)\), mở đường cho việc khử sạch mọi cấu trúc bảng băm động lúc runtime. Toàn bộ quá trình đại số được số hóa thành bảng tra tĩnh OrbitLUT trong pha prepare:

1. Đánh chỉ số cố định (Static Indexing) và Young’s Lattice: Toàn bộ các orbit được sinh sẵn một lần trong pha prepare và gán ID nguyên cố định theo thứ tự phân bậc:

   \[ 0 \to \emptyset, \quad 1 \to (1), \quad 2 \to (2), \quad 3 \to (1,1), \quad 4 \to (3), \quad 5 \to (2,1), \dots \]

   Bản thân tập hợp các phân hoạch này tạo thành Young’s Lattice (\(\mathbb{Y}\)) phân tầng theo tổng bậc \(|\lambda|\). Việc gán ID \(0, 1, 2, \dots\) chính là phép tuyến tính hóa topo (topological linear extension) của lattice, bảo đảm quỹ đạo cha luôn mang ID nhỏ hơn quỹ đạo con.

2. Cấu trúc bảng tra (LUT Structure): OrbitLUT được tổ chức thành mảng phẳng hai chiều OrbitLUT[src_orb, d] → dst_orb (trong mã nguồn là lookup_branch_from_prev). Với mỗi cặp (src_orb, d), bảng trả về trực tiếp ID của quỹ đạo đích — tương ứng với một bước nhảy có hướng giữa các tầng trên Young’s Lattice (xem sơ đồ Lattice và bảng tra tương tác ở FIGURE 8).

3. Khử triệt để chi phí runtime: Thay vì phải sắp xếp lại mảng số mũ hay băm khóa Powers qua HashMap, thuật toán tại mỗi bước SpMV chỉ tốn đúng một phép truy xuất mảng \(O(1)\):

   \[ \mathrm{dst}_{\mathrm{id}} = \operatorname{OrbitLUT}[\mathrm{src}_{\mathrm{id}}][d]. \]

   Bảng OrbitLUT có dung lượng rất nhỏ, nằm gọn trong cache L1/L2 của CPU, biến phép nhân đa thức phức tạp thành thao tác tra mảng và cộng dồn vector với hiệu năng tối đa.

8. Bước 6: Hiện thực hóa Transfer–SpMV trên mảng phẳng

Khi cấu trúc chuyển tiếp của đồ thị đã được nén vào ma trận \(K_\lambda(y)\) ([P1]) và payload đa thức đã được thu gọn thành các khóa quỹ đạo ([P2]), hai mảnh ghép này khớp lại thành một thuật toán đại số tuyến tính hoàn chỉnh: Transfer–SpMV.

Đổi đơn vị lưu trữ: Từ Map rời rạc sang Vector phẳng

Ở mỗi bước duyệt biến \(k\) (\(k = 1, \dots, n\)), toàn bộ trạng thái của hệ thống được lưu trong một mảng số nguyên liên tục Vec<i64>:

\[ \mathbf{V}_k = \mathbf{M}(x_k) \cdot \mathbf{V}_{k-1}. \]

Trong đó, mỗi profile được cấp phát một slice có độ dài bằng số lượng orbit của tầng đó. Ở mỗi vòng lặp hấp thụ một biến, thuật toán thực thi đúng hai thao tác nhịp nhàng để ghép nối hai không gian hình học và đa thức:

• Thao tác 1 (Nhân hệ số từ ma trận $K$): Máy tính đọc ma trận thưa $K$ để biết đi từ hình dáng nguồn (profile $a$) sang hình dáng đích (profile $b$) thì trọng số chuyển tiếp là bao nhiêu. Sau đó, nó lấy trọng số này nhân với hệ số đang có ở trạng thái nguồn (w * src_val).
• Thao tác 2 (Tìm tọa độ từ OrbitLUT và điền vào mảng): Máy tính lấy số gia bậc $d$ của phép chuyển đó ném vào bảng tra tĩnh OrbitLUT. Bảng này nhả ra ngay lập tức một chỉ số mảng nguyên (dst_orb). Đây chính là vị trí “đúng chỗ” (offset) trên mảng phẳng, và hệ thống chỉ việc đem kết quả vừa nhân ở Thao tác 1 cộng dồn thẳng vào tọa độ đó (dst_vec[dst_orb] += w * src_val).

Chính sự nhịp nhàng này (lấy hệ số từ $K$, lấy địa chỉ đích từ $LUT$) đã giúp thuật toán loại bỏ hoàn toàn các cấu trúc từ điển (HashMap) chậm chạp, đưa mọi tính toán phức tạp về thành các phép tra mảng và cộng dồn số nguyên siêu tốc trên RAM.

Ranh giới kiến trúc & Fallback

Điểm tiến hóa ở đây là đổi đơn vị lưu trữ: từ từng monomial sang quỹ đạo, rồi từ các map rời rạc sang vector và ma trận thưa. Miền packed hiện hỗ trợ tối đa 16 cột và chiều cao 15; khi dùng auto, input ngoài miền này được chuyển sang một backend chính xác khác.

Public API hiện giới hạn \(n\le16\). Yêu cầu Transfer–SpMV tường minh ngoài miền shape trả về lỗi, còn auto chọn một backend unpacked exact. CSR cuối vẫn chứa quan hệ comparable-pair \(L(\lambda)\); nén quỹ đạo thay cách lưu payload, không xóa quan hệ chuyển tiếp toàn cục.

Ví dụ thực chiến: Tính toán trọn vẹn $g_{(3,2)}(x_1, x_2, x_3)$ qua Prepare & Transfer–SpMV

Để thấy rõ toàn bộ cỗ máy vận hành trong thực tế, xét bài toán tính đa thức dual Grothendieck cho phân hoạch \(\lambda = (3, 2)\) với \(n = 3\) biến. Bảng Young của \(\lambda = (3, 2)\) gồm 2 hàng và 3 cột:

• Hàng 1 có 3 ô, hàng 2 có 2 ô (tổng cộng 5 ô).
• Chiều cao các cột tương ứng là \(h = (2, 2, 1)\).

Dưới đây là mô phỏng tương tác toàn trình hai giai đoạn: từ khâu chuẩn bị offline (prepare: sinh 9 col-profile, dựng ma trận chuyển tiếp và nén CSR, lập bảng tra tĩnh OrbitLUT) cho đến 3 vòng lặp nhân vector ma trận thưa (Transfer-SpMV) qua 3 biến \(x_1, x_2, x_3\):

Cơ chế chuẩn hóa hệ số: Từ mảng đếm thô (Raw Count) sang hệ số hàm đối xứng $m_\lambda$

Quan sát kết quả tại vector $\mathbf{V}_3$ của profile đích #8 [2,2,1] (shape $(3,2)$) và công thức kết quả đa thức cuối cùng:

\[ g_{(3,2)}(x_1, x_2, x_3) = m_{(1,1,1)} + m_{(2,1)} + 2m_{(2,1,1)} + m_{(2,2)} + 2m_{(2,2,1)} + m_{(3)} + m_{(3,1)} + m_{(3,1,1)} + m_{(3,2)} \]

Ta thấy một chi tiết rất đáng lưu ý: tại sao trên vector $\mathbf{V}3$ hiển thị $m{(3)} \times 3$ và $m_{(2,1,1)} \times 6$, nhưng trong phương trình kết quả lại là $1 \cdot m_{(3)}$ và $2 \cdot m_{(2,1,1)}$?

Sự khác biệt này đến từ việc phân biệt giữa tổng số đường đi đếm được (Raw Count) tích lũy trong mảng SpMV và hệ số thực sự của hàm đối xứng (Symmetric Coefficient) được xuất ra ở kết quả cuối cùng:

1. Mảng $\mathbf{V}_3$ đếm mọi đơn thức rời rạc sinh ra (Raw Count): Trong quá trình chạy vòng lặp Transfer-SpMV, mỗi khi tìm thấy một nhánh tạo ra biến bậc 3 (chẳng hạn $x_1^3$ ở Bước 1, $x_2^3$ ở Bước 2, $x_3^3$ ở Bước 3), thuật toán cứ thế cộng 1 vào cái “rổ” mang khóa quỹ đạo (3). Vì có tổng cộng 3 đơn thức rời rạc mang bậc 3 được tạo ra, cái rổ này tích lũy được giá trị là 3. Đó là lý do xuất hiện $m_{(3)} \times 3$ trong vector $\mathbf{V}_3$ trên bảng SpMV.

2. Ký hiệu $m_{(3)}$ trong kết quả cuối cùng đã “bao thầu” cả 3 biến: Về mặt toán học, bản thân hàm đối xứng $m_{(3)}$ đã được định nghĩa là tổng của toàn bộ các hoán vị hợp lệ thuộc quỹ đạo đó:

   \[ m_{(3)} = x_1^3 + x_2^3 + x_3^3 \]

   Nếu phương trình kết quả ghi là $3 \cdot m_{(3)}$, nó sẽ bung ra thành $3x_1^3 + 3x_2^3 + 3x_3^3$ (sai hoàn toàn về mặt giá trị lượng tử).

3. Bước chia tỷ lệ (Chia cho kích thước quỹ đạo): Để chuyển từ mảng thô sang hệ thức toán học cuối cùng, thuật toán lấy tổng giá trị trong rổ chia cho số lượng hoán vị (size) của quỹ đạo đó:

   • Quỹ đạo (3) trong không gian 3 biến có đúng 3 hoán vị ($x_1^3, x_2^3, x_3^3$).
   • Do đó, hệ số thực của $m_{(3)}$ là: $3 \div 3 = 1$.
   • Thế nên trong phương trình rút gọn, $m_{(3)}$ mang hệ số 1, và khi mở rộng danh sách đơn thức, nó chỉ hiện đúng 3 hạng tử độc lập x₁³ x₂³ x₃³.

Ví dụ kiểm chứng chéo với $m_{(2,1,1)} \times 6$: Tại ô #8 trong $\mathbf{V}3$, ta thấy $m{(2,1,1)} \times 6$:

• Quỹ đạo (2,1,1) với 3 biến có đúng 3 hoán vị khác nhau (là $x_1^2x_2x_3$, $x_1x_2^2x_3$, $x_1x_2x_3^2$).
• Thuật toán sẽ lấy số tổng là 6 chia cho kích thước quỹ đạo là 3: $6 \div 3 = 2$.
• Kết quả khớp hoàn toàn với hạng tử $2m_{(2,1,1)}$ xuất hiện trong công thức đa thức cuối cùng của bài viết!

9. Tiến hóa kiến trúc: Từ prototype, các ranh giới biên đến portfolio

Điểm xuất phát là lattice Baseline: đơn giản, exact, và vẫn là chuẩn đối chiếu cùng fallback cuối. Thử nghiệm đầu tiên đổi mỗi subshape thành một profile cột. Cách viết này làm bao hàm và số cột tăng trở thành so sánh tọa độ:

\[ a=(a_1,\ldots,a_w),\qquad b=(b_1,\ldots,b_w), \qquad \operatorname{inc}(a,b)=\#\{j:b_j>a_j\}. \]

Tuy nhiên, profile-DFS không giảm số trạng thái hay số cặp so sánh vì hai poset đẳng cấu. Trong benchmark lịch sử, thời gian trung vị của nó bằng khoảng \(1.06\) lần Baseline.

Prototype boundary-compressed tiếp theo đã tìm đúng trạng thái cục bộ, nhưng vẫn materialize các suffix map lớn; thời gian trung vị khi ấy bằng khoảng \(7.48\) lần Baseline. Kết quả âm này tách hướng tối ưu thành hai nhánh. LayerPoly xử lý payload: hệ số chuyển trong một lớp chỉ phụ thuộc bậc \(d=\operatorname{inc}(a,b)\), nên có thể gom theo bucket bậc và xử lý các target độc lập. Nhánh schedule bỏ đa thức khỏi boundary recursion: Grouped Kernel biên dịch một operator cho từng source rồi phát lại operator đó qua các lớp biến.

Eager preparation sau đó lộ ra chi phí khởi động. Lazy Transfer trì hoãn biên dịch đến khi một source trở nên active. Với \(n=1\), chỉ kernel của profile rỗng được dựng; nhưng từ \(n\ge2\), toàn bộ \(P(\lambda)\) kernel cuối cùng đều được dựng. Lazy Transfer vì vậy chỉ dời công việc vào execution trong regime này, không phải một warm cache bền qua nhiều lần execute.

Cost model còn chỉ ra hai giới hạn: số kernel eager vẫn là \(P(\lambda)\), còn payload cũ dùng hash map cho từng ordinary monomial. Transfer–SpMV đổi đơn vị lưu trữ sang profile packed, CSR lưu các nhánh chuyển tiếp, orbit payload và flat buffer.

Hai ranh giới sống còn định hình kiến trúc

Dù Transfer–SpMV là bước nhảy vọt về hiệu năng, việc đo đạc trên các miền dữ liệu cực biên cho thấy nó lập tức vấp phải hai giới hạn vật lý không thể vượt qua nếu chỉ dùng đơn độc:

1. Ranh giới phần cứng của miền Packed (Rộng > 16 cột hoặc Cao > 15 tầng):

   • Cơ chế: Để đạt tốc độ truy cập L1/L2 cache tối đa, Transfer–SpMV nén profile cột vào một số nguyên u64: mỗi cột dùng đúng 4 bit (chiều cao tối đa \(2^4 - 1 = 15\)) và hỗ trợ tối đa 16 cột (\(16 \times 4 = 64\) bit).
   • Khi hình dạng vượt biên:
     • Nếu shape rộng 17 cột (ví dụ \(\lambda = 17^4\)), số cột vượt quá 16 \(\implies\) Tràn dung lượng bitfield u64.
     • Nếu shape cao 16 tầng (ví dụ \(\lambda = 2^{16}\), 16 hàng), chiều cao cột \(h = 16 > 15\) \(\implies\) Tràn 4 bit cho phép.
   • Giải pháp kiến trúc: SpMV bắt buộc phải từ chối các shape này (packed = false). Hệ thống phải có các backend unpacked như LayerPoly hoặc Baseline đứng sau làm lưới đỡ an toàn, bảo đảm không bao giờ sập chương trình.

2. Ranh giới nổ bộ nhớ ma trận (\(P(\lambda) > 10^6\)):

   • Cơ chế: Các backend transfer phụ thuộc vào số lượng cặp so sánh trong poset \(P(\lambda)\).
   • Khi dữ liệu vượt biên: Với các shape chữ nhật lớn, số profile \(P(\lambda)\) vượt ngưỡng một triệu (ví dụ \(\lambda = 18^8\) có \(P(\lambda) = 1{,}562{,}275 > 10^6\)), việc dựng toàn bộ ma trận chuyển tiếp sẽ ngốn hàng Gigabyte RAM và gây tràn bộ nhớ (OOM) ngay ở pha prepare.
   • Giải pháp kiến trúc: Cần duy trì Grouped Kernel — backend chuyên biệt tách toán tử theo profile nguồn và phát lại qua từng lớp để ghìm chặt dung lượng RAM dưới ngưỡng an toàn.

Chính vì mỗi backend đều có hạn chế riêng gắn liền với cấu trúc dữ liệu của nó, việc tìm kiếm một thuật toán đơn lẻ vượt trội trong mọi trường hợp là điều bất khả thi. auto portfolio ra đời như một giải pháp thực tế: áp dụng chính sách điều phối có thứ tự trên cặp \((\lambda,n)\) để tự động kích hoạt backend tối ưu cho từng miền dữ liệu.

10. Chiến lược Portfolio thay vì một thuật toán đơn lẻ cho mọi trường hợp

Mỗi biểu diễn đổi một loại chi phí lấy một loại chi phí khác. Vì vậy, chế độ auto không chọn một backend cố định: nó tính \(P(\lambda)\), số profile cột hợp lệ, rồi kiểm tra tuần tự các điều kiện phụ thuộc vào partition và số biến \(n\). Điều kiện đúng đầu tiên kết thúc quá trình điều phối.

Thứ tự kiểm tra trong hàm điều phối choose_dual_grothendieck_backend tuân theo một danh sách gate tuần tự — một gate ở phía dưới chỉ được xét khi mọi gate phía trên đều sai:

1. Gate 1 (Packed, \(P(\lambda)>1\), \(n\ge2\)): Chọn Transfer-SpMV (operator thưa trên profile packed).
2. Gate 2 (\(n\ge7\)): Chọn LayerPoly (ưu tiên đa thức thưa theo từng lớp khi có nhiều biến).
3. Gate 3 (Rộng \(\le24\) và \(P(\lambda)\le10^6\)): Chọn Lazy Transfer (trì hoãn biên dịch kernel đến khi source active).
4. Gate 4 (Rộng \(\le40\) và \(P(\lambda)\le4\cdot10^6\)): Chọn Grouped Kernel (tách operator theo source khỏi payload và phát lại qua các lớp).
5. Gate 5 (Cao \(\le3\)): Chọn LayerPoly (nhánh tối ưu cho shape ít hàng).
6. Fallback cuối cùng: Chọn Baseline (chuẩn đối chiếu exact khi cả năm gate đều không thỏa mãn).

Nhờ thứ tự 5 gate này, các ranh giới biên phân tích ở Mục 9 được phân luồng hoàn toàn tự động:

• Shape rộng hơn 16 cột hoặc cao hơn 15 tầng: Trượt ngay ở Gate 1 (packed = false) để chuyển sang LayerPoly hoặc Lazy Transfer mà không gây tràn bit u64.
• Shape có số profile \(P(\lambda) > 10^6\): Trượt ở Gate 3 (vượt trần 1 triệu profile của Lazy) để chuyển sang Grouped Kernel ở Gate 4, ngăn chặn nổ RAM.
• Ca ít biến (\(n \le 1\)): Bị loại khỏi Gate 1 để tránh lãng phí chi phí dựng ma trận CSR.

11. Kết quả: lợi ích phụ thuộc hình dạng

Benchmark gồm 21 shape thuộc sáu họ và \(n=0,\ldots,8\), tổng cộng 189 ca. Mọi output signature của Transfer-SpMV đều khớp lattice baseline (100% exact match). Trung bình hình học là \(1.99\times\) khi tái sử dụng operator (warm) và \(1.77\times\) khi tính cả chuẩn bị (cold).

Cách đọc bộ điều phối: Đây là heuristic có thứ tự được chốt từ benchmark và giới hạn representation, không phải bộ phân lớp đã học hay bảo đảm chọn backend nhanh nhất cho mọi input.

Ở mức trung bình, toàn bộ 6 họ shape đều nhanh hơn baseline rõ rệt: staircase (\(3.35\times\) warm, \(2.67\times\) cold), thick hook (\(2.50\times\) warm), generic (\(2.28\times\) warm) hưởng lợi lớn nhất từ việc tối ưu cấu trúc chuyển tiếp; hook (\(1.52\times\)) và rectangle (\(1.46\times\)) cũng đạt mức tăng tốc ổn định.

Kết quả nên được đọc như một bản đồ regime, không phải lời hứa rằng một backend sẽ nhanh hơn cho mọi input.

12. Ba trục thay đổi biểu diễn

Toàn bộ hành trình tối ưu hóa thuật toán được định hình bởi ba trục chuyển dịch biểu diễn cốt lõi:

1. Đổi trạng thái: Từ bảng 2D sang Profile cột (Mục 3)

   • Trước tối ưu: Lưu giữ toàn bộ bảng số Young 2D và kiểm tra bao hàm trên đồ thị poset dày đặc.
   • Sau tối ưu: Nén trạng thái thành chiều cao từng cột (Column-Profile) — chỉ cần theo dõi đường biên 1D ngoài cùng.

2. Đổi đường duyệt: Từ duyệt cây động sang SpMV ma trận cố định (Mục 4, 5, 7)

   • Trước tối ưu: Mỗi bước duyệt biến \(x_k\) phải chạy đệ quy tìm nhánh chuyển tiếp và kiểm tra luật điền số RPP lúc runtime.
   • Sau tối ưu: Dùng Transducer quét cột tiền tính toán một lần, đóng băng toàn bộ đồ thị chuyển tiếp vào ma trận thưa \(K_\lambda(y)\) và bảng tra tĩnh OrbitLUT \(O(1)\) — biến phép duyệt cây phức tạp thành vòng lặp nhân ma trận thưa thẳng tắp (Transfer–SpMV, Mục 8).

3. Đổi payload: Từ bảng băm đơn thức sang Vector phẳng (Mục 6, 8)

   • Trước tối ưu: Quản lý hàng triệu đơn thức rời rạc qua HashMap<Powers, i64> gây phân mảnh bộ nhớ và nghẽn CPU.
   • Sau tối ưu: Gom các đơn thức hoán vị thành một khóa quỹ đạo đối xứng (Orbit Key) và lưu hệ số trên mảng phẳng liên tục Vec<i64>.

Không bước nào trong số này thay đổi định nghĩa toán học của đa thức dual Grothendieck \(g_\lambda(x_1, \dots, x_n)\). Thuật toán chỉ từng bước bóc tách để giữ lại đúng cấu trúc đại số tối thiểu, biến bài toán tổ hợp phân mảnh thành đại số tuyến tính hiệu năng cao.