Ma trận thưa

Trong giải tích số và khoa học tính toán, một ma trận thưa (hay mảng thưa, tiếng Anh: sparse matrix hay sparse array) là một ma trận toán học mà trong đó đa số phần tử có giá trị là 0. Không có định nghĩa chặt chẽ bao nhiêu phần tử cần bằng 0 để ma trận được coi là thưa nhưng với một tiêu chí chung là số phần tử khác 0 phải xấp xỉ bằng số hàng hoặc các cột. Ngược lại, nếu ma trận không có nhiều các phần tử khác 0, thì ma trận đó được coi là đặc ("dày", "dầy"). Số phần tử có giá trị bằng 0 chia cho tổng số phần tử (ví dụ, M x N với một ma trận có kích thước M x N) đôi khi gọi là tính thưa (sparsity) của ma trận.
Về mặt khái niệm, sự thưa thớt tương ứng với các hệ thống có ít sự tương tác theo từng cặp. Ví dụ, một hàng người xếp hàng chờ mua đồ trước một cửa hàng ăn nhanh, mỗi người cách nhau 5 mét và không có tiếp xúc cơ thể với nhau thì đây được coi là một hệ thống thưa thớt. Ngược lại, nếu một hàng người này nắm tay nhau (hay đứng cách nhau cự ly gần hơn, khoảng 30 cm) thì được xem là một hệ thống dày đặc. Khái niệm thưa thớt rất hữu ích trong toán học tổ hợp và các lĩnh vực ứng dụng như lý thuyết mạng và giải tích số, thường có mật độ dữ liệu hoặc kết nối quan trọng thấp. Các ma trận thưa quy mô lớn thường xuất hiện trong các ứng dụng khoa học hay kỹ thuật khi giải quyết các vấn đề về phương trình vi phân riêng phần.
Khi lưu trữ và thao tác với ma trận thưa trên máy tính, việc sử dụng các thuật toán và cấu trúc dữ liệu chuyên dụng là điều hữu ích và thường cần thiết để tận dụng cấu trúc thưa thớt của ma trận.
Trong lĩnh vực học máy, các máy tính chuyên dụng được tạo ra dành cho các ma trận thưa rất phổ biến. Các thuật toán và cấu trúc dữ liệu tiêu chuẩn dùng để thực hiện các phép tính với ma trận dày thường chậm và không hiệu quả khi áp dụng cho các ma trận thưa có kích thước lớn. Lý do là vì bộ nhớ máy tính buộc phải lãng phí tài nguyên khi lưu trữ các giá trị 0 xuất hiện tần suất cao trong ma trận thưa. Về bản chất, dữ liệu thưa sẽ được nén lại dễ dàng hơn và do đó giảm thiểu yêu cầu lưu trữ trên máy tính. Một số ma trận thưa có kích thước lớn không thể thực thi bằng các thuật toán tiêu chuẩn như đã làm với các ma trận dày.
Lưu trữ ma trận thưa.
Một ma trận thường được lưu lại bằng một mảng hai chiều. Mỗi phần tử trong mảng thể hiện một phần tử của ma trận và được truy cập bằng hai mảng và . Thông thường, là chỉ số hàng, đánh số thứ tự từ trên xuống dưới, và là chỉ số cột, đánh số thứ tự từ trái sang phải. Với một ma trận , dung lượng bộ nhớ cần thiết để lưu trữ ma trận ở định dạng này tương ứng với (bỏ qua thực tế là các kích thước của ma trận cũng cần được lưu trữ).
Với trường hợp ma trận thưa, yêu cầu giảm bộ nhớ lưu trữ một cách đáng kể có thể được thực hiện bằng cách chỉ lưu các phần tử khác 0. Tùy thuộc vào số lượng và sự phân bố của các phần tử khác 0, các cấu trúc dữ liệu khác nhau có thể được sử dụng và tiết kiệm rất nhiều bộ nhớ khi so sánh với cách lưu trữ cơ bản (như mảng 2 chiều). Tuy nhiên, khi làm điều này thì phải đánh đổi lại việc truy cập các phần tử đơn lẻ trở nên phức tạp hơn và cần có các cấu trúc bổ sung để có thể khôi phục ma trận ban đầu một cách rõ ràng.
Các định dạng có thể được chia thành hai nhóm:
Phần mềm.
Nhiều thư viện phần mềm hỗ trợ việc xử lý ma trận thưa và cung cấp bộ giải cho các phương trình ma trận thưa. Sau đây là các thư viện mã nguồn mở:
Lịch sử.
Thuật ngữ "ma trận thưa" có thể được đặt ra bởi Harry Markowitz người khởi xướng một số công việc tiên phong nhưng sau đó rời bỏ lĩnh vực này.