Xem mã nguồn của Ma trận thưa

{| class=wikitable align=right width=240px style="margin: 3px 0 5px 14px;"
| <center>''Ví dụ của ma trận thưa''</center>
<center><math>\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)</math></center>
|-
| <center>{{midsize|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%.}}</center>
|}
[[Hình:Finite element sparse matrix.png|right|thumb|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)|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&nbsp;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<ref>{{chú thích web|url=https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-Industry%E2%80%99s-Trillion-Transistor-Chip|title=Cerebras Systems Unveils the Industry’s First Trillion Transistor Chip|quote=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|date = ngày 19 tháng 8 năm 2019 |website=www.businesswire.com|language=en|access-date = ngày 2 tháng 12 năm 2019}}</ref> rất phổ biến.<ref>{{Cite press|url=https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer|title=Argonne National Laboratory Deploys Cerebras CS-1, the World’s Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory|quote=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.|website=www.anl.gov|language=en|access-date = ngày 2 tháng 12 năm 2019}}</ref> 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 dữ liệu|nén]] lại dễ dàng hơn và do đó giảm thiểu yêu cầu [[Lưu trữ dữ liệu máy tính|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ử {{math|''a''<sub>''i'',''j''</sub>}} của ma trận và được truy cập bằng hai [[Mảng (cấu trúc dữ liệu)|mảng]] {{math|''i''}} và {{math|''j''}}. Thông thường, {{math|''i''}} là chỉ số hàng, đánh số thứ tự từ trên xuống dưới, và {{math|''j''}} là chỉ số cột, đánh số thứ tự từ trái sang phải. Với một ma trận {{math|''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 {{math|''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ở:
* [http://faculty.cse.tamu.edu/davis/suitesparse.html 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)]] ('''MU'''ltifrontal '''M'''assively '''P'''arallel sparse direct '''S'''olver), 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.
* [http://pastix.gforge.inria.fr/ PaStix].
* [http://crd-legacy.lbl.gov/~xiaoye/SuperLU/ 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.
* [https://cran.r-project.org/web/packages/spam/index.html SPArse Matrix (spam)] gói R cho các ma trận thưa.
* [https://reference.wolfram.com/language/guide/SparseArrays.html 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.
* [https://www.netlib.org/sparse/ 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.
* [https://www.sympiler.com/ 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.<ref>[http://purl.umn.edu/107467 Oral history interview with Harry M. Markowitz], pp. 9, 10.</ref>

== Xem thêm ==
{{columns-list|colwidth=22em|
* [[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ú ==
{{tham khảo}}

== Tham khảo ==
* {{chú thích sách | first1=Gene H. | last1=Golub | author1-link=Gene H. Golub | first2=Charles F. | last2=Van Loan | author2-link=Charles F. Van Loan | year=1996 | title=Matrix Computations |edition=3 | publisher=Johns Hopkins | place=Baltimore | isbn=978-0-8018-5414-9 }}
* {{chú thích sách | last1=Stoer | first1=Josef | last2=Bulirsch | first2=Roland | title=Introduction to Numerical Analysis | url=https://archive.org/details/introductiontonu0000stoe_t7w1 | publisher=[[Springer-Verlag]] | location=Berlin, New York |edition=3 | isbn=978-0-387-95452-3 | year=2002}}
* {{chú thích sách | last=Tewarson| first=Reginald P.|title=Sparse Matrices (Part of the Mathematics in Science & Engineering series)|publisher= Academic Press Inc.|date=May 1973}} (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).
* {{chú thích web|title= Sparse Matrix Multiplication Package|first1= Randolph E.|last1= Bank|first2= Craig C.|last2= Douglas|url= http://www.mgnet.org/~douglas/Preprints/pub0034.pdf|ngày truy cập= 2020-11-20|archive-date= 2014-12-21|archive-url= https://web.archive.org/web/20141221225953/http://www.mgnet.org/~douglas/Preprints/pub0034.pdf|url-status= dead}}
* {{chú thích sách |last=Pissanetzky|first= Sergio|year= 1984|title=Sparse Matrix Technology|url=https://archive.org/details/sparsematrixtech0000piss|url-access=registration|publisher= Academic Press}}

== Đọc thêm ==
* {{chú thích tạp chí | title = A comparison of several bandwidth and profile reduction algorithms | journal = ACM Transactions on Mathematical Software | year = 1976 | volume = 2 | issue = 4 | pages = 322–330 | url = http://portal.acm.org/citation.cfm?id=355707 | doi = 10.1145/355705.355707 | last1 = Gibbs | first1 = Norman E. | last2 = Poole | first2 = William G. | last3 = Stockmeyer | first3 = Paul K.  }}
* {{chú thích tạp chí | title = Sparse matrices in MATLAB: Design and Implementation | journal = SIAM Journal on Matrix Analysis and Applications | year = 1992 | volume = 13 | issue = 1 | pages = 333–356 | url = http://citeseer.ist.psu.edu/gilbert91sparse.html | doi = 10.1137/0613024 | last1 = Gilbert | first1 = John R. | last2 = Moler | first2 = Cleve | last3 = Schreiber | first3 = Robert | citeseerx = 10.1.1.470.1054 }}
* [http://faculty.cse.tamu.edu/davis/research.html  Sparse Matrix Algorithms Research] at the Texas A&M University.
* [https://sparse.tamu.edu/ SuiteSparse Matrix Collection]
* [http://www.small-project.eu SMALL project] A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.

{{Cấu trúc dữ liệu}}
{{Đại số tuyến tính số}}

[[Thể loại:Ma trận thưa]]