Cây loại bỏ trong thuật toán Cholesky thưa: Hiểu về Fill-in và Đồ thị tác vụ

Trong lĩnh vực tính toán khoa học và đại số tuyến tính số, việc xử lý các ma trận thưa (sparse matrices) là một thách thức lớn nhưng cũng đầy tiềm năng. Bài viết này sẽ phân tích cấu trúc cây loại bỏ (elimination tree) cho thuật toán Cholesky thưa kiểu "right-looking" dùng để tính toán phân rã $A = LL^T$, trong đó $L$ là ma trận tam giác dưới.

Cây loại bỏ này đóng vai trò là nền tảng cho hầu hết các phần mềm phân rã ma trận thưa hiện nay. Nó cung cấp hai thông tin quan trọng: vị trí xuất hiện của các phần tử khác không trong ma trận $L$ (kể cả khi chúng không có trong ma trận gốc $A$, một hiện tượng gọi là "fill-in") và đồ thị phụ thuộc của các tác vụ trong quá trình phân rã.

Từ thuật toán đặc đến đồ thị tác vụ

Hãy bắt đầu với thuật toán Cholesky đặc (dense) cơ bản. Cấu trúc vòng lặp của thuật toán này ngầm định tạo ra một đồ thị tác vụ có hướng không chu trình (DAG - Directed Acyclic Graph). Tuy nhiên, khi ma trận $A$ là ma trận thưa, chúng ta có thể loại bỏ nhiều phép tính không cần thiết.

Sơ đồ minh họa fill-in trong ma trận

Bằng cách cắt tỉa (prune) các phép tính thừa từ đồ thị đặc, chúng ta thu được một đồ thị nhỏ hơn nhiều. Một nhóm cột có thể được hiểu là "khi đã hoàn thành tất cả các thao tác trong nhóm cột $i$, không có thao tác nào trong tương lai tham chiếu đến cột $i$ nữa". Đồ thị đã cắt tỉa này cho biết chính xác mọi thao tác cần thiết để phân rã hoàn toàn ma trận thưa đó.

Vấn đề của việc cắt tỉa trực tiếp

Mặc dù đồ thị cắt tỉa rất hữu ích, nhưng để xác định nó, chúng ta thường phải thực hiện quá trình phân rã đặc rồi mới loại bỏ các phép tính thừa. Điều này không hiệu quả. Thay vào đó, có một cấu trúc dữ liệu đơn giản với độ phức tạp $O(n)$ kết hợp với mô hình khác không ban đầu của $A$ có thể cho chúng ta biết ngay mẫu lấp đầy (fill pattern) cuối cùng cũng như đồ thị tác vụ đã cắt tỉa. Đó chính là cây loại bỏ cột (column elimination tree).

Quy tắc cấu trúc và sự dư thừa

Một thực tế cấu trúc quan trọng từ bước cập nhật của thuật toán Cholesky là: Nếu $k < j < i$, $L_{ik} \neq 0$ và $L_{jk} \neq 0$, thì $L_{ij} \neq 0$.

Quy tắc này tạo ra các cạnh phụ thuộc. Ví dụ, nếu cột 0 phụ thuộc vào cột 1 và cột 2 (0->1 và 0->2), thì cột 0 có hai "cha". Đây là một mẫu DAG. Tuy nhiên, quy tắc cấu trúc trên cho thấy cạnh 0->2 là thừa. Vì $L_{1,0} \neq 0$ và $L_{2,0} \neq 0$, ta bắt buộc phải có $L_{2,1} \neq 0$, do đó tồn tại cạnh ngầm định 1->2. Chúng ta phải đi từ 0->1 trước anyway, nên thông tin 0->2 là thừa.

So sánh giữa DAG cột và Cây loại bỏ

Nếu chúng ta loại bỏ tất cả các cạnh thừa khỏi DAG cột, kết quả thu được sẽ là một cây.

Xây dựng cây loại bỏ

Cây loại bỏ cho biết cách tạo ra mẫu lấp đầy của $L$ từ mô hình khác không ban đầu của $A$ dựa trên quy tắc cấu trúc đã nêu. Để xây dựng cây này, chúng ta có thể sử dụng một thuật toán đơn giản: duyệt qua các hàng, tìm chỉ số cột đầu tiên $k$ sao cho $L_{ik} \neq 0$ và $k < i$. Sau đó, lưu $c \to r$ vào ancestors[c] và lặp ngược lên các tổ tiên cho đến khi tìm thấy cột chưa được khớp; cột đó sẽ trở thành cha của $r$.

Kết luận

Việc trình bày các cây loại bỏ thường đi kèm với lý thuyết đồ thị khá trừu tượng. Tuy nhiên, khi tiếp cận trực tiếp từ thuật toán phân rã Cholesky sang DAG tác vụ, sau đó cắt tỉa DAG đó và chỉ ra rằng quy tắc cấu trúc dẫn đến một biểu diễn nén của DAG — biểu diễn đó tình cờ lại là một cây — chúng ta có cái nhìn trực quan và sâu sắc hơn về cơ chế hoạt động của các thư viện đại số tuyến tính hiện đại.