ต วอย างเมทร กซ มากเลขศ นย 11220000003344000000556677000000088000000099 displaystyle left begin smallmatrix 11 amp 22 am

ตัวอย่างเมทริกซ์มากเลขศูนย์ $\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)$ เมทริกซ์มากเลขศูนย์ข้างต้นมีองค์ประกอบที่ไม่ใช่ศูนย์เพียง 9 องค์ประกอบและ 26 องค์ประกอบที่เป็นศูนย์ ดังนั้น ความมากเลขศูนย์แหร็มเป็น 74% และ ความหนาแน่นเป็น 26%

ในสาขาการวิเคราะห์เชิงตัวเลข และ วิทยาการคอมพิวเตอร์ เมทริกซ์มากเลขศูนย์ (อังกฤษ: sparse matrix) หรือ แถวลำดับมากเลขศูนย์ (อังกฤษ: sparse array) หมายถึงเมทริกซ์ที่องค์ประกอบส่วนใหญ่เป็นศูนย์ ไม่มีคำจำกัดความที่แน่ชัดว่าต้องมีองค์ประกอบที่เป็นศูนย์อยู่มากเท่าไดจึงจะถือว่าเป็นเมทริกซ์ที่มากเลขศูนย์ (sparse) แต่เงื่อนไขโดยทั่วไปคือจำนวนองค์ประกอบที่ไม่ใช่ศูนย์นั้นใกล้เคียงกับจำนวนแถวหรือสดมภ์โดยประมาณ ในทางกลับกัน เมทริกซ์ที่องค์ประกอบส่วนใหญ่ไม่เป็นศูนย์จะถือว่าเป็นเมทริกซ์ที่ หนาแน่น (dense) จำนวนองค์ประกอบที่เป็นศูนย์ในเมทริกซ์หารด้วยจำนวนองค์ประกอบทั้งหมด บางครั้งเรียกว่า ความมากเลขศูนย์ (sparsity) ของเมทริกซ์

เมทริกซ์มากเลขศูนย์ที่ได้เมื่อแก้ปัญหาด้วยระเบียบวิธีไฟไนต์เอลิเมนต์ในสองมิติ องค์ประกอบที่ไม่เป็นศูนย์จะเป็นสีดำ

ตามหลักการแล้ว ความมากเลขศูนย์จะเกิดขึ้นกับระบบที่มีการโต้ตอบแบบคู่กันเพียงเล็กน้อย ตัวอย่างเช่น ถ้าเราพิจารณาเส้นของลูกบอลที่เชื่อมต่อถึงกันด้วยสปริง นี่เป็นระบบแบบมากเลขศูนย์ เนื่องจากลูกบอลแต่ละลูกจะจับคู่กับตัวข้าง ๆ เท่านั้น ในทางตรงข้าม ระบบนี้จะเป็นเมทริกซ์หนาแน่น หากลูกบอลลูกหนึ่งเชื่อมต่อกันด้วยสปริงกับลูกบอลอีกลูกที่อยู่ในแนวเดียวกัน แนวคิดเรื่องความมากเลขศูนย์มีประโยชน์ในด้านการใช้งาน เช่น คณิตศาสตร์เชิงการจัด และ และ การวิเคราะห์เชิงตัวเลข ซึ่งโดยปกติแล้วความหนาแน่นของข้อมูลสำคัญและการเชื่อมต่อจะต่ำ เมทริกซ์มากเลขศูนย์ขนาดใหญ่มักปรากฏในการประยุกต์ใช้ทางวิทยาศาสตร์ และ วิศวกรรมศาสตร์ เมื่อแก้สมการเชิงอนุพันธ์ย่อย

เมื่อจัดเก็บและจัดการเมทริกซ์แบบมากเลขศูนย์บนคอมพิวเตอร์ จะเป็นประโยชน์และมักจำเป็นต้องใช้ ขั้นตอนวิธีพิเศษและโครงสร้างข้อมูลที่ใช้ประโยชน์จากโครงสร้างแบบมากเลขศูนย์ของเมทริกซ์ เนื่องจากเมทริกซ์มากเลขศูนย์มักใช้ในด้านการเรียนรู้ของเครื่อง บางเครื่องจึงอาจถูกสร้างขึ้นมาสำหรับเมทริกซ์แบบนี้โดยเฉพาะ การดำเนินการที่ใช้โครงสร้างเมทริกซ์หนาแน่นมาตรฐานจะช้าและไม่มีประสิทธิภาพเมื่อนำไปใช้กับเมทริกซ์มากเลขศูนย์ขนาดใหญ่ การสูญเสียการประมวลผลและหน่วยความจำไปกับค่าศูนย์ ข้อมูลมากเลขศูนย์จะบีบอัดได้ง่ายกว่าดังนั้นจึงใช้พื้นที่จัดเก็บน้อยกว่ามาก สำหรับเมทริกซ์มากเลขศูนย์ที่มีขนาดใหญ่มาก อาจเป็นไปได้ที่จะใช้การดำเนินการกับเมทริกซ์หนาแน่นมาตรฐาน

สมการเชิงอนุพันธ์ย่อยอรจถูกวิเคราะห์ได้โดยใช้ วิธีไฟไนต์เอลิเมนต์ ฯลฯ โดยทั่วไปจะกลายเป็น ระบบสมการเชิงเส้นที่มีเมทริกซ์มากเลขศูนย์ เป็นเมทริกซ์สัมประสิทธิ์

ในสาขาการวิเคราะห์เชิงตัวเลข มีวิธีการแก้ปัญหาหลายวิธีที่ใช้เมทริกซ์มากเลขศูนย์ การจัดเก็บเฉพาะองค์ประกอบที่ไม่ใช่ศูนย์ของเมทริกซ์มากเลขศูนย์อย่างชาญฉลาด จะช่วยให้จัดการกับปัญหามิติขนาดใหญ่ได้ง่ายขึ้น ข้อดีอีกประการหนึ่งคือ ตัวอย่างเช่น สามารถคำนวณผลคูณของเวกเตอร์และเมทริกซ์ได้โดยใช้ความพยายามเพียงเล็กน้อย นั้นใช้ได้ดีในการประมวลผลทางคอมพิวเตอร์โดยใช้เมทริกซ์มากเลขศูนย์ซึ่งมักจะเกี่ยวข้องกับการเข้าถึงหน่วยความจำแบบสุ่ม และยังคงเป็นกระบวนการที่ ทั่วไปและ นั้นยังทำได้ไม่ค่อยดี

รูปแบบการจัดเก็บข้อมูล

โดยทั่วไปเมทริกซ์จะถูกเก็บไว้ในแถวลำดับสองมิติ แต่ละองค์ประกอบของแถวลำดับแสดงถึงองค์ประกอบ $a i, j$ ของเมทริกซ์ และเข้าถึงได้โดยใช้ดัชนี สองตัว $i$ และ $j$ ตามแบบแผนทั่วไป $i$ หมายถึงดัชนีแถวโดยนับจากบนลงล่าง และ $j$ หมายถึงดัชนีสดมภ์โดยนับจากซ้ายไปขวา สำหรับเมทริกซ์ขนาด $m \times n$ จำนวนหน่วยความจำที่ต้องใช้ในการจัดเก็บเมทริกซ์ในรูปแบบนี้เป็นสัดส่วนกับ $m \times n$ (แม้ว่าจะมักลืมไปว่าขนาดของเมทริกซ์ก็ต้องถูกจัดเก็บด้วย)

ในกรณีของเมทริกซ์มากเลขศูนย์ การจัดเก็บเฉพาะองค์ประกอบที่ไม่เป็นศูนย์จะช่วยลดจำนวนหน่วยความจำที่ต้องการได้อย่างมาก การใช้โครงสร้างข้อมูลที่แตกต่างกันขึ้นอยู่กับจำนวนและการกระจายขององค์ประกอบที่ไม่ใช่ศูนย์ ช่วยให้ประหยัดหน่วยความจำได้มากเมื่อเทียบกับวิธีการพื้นฐาน ข้อเสียคือการเข้าถึงแต่ละองค์ประกอบนั้นซับซ้อนกว่า และจำเป็นต้องมีโครงสร้างเพิ่มเติมเพื่อให้สามารถกู้คืนเมทริกซ์ดั้งเดิมได้อย่างชัดเจน

ด้วยเหตุนี้ จึงมีรูปแบบไฟล์แบบต่าง ๆ สำหรับจัดเก็บเมทริกซ์มากเลขศูนย์

รูปแบบจะแบ่งออกเป็นสองกลุ่ม

รูปแบบที่รองรับการแก้ไขอย่างมีประสิทธิภาพ
- DOK (พจนานุกรมคีย์)
- LIL (รายการ)
- COO
รูปแบบที่รองรับการเข้าถึงที่มีประสิทธิภาพและการจัดการเมทริกซ์
- CSR
- CSC
- BSR

ชื่อต่อไปนี้เป็นไปตามที่ใช้ใน , และ ให้พิจารณาเมทริกซ์มากเลขศูนย์ A ต่อไปนี้เป็นตัวอย่าง

${\begin{bmatrix}1&2&3&0\\0&0&0&1\\2&0&0&2\\0&0&0&1\\\end{bmatrix}}$

พจนานุกรมคีย์

พจนานุกรมคีย์ (Dictionary of Key, DOK) เป็นวิธีการที่ใช้ (แถว, สดมภ์) เป็นคีย์และจัดเก็บไว้ในแถวลำดับแบบจับคู่

รายการของรายการ

รายการของรายการ (list of list, LIL) เป็นวิธีการที่สร้างรายการสำหรับแต่ละแถวและจัดเก็บสิ่งอันดับ (สดมภ์, ค่า) ในรายการนั้น

พิกัด

พิกัด (coordinate, COO) เป็นวิธีการแสดงเมทริกซ์เป็นชุดของหลายสิ่งอันดับ [ค่า, ดัชนีแถว, ดัชนีสดมภ์]

การจัดเรียงองค์ประกอบของเมทริกซ์ A พร้อมกับพิกัด (ดัชนี) จะให้ผลลัพธ์ดังนี้

A = [1 2 3 0 0 0 0 1 2 0 0 2 0 0 0 1] # ค่า IA = [1 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4] # ดัชนีแถว JA = [1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4] # ดัชนีสดมภ์

ในที่นี้หากระบุว่า "ค่าที่ไม่มีอยู่จะถือเป็นองค์ประกอบศูนย์" องค์ประกอบที่เป็นศูนย์ทั้งหมดสามารถลบทิ้ง ซึ่งส่งผลให้ได้

A = [1 2 3 1 2 2 1] # ค่า IA = [1 1 1 2 3 3 4] # ดัชนีแถว JA = [1 2 3 4 1 4 4] # ดัชนีสดมภ์

เป็นการแทนด้วยเมทริกซ์มากเลขศูนย์ A ในรูปแบบ COO

หากต้องการแก้ไของค์ประกอบที่เป็นศูนย์ของเมทริกซ์ COO ให้ไม่เป็นศูนย์ ก็แค่ต้องเพิ่มหลายสิ่งอันดับที่ไม่เป็นศูนย์หลังจากนั้นเท่านั้น ซึ่งเป็นวิธีที่มีประสิทธิภาพ

ที่เก็บข้อมูลแถวบีบอัด

ที่เก็บข้อมูลแถวที่ถูกบีบอัด (compressed row storage, CRS) หรือ แถวมากเลขศูนย์บีบอัด (compressed sparse row, CSR) เป็นวิธีการบีบอัดแถวลำดับดัชนีแถว

ในวิธี CSR ขั้นแรกให้จัดเรียงเมทริกซ์สองมิติตามทิศทางของแถว ต่อไปจะพิจารณาว่า "ค่าที่ไม่มีอยู่จะถือเป็นองค์ประกอบศูนย์" และองค์ประกอบที่เป็นศูนย์ทั้งหมดจะถูกลบทิ้ง ในขั้นตอนนี้ หากจัดเรียงดัชนีด้วยแถวและสดมภ์ จะมีลักษณะดังนี้:

data = [1 2 3 1 2 2 1] # ค่า IA = [1 1 1 2 3 3 4] # ดัชนีแถว JA = [1 2 3 4 1 4 4] # ดัชนีสดมภ์

ในที่นี้เราจะมุ่งความสนใจไปที่แถวลำดับดัชนีแถว (IA) ในปัจจุบัน แต่ละองค์ประกอบมีดัชนีแถวที่ชัดเจน แต่สามารถรับมาได้โดยอัตโนมัติหากทราบการแบ่งแถว ตัวอย่างเช่น IA[1] = IA[2] = IA[3] = 1 แต่ถ้ารู้ว่า "บรรทัดแรกเริ่มจากองค์ประกอบแรก และบรรทัดที่ 2 เริ่มจากองค์ประกอบที่ 4" ดังนั้นจะได้ว่า IA[1:4]=[1 1 1] ในทันที นี่เป็นผลมาจากกฎที่ว่าวิธี CSR จัดเรียงทีละแถวแล้วลบองค์ประกอบที่เป็นศูนย์

การแสดงดัชนีแถวนี้สามารถมองได้ว่าเป็นแถวลำดับของตัวชี้ส่วนหัวของแถว นั่นคือ indptr = [ptr_row_1 ptr_row2 ...] ขณะนี้แถวลำดับดัชนีสดมภ์ JA เป็นเพียงแถวลำดับเดียวที่ระบุดัชนีโดยตรง ดังนั้นจะเปลี่ยนชื่อเป็น indices ซึ่งจะได้ว่า

data = [1 2 3 1 2 2 1] # ค่า indices = [1 2 3 4 1 4 4] # ดัชนีสดมภ์ indptr = [1 4 5 7] # ตัวชี้แถว

นี่เป็นการแสดงเมทริกซ์มากเลขศูนย์ A ในรูปแบบ CSR

รูปแบบ CSR ช่วยให้เข้าถึงแถวได้ดีขึ้น เมื่อเข้าถึงแถวแรกสามารถดึงเอาข้อมูลโดย data[indptr[1]:indptr[2]] และดัชนีสดมภ์ที่มี indices[indptr[1]:indptr[2]] (ดัชนีแถวคือ 1 แน่นอน) ในขณะที่ ในรูปแบบ COO ขั้นแรกจะกวาดดูความยาวทั้งหมดของแถวลำดับดัชนีแถว IA แสดงรายการหมายเลของค์ประกอบ k ที่สอดคล้องกับ IA[k] == 1 จากนั้นจะต้องทำการเข้าถึง k ทั้งหมดโดยใช้ data[k], indices[k]

ในทางตรงกันข้าม รูปแบบ CSR ทำให้เข้าถึงสดมภ์ได้ไม่ดี เมื่อต้องการเข้าถึงสดมภ์แรก ต้องกวาดหา indices ตามความยาวทั้งหมด และแสดงรายการหมายเลของค์ประกอบ k ที่ indices[k] == 1 จากนั้นกวาดหา indptr เพื่อให้ได้ดัชนีแถว และต้องค้นหา n ที่ทำให้ indptr[n] <= k < indptr[n+1] ที่แต่ละ k

ที่เก็บข้อมูลสดมภ์บีบอัด

ที่เก็บข้อมูลสดมภ์บีบอัด (compressed column storage, CCS) หรือ สดมภ์มากเลขศูนย์บีบอัด (compressed sparse Column, CSC) จะเหมือนกับ CRS แต่อิงสดมภ์แทนที่จะอิงแถว

ที่เก็บข้อมูลแนวทแยงบีบอัด

ที่เก็บข้อมูลแนวทแยงบีบอัด (compressed diagonal storage, CDS) และ diagonal (DIA) เป็นรูปแบบ CRS/CSR ในหน่วยเมทริกซ์แนวทแยง

เมทริกซ์เส้นขอบฟ้า (SKS, SKY)

เมทริกซ์เส้นขอบฟ้า (skyline matrix) ใช้สำหรับ

ที่จัดเก็บแถวบีบอัดแบบบล็อก

ที่จัดเก็บแถวบีบอัดแบบบล็อก (block compressed row storage, BCRS) หรือ แถวมากเลขศูนย์แบบบล็อก (Block Sparse Row, BSR) เหมือนกับ CRS แต่ทำเป็นในหน่วยบล็อก

อ้างอิง

"ศัพท์บัญญัติ ๔๐ สาขาวิชา สำนักงานราชบัณฑิตยสภา".{{}}: CS1 maint: url-status ()
Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). An efficient sparse-dense matrix multiplication on a multicore system. IEEE. doi:10.1109/icct.2017.8359956. ISBN .
"Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory" (Press release) (ภาษาอังกฤษ). สืบค้นเมื่อ 2019-12-02.
"Cerebras Systems Unveils the Industry's First Trillion Transistor Chip". www.businesswire.com (ภาษาอังกฤษ). 2019-08-19. สืบค้นเมื่อ 2019-12-02.
"プロセッサ開発のセンス～第4回ベクトル・プロセッサ～ | 株式会社エヌエスアイテクス（NSITEXE,Inc.）" (ภาษาญี่ปุ่น). 2023-02-22. สืบค้นเมื่อ 2023-06-18.
Survey of Sparse Matrix Storage Formats
Intel® MKL Sparse BLAS Overview | Intel® Developer Zone
"scipy.sparse.coo_matrix ... A sparse matrix in COOrdinate format." scipy.sparse.coo_matrix. scipy. 2022-03-05閲覧.
"scipy.sparse.csr_matrix ... Compressed Sparse Row matrix" scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.
"csr_matrix((data, indices, indptr) ... is the standard CSR representation where the column indices for row i are stored in indices[indptr[i]:indptr[i+1]] and their corresponding values are stored in data[indptr[i]:indptr[i+1]]." scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.
"Advantages of the CSR format ... efficient row slicing" scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.
"csr_matrix((data, indices, indptr) ... is the standard CSR representation where the column indices for row i are stored in indices[indptr[i]:indptr[i+1]] and their corresponding values are stored in data[indptr[i]:indptr[i+1]]." scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.
"Disadvantages of the CSR format slow column slicing operations" scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.
"scipy.sparse.csc_matrix ... Compressed Sparse Column matrix" scipy.sparse.csc_matrix. scipy. 2022-03-05閲覧.
"scipy.sparse.bsr_matrix ... Block Sparse Row matrix" scipy.sparse.bsr_matrix. 2022-03-05閲覧.

[1] "ศัพท์บัญญัติ ๔๐ สาขาวิชา สำนักงานราชบัณฑิตยสภา".{{}}: CS1 maint: url-status ()

[Yan_Wu_Liu_Gao_2017_p.2-2] Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). An efficient sparse-dense matrix multiplication on a multicore system. IEEE. doi:10.1109/icct.2017.8359956. ISBN .

[3] "Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory" (Press release) (ภาษาอังกฤษ). สืบค้นเมื่อ 2019-12-02.

[4] "Cerebras Systems Unveils the Industry's First Trillion Transistor Chip". www.businesswire.com (ภาษาอังกฤษ). 2019-08-19. สืบค้นเมื่อ 2019-12-02.

[5] "プロセッサ開発のセンス～第4回ベクトル・プロセッサ～ | 株式会社エヌエスアイテクス（NSITEXE,Inc.）" (ภาษาญี่ปุ่น). 2023-02-22. สืบค้นเมื่อ 2023-06-18.

[6] Survey of Sparse Matrix Storage Formats

[7] Intel® MKL Sparse BLAS Overview | Intel® Developer Zone

[8] "scipy.sparse.coo_matrix ... A sparse matrix in COOrdinate format." scipy.sparse.coo_matrix. scipy. 2022-03-05閲覧.

[9] "scipy.sparse.csr_matrix ... Compressed Sparse Row matrix" scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.

[:02-10] "csr_matrix((data, indices, indptr) ... is the standard CSR representation where the column indices for row i are stored in indices[indptr[i]:indptr[i+1]] and their corresponding values are stored in data[indptr[i]:indptr[i+1]]." scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.

[11] "Advantages of the CSR format ... efficient row slicing" scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.

[:03-12] "csr_matrix((data, indices, indptr) ... is the standard CSR representation where the column indices for row i are stored in indices[indptr[i]:indptr[i+1]] and their corresponding values are stored in data[indptr[i]:indptr[i+1]]." scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.

[13] "Disadvantages of the CSR format slow column slicing operations" scipy.sparse.csr_matrix. scipy. 2022-03-05閲覧.

[14] "scipy.sparse.csc_matrix ... Compressed Sparse Column matrix" scipy.sparse.csc_matrix. scipy. 2022-03-05閲覧.

[15] "scipy.sparse.bsr_matrix ... Block Sparse Row matrix" scipy.sparse.bsr_matrix. 2022-03-05閲覧.