Title Page
Abstract
Contents
Chapter 1. Introduction 9
Chapter 2. Backgrounds 13
2.1. Matrix Update 13
2.2. Categories of Sparse Matrix Formats 14
2.2.1. Formats for Fast LA Operations 14
2.2.2. Formats for Fast Updates 15
Chapter 3. Proposed Sparse Matrix Formats 18
3.1. Dictionary of Keys (DOK) 20
3.2. List of Lists (LIL) 20
3.3. Red-Black Tree (RBT) 21
Chapter 4. RBForest 23
4.1. Design Choices 24
4.1.1. Individual Red-Black Trees for each row 24
4.1.2. Hash Table Connected to Red-Black Trees 25
4.2. Operations 25
4.2.1. Search 26
4.2.2. Insertion 26
4.2.3. Modification 27
4.2.4. Deletion 27
4.2.5. CSR Conversion 28
Chapter 5. Evaluation 30
5.1. Performance on Individual Operations 30
5.1.1. Insertion 32
5.1.2. Modification 33
5.1.3. CSR Conversion 33
5.1.4. Deletion 33
5.2. Performance on Dynamic Workload 34
5.2.1. Test with Synthetic Matrix 34
5.2.2. Test with Real-World Matrices 36
5.3. Memory Consumption 38
5.4. Additional Remarks on Experimental Results 39
Chapter 6. Conclusion and Future Works 42
Bibliography 43
국문초록 47
Table 3.1. Notation 18
Table 3.2. Performance comparison between update-friendly formats 19
Table 5.1. Statistics of the real-world sparse matrices 37
Figure 2.1. Matrix Update Procedures 13
Figure 2.2. A sparse matrix in CSR format 15
Figure 4.1. A sparse matrix in RBF format 23
Figure 5.1. Performance comparisons on individual operations 31
Figure 5.2. Performance comparison on dynamic workload with a synthetic matrix 35
Figure 5.3. Performance comparison on dynamic workload with real-world matrices 37
Figure 5.4. Memory Consumption of each sparse matrix format 38