Luận án Tiến sĩ: Đặc trưng không gian trạng thái và tính ổn định của hệ Sandpile Model mở rộng

Mô hình đống cát Bak-Tang-Wiesenfeld (BTW Model) ra đời năm 1987. Mô hình giải thích hiện tượng nhiễu 1/f và các hệ phức hợp tự nhiên. Không gian mô hình là lưới ô vuông hoặc đồ thị hữu hạn. Mỗi đỉnh chứa một số lượng hạt cát nguyên không âm. Nguồn ngoài liên tục bổ sung từng hạt cát vào các vị trí ngẫu nhiên. Khi số hạt tại một đỉnh đạt ngưỡng tới hạn, đỉnh đó mất ổn định. Đỉnh mất ổn định sẽ thực hiện bước đổ cát sang các đỉnh lân cận. Chuỗi sụt lở lan truyền nhanh chóng trên toàn bộ mạng lưới. Đỉnh tiêu tán (sink) hấp thụ hạt cát ở biên để giải tỏa năng lượng dư thừa. Hiện tượng này minh chứng rõ nét cho tính tới hạn tự tổ chức (Self-Organized Criticality - SOC).

Động lực học của mô hình đống cát được mô tả hình thức qua đại số ma trận. Ma trận toppling (toppling matrix) chi phối trực tiếp quy tắc chuyển dịch hạt cát tại mỗi bước sụt lở. Trên đồ thị liên thông tổng quát, ma trận toppling tương đương với ma trận Laplacian trên đồ thị sau khi loại bỏ hàng và cột của đỉnh tiêu tán. Ma trận Laplacian là ma trận đối xứng, xác định dương. Các phần tử trên đường chéo chính phản ánh bậc của đỉnh. Các phần tử ngoài đường chéo biểu diễn mối liên kết cạnh giữa các đỉnh kề nhau. Khi một đỉnh sụt lở, vectơ trạng thái biến đổi bằng cách trừ đi cột tương ứng của ma trận toppling. Phép toán này bảo toàn số hạt cát tổng thể trừ các hạt rơi vào đỉnh tiêu tán. Đại số ma trận giúp giải quyết trọn vẹn bài toán cân bằng và bảo toàn.

Không gian cấu hình của hệ đống cát phân rã thành các lớp trạng thái rõ rệt. Cấu hình ổn định (stable configurations) xuất hiện khi mọi đỉnh trong mạng lưới đều có số hạt cát nhỏ hơn ngưỡng tới hạn. Ngược lại, cấu hình không ổn định sẽ kích hoạt chuỗi sụt lở tất định để quay về trạng thái ổn định. Trong tập hợp cấu hình ổn định, các trạng thái tiếp tục phân nhánh thành hai lớp: trạng thái chuyển tiếp (transient configurations) và trạng thái hồi quy (recurrent configurations). Trạng thái chuyển tiếp chỉ xuất hiện trong giai đoạn đầu của hệ động lực. Sau một số bước thêm hạt và sụt lở, hệ thống không bao giờ lặp lại trạng thái chuyển tiếp. Hệ sẽ tiến vào tập hút bền vững gồm toàn bộ trạng thái hồi quy.

Phân hoạch trơn đóng vai trò hạt nhân trong không gian trạng thái hệ E-SPM. Phân hoạch trơn là dãy số nguyên giảm nghiêm ngặt với độ dốc giữa hai cột liền kề không vượt quá 1. Biểu đồ Ferrer minh họa trực quan hình dạng của phân hoạch trơn. Trong hệ E-SPM, hạt cát chỉ trượt từ cột cao xuống cột thấp khi chênh lệch chiều cao vượt ngưỡng cho phép. Mối quan hệ thứ tự giữa các phân hoạch thiết lập một cấu trúc dàn phân phối. Mỗi nút trong dàn đại diện cho một trạng thái hợp lệ. Các cạnh có hướng tương ứng với phép dịch chuyển hạt cát cơ bản. Cấu trúc này bảo đảm tính hội tụ toàn cục từ bất kỳ trạng thái ban đầu nào về trạng thái cân bằng duy nhất.

Độ dài đường đi giữa hai trạng thái đo lường số bước sụt lở cần thiết để hệ thống đạt cân bằng. Trong hệ E-SPM, khoảng cách giữa hai phân hoạch trơn được tính toán thông qua biểu đồ năng lượng. Biểu đồ năng lượng theo dõi sự thay đổi vị trí của từng hạt cát riêng lẻ. Đường đi dài nhất tương ứng với chuỗi sụt lở cực đại từ cấu hình ban đầu đến điểm dừng. Công thức giải tích xác định chính xác cận trên và cận dưới của độ dài đường đi. Thời gian tiếp cận trạng thái ổn định phụ thuộc đa thức vào tổng số hạt cát. Kết quả này khẳng định tính hiệu quả thuật toán trong mô phỏng hệ động lực rời rạc.

Việc nhận diện trạng thái hồi quy (recurrent configurations) là bài toán cốt lõi trong lý thuyết hệ đống cát. Trạng thái hồi quy hình thành nên tập hút tuần hoàn của hệ thống dưới tác động thêm hạt liên tục. Thuật toán Burning Algorithm của Dhar cung cấp tiêu chuẩn kiểm tra trạng thái hồi quy hiệu quả. Thuật toán đốt cháy lan truyền từ đỉnh biên vào sâu trong mạng lưới. Nếu đám cháy thiêu rụi toàn bộ các đỉnh, cấu hình đó là trạng thái hồi quy. Ngược lại, sự tồn tại của rào cản hạt cát ngăn chặn đám cháy minh chứng cấu hình thuộc lớp trạng thái chuyển tiếp (transient configurations). Phân tích cấu trúc chu trình giúp dự đoán chính xác chu kỳ hoạt động của hệ động lực.

Động học song song thay đổi căn bản cách thức lan truyền sụt lở so với động học tuần tự. Trong một bước thời gian, toàn bộ các cột cát vượt ngưỡng đều đổ hạt sang hai bên. Động lực học đối xứng áp đặt điều kiện bảo toàn hình dạng đối xứng qua mỗi bước biến đổi. Khi kết hợp thành hệ PS-SPM, quỹ đạo trạng thái trở nên ngắn hơn và tốc độ hội tụ tăng nhanh. Không gian cấu hình phân chia thành các thành phần liên thông độc lập. Mỗi thành phần liên thông dẫn tới một điểm cân bằng hoặc một chu trình giới hạn có độ dài nhỏ. Nghiên cứu chứng minh rằng hệ luôn duy trì tính đóng đối với tập phân hoạch đối xứng.

Thủ tục Atom và thủ tục đan xen là hai công cụ kỹ thuật then chốt để giải mã hệ PS-SPM. Thủ tục Atom thực hiện phép phân rã một phân hoạch lớn thành các khối đơn vị tối tiểu không thể chia cắt. Mỗi khối nguyên tử tuân theo quy tắc biến đổi độc lập dưới tác động sụt lở song song. Thủ tục đan xen kết hợp các khối nguyên tử theo trật tự xen kẽ để tái tạo cấu hình đối xứng toàn vẹn. Kỹ thuật giả đan xen mở rộng phạm vi áp dụng cho các phân hoạch có số lượng hạt cát bất kỳ. Hai thủ tục này cho phép tính toán tường minh quỹ đạo chuyển trạng thái mà không cần mô phỏng từng bước đơn lẻ.

Điểm cố định của hệ PS-SPM là những cấu hình không còn đỉnh nào đủ điều kiện sụt lở. Các cấu hình ổn định này phản ánh trạng thái năng lượng cực tiểu của hệ thống. Tập hợp các điểm cố định tổ chức thành một cấu trúc dàn thứ tự hoàn chỉnh. Phép toán hợp và giao trên dàn bảo toàn tính ổn định và tính đối xứng. Mọi đường đi trong không gian trạng thái đều hội tụ đơn điệu về đáy dàn. Tính chất này đảm bảo tính dự đoán tuyệt đối của hệ động lực đối xứng song song. Kết quả mở ra khả năng ứng dụng hệ trong các bài toán cân bằng tải trên kiến trúc mạng đối xứng.

Hệ Chip Firing Game có dấu (S-CFG) trên đường thẳng gán nhãn trạng thái bằng cả số nguyên dương và số nguyên âm. Hạt mang dấu dương đại diện cho tích lũy năng lượng, hạt mang dấu âm biểu thị sự thiếu hụt năng lượng. Quy tắc bắn chip mở rộng cho phép chuyển dịch chip có dấu nhằm triệt tiêu chênh lệch thế năng. Hệ thống duy trì tính giao hoán Abelian trong chuỗi bắn chip. Thứ tự thực hiện các bước bắn không làm thay đổi cấu hình ổn định cuối cùng. Không gian trạng thái của hệ S-CFG trên đường thẳng ánh xạ trực tiếp sang mô hình phân hoạch đối xứng. Cấu trúc đại số này cung cấp mô hình toán học chuẩn xác cho các bài toán phân phối tài nguyên hai chiều.

Mối quan hệ giữa hệ SPM đối xứng (S-SPM) và hệ CFG có dấu (S-CFG) được thiết lập qua ánh xạ bảo toàn thứ tự. Công trình nghiên cứu chứng minh hai hệ thống này hoàn toàn đẳng cấu với nhau trên đồ thị đường thẳng. Mỗi bước sụt lở trong hệ S-SPM tương ứng 1-1 với một bước bắn chip hợp lệ trong hệ S-CFG. Tính đẳng cấu giúp chuyển giao toàn bộ kết quả về không gian trạng thái từ lý thuyết phân hoạch sang lý thuyết đồ thị. Nhờ đó, tính ổn định và phân loại trạng thái hồi quy được giải quyết đồng thời trên cả hai mô hình. Sự tương đương này khẳng định tính phổ quát của nguyên lý chuyển pha rời rạc.

Trên đồ thị vòng tròn C_n, không gian trạng thái của hệ SPM(C_n) và S-CFG(C_n) mang đặc tính tuần hoàn rõ rệt. Không có đỉnh tiêu tán cố định, số lượng hạt cát hoặc chip trong hệ được bảo toàn tuyệt đối. Cấu hình ổn định phụ thuộc chặt chẽ vào tổng số hạt cát ban đầu so với số đỉnh của chu trình. Khi mật độ hạt vượt qua giá trị tới hạn, hệ thống rơi vào chu trình sụt lở vĩnh cửu không bao giờ dừng. Dàn con SPM(C_n, k) nhúng tự nhiên vào dàn phân hoạch tự do. Phân tích đại số ma trận toppling trên C_n cho phép xác định chính xác số lượng và cấu trúc của các chu trình trạng thái giới hạn.

Động lực học sụt lở (avalanche dynamics) phản ánh quá trình giải phóng năng lượng tích tụ trong hệ thống. Khi thêm một hạt cát vào cấu hình ổn định, hệ có thể kích hoạt một vụ sụt lở nhỏ hoặc một chuỗi sụt lở khổng lồ bao trùm toàn mạng. Xác suất xuất hiện một vụ sụt lở kích thước s tỷ lệ nghịch với lũy thừa của s. Phân bố này tuân thủ nghiêm ngặt quy luật lũy thừa (power-law distribution) dạng phân phối không tỷ lệ. Hệ thống tự duy trì ở trạng thái tới hạn mà không cần điều khiển tham số. Quy luật lũy thừa là dấu hiệu kinh điển của tính tới hạn tự tổ chức. Cơ chế này giải thích nguồn gốc của các hiện tượng tự nhiên như động đất, cháy rừng và biến động thị trường tài chính.

Nhóm Abelian Sandpile (Sandpile group / Picard group) đại diện cho cấu trúc đại số trừu tượng của các trạng thái hồi quy (recurrent configurations). Phép toán nhóm được định nghĩa bằng phép cộng vectơ thành phần kèm theo bước ổn định hóa sụt lở. Phần tử trung hòa của nhóm là một trạng thái hồi quy đặc biệt, đóng vai trò như toán tử đơn vị. Nhóm Sandpile là nhóm Abel hữu hạn và đẳng cấu với nhóm Picard của đồ thị trong hình học đại số. Cấp của nhóm bằng định thức của ma trận toppling (toppling matrix). Định thức này trùng khớp với số lượng cây khung của đồ thị theo Định lý Cây Ma trận Kirchhoff. Nhóm Sandpile mang đến cái nhìn sâu sắc về tính đối xứng tiềm ẩn của hệ động lực rời rạc.

Mô hình Sandpile mở rộng mở ra nhiều ứng dụng thực tiễn trong khoa học máy tính và tính toán rời rạc. Bản chất tính toán song song tự nhiên của quy tắc toppling giúp thiết kế các thuật toán phân tán hiệu năng cao. Mô hình được ứng dụng thành công trong cân bằng tải mạng máy tính, xử lý ảnh số và mã hóa dữ liệu. Các thuật toán định tuyến phân tán khai thác cơ chế sụt lở để điều tiết lưu lượng giao thông tự động, tránh tắc nghẽn cục bộ. Ngoài ra, cấu trúc nhóm Abelian Sandpile hỗ trợ xây dựng các giao thức mật mã học dựa trên độ khó của bài toán logarit rời rạc trên nhóm hữu hạn. Mô hình đống cát tiếp tục là cầu nối liên ngành vững chắc giữa toán học thuần túy và công nghệ thông tin.