Arrays and Special Matrices

Arrays are the most fundamental storage structure in programming, and almost every other data structure is built on top of them. For special matrices and sparse matrices that contain many repeated elements or many zero elements, compressed storage saves a great deal of space, which is why it is a frequent topic in the postgraduate entrance exam. This chapter revolves around one core question, namely how to store a matrix in less space, and develops the address computation of multidimensional arrays, the compressed storage schemes for special matrices, and the two classic representations of sparse matrices. After reading this chapter you will be able to master the storage structure of one-dimensional and two-dimensional arrays, compute the address of any element, understand the address formulas for row-major and column-major storage together with the difference between them, apply the compressed storage formulas for symmetric, lower-triangular and tridiagonal matrices, master the triple representation and the orthogonal list representation of sparse matrices, and use compressed storage to solve problems of matrix access and matrix operations.

Questions This Chapter Answers

A 10×10 matrix needs 100 storage units, yet a symmetric matrix really needs only half of them, and a sparse matrix may need only a few dozen non-zero elements. How can a matrix be compressed to the smallest possible space while still allowing any element to be accessed? Answering that question requires the row-major and column-major address formulas of multidimensional arrays, the compression patterns of symmetric, triangular and tridiagonal matrices, and the triple and orthogonal list representations of sparse matrices.

Basic route: storage of multidimensional arrays → compressed storage of special matrices; master the address computation formulas first.

Advanced route: sparse matrices → typical applications → summary; understand when the triple representation and the orthogonal list are the right choice.

Storage of Multidimensional Arrays

One-Dimensional Arrays

Let the base address of the one-dimensional array $A[0..n-1]$ be $LOC(a_0)$ and let every element occupy $L$ storage units. Then:

$LOC(a_i) = LOC(a_0) + i \times L$

Two-Dimensional Arrays (Row-Major)

Let the two-dimensional array $A[m][n]$ have $m$ rows and $n$ columns. In row-major storage the address of the element $A[i][j]$ is:

$LOC(A[i][j]) = LOC(A[0][0]) + (i \times n + j) \times L$

Derivation: in row-major order there are $i \times n$ elements before row $i$, and there are $j$ further elements before column $j$ of row $i$, so the offset is $i \times n + j$.

Two-Dimensional Arrays (Column-Major)

In column-major storage the address of the element $A[i][j]$ is:

$LOC(A[i][j]) = LOC(A[0][0]) + (j \times m + i) \times L$

Derivation: there are $j \times m$ elements before column $j$, and there are $i$ further elements before row $i$ of column $j$, so the offset is $j \times m + i$.

Exercises

Exercise 1

A two-dimensional array A[0..4][0..5] is stored in row-major order. If every element occupies 2 storage units and the address of A[0][0] is 1000, what is the address of A[3][4]? ( )

A. 1034 B. 1040 C. 1044 D. 1048

Exercise 2

How are multidimensional arrays stored in memory, and how is the address of an element computed?

Compressed Storage of Special Matrices

A special matrix is a matrix that contains many identical elements or many zero elements. It can be stored in compressed form in a one-dimensional array, which saves space.

Symmetric Matrices

A symmetric matrix satisfies $A[i][j] = A[j][i]$, so only the lower triangle including the diagonal has to be stored, which takes $\frac{n(n+1)}{2}$ elements.

The index of the lower-triangular element $A[i][j]$ (with $i \ge j$) in the one-dimensional array $B[0..n(n+1)/2-1]$ is:

$k = \frac{i(i+1)}{2} + j$

Derivation: there are $0+1+2+\cdots+i = \frac{i(i+1)}{2}$ elements before row $i$, and there are $j$ further elements before column $j$ of row $i$.

Lower-Triangular Matrices

The storage scheme is the same as for a symmetric matrix, except that the upper triangle is represented by a single constant, so $\frac{n(n+1)}{2} + 1$ storage units are needed.

Tridiagonal Matrices (Banded Matrices)

A tridiagonal matrix has non-zero elements only on the main diagonal and the two diagonals next to it, that is, $3n-2$ non-zero elements in total. Stored in row-major order, the index of $A[i][j]$ (with $|i-j| \le 1$) is:

$k = 2i + j$

Derivation: there are $3(i) - 1$ elements before row $i$ (each of the first $i$ rows contributes 3 elements, except that the first row contributes only 2), and within row $i$ the element in column $j$ is the $j-(i-1)$-th one.

Exercises

Exercise 1

Suppose a 10×10 symmetric matrix A is stored in compressed form, with its lower triangle kept in a one-dimensional array B. What is the index of A[5][3] (indices counted from 0) in B? ( )

A. 13 B. 14 C. 15 D. 16

Exercise 2

Briefly describe how the compressed storage formula for a symmetric matrix is derived.

Sparse Matrices

A sparse matrix is a matrix in which the number of non-zero elements is far smaller than the number of zero elements, typically with fewer than 5 percent non-zero elements.

Triple Representation

Only the row number, the column number and the value of each non-zero element are stored, represented by a table of triples:

#define MAXSIZE 100
typedef struct {
    int row;   // row number
    int col;   // column number
    int value; // element value
} Triple;

typedef struct {
    Triple data[MAXSIZE];
    int rows, cols, nums;  // number of rows, columns and non-zero elements
} TSMatrix;

Advantages: it saves an enormous amount of storage space. Disadvantages: accessing an arbitrary element requires a traversal and a search, so the efficiency is low.

Orthogonal List Representation

The non-zero elements are stored as linked list nodes, and every non-zero element node is attached simultaneously to a row list and a column list, which makes matrix addition, multiplication and similar operations convenient.

typedef struct OLNode {
    int row, col, value;
    struct OLNode *right;  // points to the next non-zero element in the same row
    struct OLNode *down;   // points to the next non-zero element in the same column
} OLNode, *OLink;

Exercises

Exercise 1

How is a sparse matrix stored in compressed form, and which methods are available?

Typical Applications

The compressed storage of arrays and matrices is not pure theory: from image processing to the solution of large-scale systems of equations, the storage layout of the data often decides how fast a program can run. This section puts the sequential storage, the address computation and the compressed storage formulas described above back into real scenarios, and explains when an ordinary two-dimensional array is good enough and when it is worth paying the extra cost of index conversion for a special matrix.

Typical Applications of Arrays

• Data storage: putting data of the same type into a contiguous block of memory and locating an element directly by base address plus index times element length is the basis of almost every program.
• Searching and sorting: binary search relies on the orderedness of an array and on its random access capability; classic sorting algorithms such as insertion sort, merge sort and quicksort are all built on top of arrays.
• Matrix operations: image processing, linear algebra and state space computation all perform matrix multiplication, and the contiguous storage of an array directly determines the memory access pattern and the cache hit rate.

Typical Applications of Sparse Matrices

• Adjacency matrices of graphs: when a sparse graph is stored as an adjacency matrix, almost every position is 0; switching to the triple representation or the orthogonal list keeps only the non-zero elements and reduces the storage from $O(n^2)$ to a quantity proportional to the number of non-zero elements.
• Scientific computing: the matrices produced by the numerical solution of partial differential equations or by the finite element method are often non-zero only near the main diagonal, so compressed storage is the standard practice.
• Solving large-scale systems of equations: sparse matrix factorizations such as LU and Cholesky exploit the structure of the zero elements to skip useless computation, which is the key to solver performance.

Trade-offs in Choosing a Representation

Common Misconceptions

What compressed storage saves is space, and what it costs is that locating an element by index is no longer a single multiplication and addition but may become a table lookup or even a full traversal. Compressed storage therefore only pays off when the structure of the matrix is genuinely special and the access pattern is dominated by whole-block traversal; if the code frequently accesses a compressed matrix at random by index, the trade-off is usually a bad one.

Returning to the formulas of this chapter: the index conversion of a symmetric matrix is $k = \frac{i(i+1)}{2} + j$ (for $i \ge j$), the tridiagonal matrix uses $k = 2i + j$, and a triple of a sparse matrix is the combination of three numbers, namely (row, column, value). Memorize these three expressions and combine them with the selection table above, and you will be able to decide which storage scheme a concrete question calls for.

Summary

The conclusion of this chapter can be compressed into one sentence: the price of an array is paid in random access by index, and the price of a matrix is paid in storing it more compactly according to its structure. The terminology table aligns terms such as row-major order, symmetric matrix, triple and orthogonal list with their English names, while the key takeaways gather the address formulas and the compressed index formulas that have to be remembered, so that one quick pass before the exam connects all the formulas of this chapter.

Terminology Reference

Key Takeaways

• Row-major address formula: $LOC = LOC_{00} + (i \times n + j) \times L$
• Compressed index of a symmetric matrix: $k = \frac{i(i+1)}{2} + j$ (for $i \ge j$)
• Compressed index of a tridiagonal matrix: $k = 2i + j$
• A sparse matrix is stored with triples or an orthogonal list, which saves space but slows down random access