Ma trận thưa

Ví dụ của ma trận thưa ${\displaystyle \left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)}$

Trong hình trên chỉ chứa 9 giá trị khác 0, và với 26 giá trị bằng 0. Mật độ thưa là 74%, và mật độ đặc là 26%.

Một ma trận thưa thớt thu được khi giải một phương pháp phần tử hữu hạn trong 2 chiều. Các phần tử không có giá trị bằng 0 được hiển thị bằng màu đen.

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 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^[1] rất phổ biến.^[2] 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ử a_i,j của ma trận và được truy cập bằng hai mảng i và j. Thông thường, i là chỉ số hàng, đánh số thứ tự từ trên xuống dưới, và j là chỉ số cột, đánh số thứ tự từ trái sang phải. Với một ma trận m × 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 m × n (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:

• Những định dạng hỗ trợ sửa đổi hiệu quả, chẳng hạn như DOK (từ điển khóa), LIL (danh sách các danh sách) hoặc COO (danh sách tọa độ). Các định dạng này thường được sử dụng để xây dựng các ma trận.
• Những định dạng hỗ trợ truy cập hiệu quả và hoạt động ma trận, chẳng hạn như CSR (hàng thưa thớt được nén) hoặc CSC (cột thưa thớt được nén).

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ở:

• SuiteSparse, một bộ các thuật toán ma trận thưa, hướng tới giải pháp trực tiếp của các hệ thống tuyến tính thưa.
• Portable, Extensible Toolkit for Scientific Computation, một thư viện C lớn, chứa nhiều bộ giải ma trận khác nhau cho nhiều định dạng lưu trữ ma trận.
• Trilinos, một thư viện C ++ lớn, với các thư viện con dành riêng cho việc lưu trữ các ma trận dày/thưa và giải pháp của các hệ thống tuyến tính tương ứng.
• Eigen (thư viện C++) là một thư viện C ++ chứa một số trình giải ma trận thưa. Tuy nhiên, không có trình giải nào chứa tính toán song song.
• MUMPS (phần mềm) (MUltifrontal Massively Parallel sparse direct Solver), viết bằng Fortran90, là một trình giải trước (frontal solver).
• Dune (phần mềm), một thư viện phần tử hữu hạn mà cũng có một thư viện con cho các hệ thống tuyến tính thưa và các giải pháp kèm theo.
• PaStix.
• SuperLU.
• Armadillo (thư viện C++) cung cấp một trình bao bọc (wrapper) C ++ thân thiện với người dùng dành cho BLAS và LAPACK.
• SciPy cung cấp hỗ trợ cho một số định dạng ma trận thưa, đại số tuyến tính và bộ giải.
• SPArse Matrix (spam) gói R cho các ma trận thưa.
• Wolfram Language xử lý các mảng thưa với số phần tử theo nghĩa đen.
• ALGLIB là một thư viện C++ và C# với hỗ trợ đại số tuyến tính thưa.
• ARPACK thư viện Fortran 77 dành cho thao tác và chéo hóa ma trận thưa, sử dụng thuật toán Arnoldi.
• SPARSE, gói tham khảo (đã cũ) của Viện Tiêu chuẩn và Kỹ thuật quốc gia (Hoa Kỳ) dành cho (số thực hoặc số phức) đường chéo ma trận thưa.
• SLEPc, thư viện dành cho giải pháp hệ thống tuyến tính quy mô lớn và các ma trận thưa.
• Sympiler, một trình tạo mã theo lĩnh vực cụ thể và thư viện để giải các hệ thống tuyến tính và các bài toán lập trình bậc hai.

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.^[3]

Xem thêm

• Biểu diễn ma trận (matrix representation)
• Nguyên lý Pareto
• Ma trận bất thường (ma trận bất quy tắc, irregular matrix)
• Ma trận một phần tử (single-entry matrix)
• Ma trận đường chân trời (skyline matrix)
• Mã đồ thị thưa (sparse graph code)
• Tập tin thưa (Sparse file)
• Định dạng tập tin Harwell-Boeing
• Các định dạng trao đổi Thị trường Ma trận (matrix Market exchange formats)

Ghi chú

1. “Cerebras Systems Unveils the Industry's First Trillion Transistor Chip”. www.businesswire.com (bằng tiếng Anh). ngày 19 tháng 8 năm 2019. Truy cập ngày 2 tháng 12 năm 2019. The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation
2. “Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory”. www.anl.gov (Thông cáo báo chí) (bằng tiếng Anh). Truy cập ngày 2 tháng 12 năm 2019. The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.
3. Oral history interview with Harry M. Markowitz, pp. 9, 10.

Tham khảo

• Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (ấn bản thứ 3). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Stoer, Josef; Bulirsch, Roland (2002). Introduction to Numerical Analysis (ấn bản thứ 3). Berlin, New York: Springer-Verlag. ISBN 978-0-387-95452-3.
• Tewarson, Reginald P. (tháng 5 năm 1973). Sparse Matrices (Part of the Mathematics in Science & Engineering series). Academic Press Inc. (This book, by a professor at the State University of New York at Stony Book, was the first book exclusively dedicated to Sparse Matrices. Graduate courses using this as a textbook were offered at that University in the early 1980s).
• Bank, Randolph E.; Douglas, Craig C. “Sparse Matrix Multiplication Package” (PDF). Bản gốc (PDF) lưu trữ ngày 21 tháng 12 năm 2014. Truy cập ngày 20 tháng 11 năm 2020.
• Pissanetzky, Sergio (1984). Sparse Matrix Technology. Academic Press.

Đọc thêm

• Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. (1976). “A comparison of several bandwidth and profile reduction algorithms”. ACM Transactions on Mathematical Software. 2 (4): 322–330. doi:10.1145/355705.355707.
• Gilbert, John R.; Moler, Cleve; Schreiber, Robert (1992). “Sparse matrices in MATLAB: Design and Implementation”. SIAM Journal on Matrix Analysis and Applications. 13 (1): 333–356. CiteSeerX 10.1.1.470.1054. doi:10.1137/0613024.
• Sparse Matrix Algorithms Research at the Texas A&M University.
• SuiteSparse Matrix Collection
• SMALL project A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.