DS - 4.1

Introduction

Data is often available in tabular form

Tabular: 표

Tabular data is often represented in arrays

Matrix is an example of tabular data and is often represented as a 2-dimensional array

• Matrices are normally indexed beginning at 1 rather than 0
• Matrices also support operations such as add, multiply, and transpose, which are NOT supported by c++'s 2D array.

It is possible to reduce time and space using a customized representation of multidimensional arrays

This chapter focuses on

• Row- and column-major mapping and representations of multidimensional arrays
• the class Matrix
• Special matrices
  • Diagonal, tridiagonal, triangular, symmetric, sparse

1D Array Representation in C++

1-dimensional array x = [a, b, c, d]

map into contiguous memory locations

location(x[i]) = start + i

2D Arrays

The elements of a 2-dimensional array a declared as:

int a[3][4];

may be shown as a table

a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]

Rows of a 2D Array

a[0][0] a[0][1] a[0][2] a[0][3] row 0
a[1][0] a[1][1] a[1][2] a[1][3] row 1
a[2][0] a[2][1] a[2][2] a[2][3] row 2

Columns of a 2D Array

a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]

column 0 column 1 column 2 column 3

2D Array Representation in C++

2-dimensional array x

a, b, c, d

e, f, g, h

i, j, k, l

view 2D array as a 1D array of rows

x = [row0, row1, row 2]

row 0 = [a, b, c, d]

row 1 = [e, f, g, h]

row 2 = [i, j, k, l]

and store as 4 1D arrays

space overhead = overhead for 4 1D arrays

This representation is called the array-of-arrays representation.

Requires contiguous memory of size 3, 4, 4, and 4 for the 4 1D arrays.

1 memory block of size number of rows and number of rows blocks of size number of columns

Row-Major Mapping

Example 3 x 4 array:

a b c d
e f g h
i j k l

• Convert into 1D array y by collecting elements by rows.
• Within a row elements are collected from left to right.
• Rows are collected from top to bottom.
• We get y[] = {a, b, c, d, e, f, g, h, i, j, k, l}

Locating Element x[i][j]

assume x has r rows and c columns

each row has c elements

i rows to the left of row i

so ic elements to the left of x[i][0]

x[i][j] is mapped to position

ic + j of the 1D array

Column-Major Mapping

a b c d

e f g h

i j k l

Convert into 1D array y by collecting elements by columns.

Within a column elements are collected from top to bottom.

Columns are collected from left to right.

We get y = {a, e, i, b, f, j, c, g, k, d, h, l}

Row- and Column-Major Mappings

2D Array int a[3][6];

a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[0][5]
a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5]
a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] a[2][5]

row major mapping

0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17

column major mapping

0 3 6 9 12 15
1 4 7 10 13 16
2 5 8 11 14 17

Row-major order mapping functions

map(i1,i2) = i1u2+i2 //for 2D arrays

map(i1,i2,i3) = i1u2u3+i2u3+i3 //for 3D arrays

What is the mapping function for Figure 7.2(a)?

• map(i1,i2) = 6i1+i2

• map(2,3) = 2*6 + 3

Column-major order mapping functions 15

Irregular 2D Arrays

x[]

1
2 3
4 5 6
7 8 9 10

Irregular 2-D array: the length of rows is not required to be the same.

Matrices

m x n matrix is a table with m rows and n columns.

M(i,j) denotes the element in row i and column j.

Common matrix operations

– transpose

– addition

– multiplication

Matrix Operations

Transpose

The result of transposing an m x n matrix is an n x m matrix with property:

MT(j,i) = M(i,j), 1 <= i <= m, 1 <= j <= n

Addition

The sum of matrices is only defined for matrices that have the same dimensions.

The sum of two m x n matrices A and B is an m x n matrix with the property:

C(i,j) = A(i,j) + B(i,j), 1 <= i <= m, 1 <= j <= n

Multiplication

The product of matrices A and B is only defined when the number of columns in A is equal to the number of rows in B.

Let A be m x n matrix and B be a n x q matrix. A*B will produce an m x q matrix with the following property:

C(i,j) = Σ(k=1...n) A(i,k) * B(k,j)
where 1 <= i <= m and 1 <= j <= q

손으로 써보는게 더 편 할 듯.

A Matrix Class

There are many possible implementations for matrices.

// use a built-in 2 dimensional array

T matrix[m][n]

// use the Array2D class

Array2D<T> matrix(m,n)

// or flatten the matrix into a one-dimensional array

template<class T> class Matrix {

21

private: int rows, columns; T *data;

};

Shortcomings of using a 2D Array for a Matrix

Indexes are off by 1.

C++ arrays do not support matrix operations such as add, transpose, multiply, and so on.

• Suppose that x and y are 2D arrays.Cannot do x+y, x – y, x * y, etc. in C++.

We need to develop a class matrix for object-oriented support of all matrix operations.

구현 코드

Class Matrix{
    matrix(Row, Col);
    private:
        int theRow;
        int theCol;
        int * element;
}

Matrix:: matrix(int theRow, int theCol)
{
    if(theRow<0 || theCol<0)
        error;
    this -> theRows = Row;
    this -> theCol = Col;
    this -> element = new int[Row*col];
}

실제 사용 코드

int main(){
    matrix * myMatrix;
    myMatrix = new matrix(3, 4);
}

• operator 구현
  operator c++ 문법??

class Matrix()
{
    matrix(Row, Col)
    operator +
    ...
}

//this + m = new Matrix
Matrix :: operator + (matrix & m)
{
    //check if they have the same dimension
    if(this -> theRow != m.theRow || this -> theCol != m.theCol)
        //throw error
    //add element 
    for(int i=0; i<theRow * theCol; i++)
        w.element[i] = this-> element[i] + m.element[i]
    
}

참고로 . operator, 그리고 -> 의 차이는 시험에 출제될 수 있다.

곱셈연산은 다른 수업자료를 참고해보자.

Special Matrices

A square matrix has the same number of rows and columns.

Some special forms of square matrices are

• Diagonal: M(i, j) = 0 for i != j

• Tridiagonal: M(i, j) = 0 for |i-j| <= 1 //정확한 공식이??

• Lower triangular: M(i, j) = 0 for i < j

• Uppertriangular: M(i, j) = 0 for i > j

• Symmetric M(i, j) = M(j, i) for all i and j

Diagonal

2 0 0 0
0 1 0 0
0 0 4 0
0 0 0 6

Tridiagonal

2 1 0 0
3 1 3 0
0 5 2 7
0 0 9 0

Lower Triangular

2 0 0 0
5 1 0 0
0 3 1 0
4 2 7 0

Upper triangular

2 1 3 0
0 1 3 8
0 0 1 6
0 0 0 0

Symmetric

2 4 6 0
4 1 9 5
6 9 4 7
0 5 7 0

symmetric 예시?

traffic matrix

s for seoul
s d b k
s 0 100 400 300
d 100 0
b 400 0
k 300 0

Why are we interested in these “special” matrices?

• We can provide more efficient implementations for specific special matrices
• Rather than having a space complexity of O(n^2), we can find an implementation that is O(n)
• We need to be clever about the "store" and "retrieve" operations to reduce time.

25

Diagonal Matrix

Naive way to represent n x n diagonal matrix

• Td[n][n]

• d[i-1][j-1]forD(i,j)

• requires n^2 x sizeof(T) bytes of memory

Better way

• Td[n]

• d[i-1] for D(i,j) where i = j
  0 for D(i,j) where i ≠ j

• requires n x sizeof(T) bytes of memory

l See Program 7.8 for the class diagonalMatrix

26

Tridiagonal Matrix

2 1 0 0
3 1 3 0
0 5 2 7
0 0 9 0

Nonzero elements lie on one of three diagonals:

– main diagonal:i=j
– diagonal below main diagonal:i=j+1
– diagonal above main diagonal:i=j-1

3n-2 elements on these three diagonals: T t[3n-2]

Mappings of Figure 7.2(b)

• by row [2, 1, 3, 1, 3, 5, 2, 7, 9, 0]
• by column [2, 3, 1, 1, 5, 3, 2, 9, 7, 0]
• by diagonal [3, 5, 9, 2, 1, 2, 0, 1, 3, 7]

실제로 어떻게 적용? (by diagonal)

Mapping by diagonals beginning with the lowest

switch(i - j){
    case 1:  //lower diagonal
        return t[i - 2];
    case 2:  //main diagnoal
        return t[n + i -2];
    case 3:  //upper diagonal
        return t[2 * n + i - 2];
    default: return 0;
}
s

2 1 0 0
3 1 3 0
0 5 2 7
0 0 9 0

D(2, 1) -> t[0]
D(3, 2) - > t[1]
...
D(m, n-1) -> t[n -2]
D(1, 1) -> t[n-1]
D(2, 2) -> t[n]
...
D(n, n) -> t[(n-2)+n] = t[2n-2]

Triangular Matrix

Nonzero elements lie in the region marked “nonzero” in the figure below

1+2+...+n = Σ(i=1..n) = n(n+1)/2 elements in the nonzero region

Both triangular matrices may be represented using 1-D array

T t[n(n+1)/2]

2 0 0 0
5 1 0 0
0 3 1 0
4 2 7 0

Mappings

by row?

[2,5,1,0,3,1,4,2,7,0]

by column?

[2,5,0,4,1,3,2,1,7,0]

Lower Triangular Matrix

Mapping by row

L(i,j) = 0 //if i < j
L(i,j) = t[1+2+...+(i-1)+(j-1)] if i ≥ j
= t[i(i-1)/2 + j-1]

• See Program 7.12 for the method lowerTriangularMatrix::set

Upper Triangular Matrix

2 1 3 0
0 1 3 8
0 0 1 6
0 0 0 0

Mapping by column

a[2, 1, 1, 3, 3, 1, 0, 8, 6, 0]

L(i,j) = ? //if i>j

L(i,j) = ? //if i<=j

Symmetric Matrix

An n x n matrix can be represented using 1-D array of size n(n+1)/2 by storing either the lower or upper triangle of the matrix

Use one of the methods for a triangular matrix

The elements that are not explicitly stored may be computed from those that are stored

– How do we compute this?

Sparse Matrix

A matrix is sparse if many of its elements are zero

A matrix that is not sparse is dense

The boundary is not precisely defined

• Diagonal and tridiagonal matrices are sparse
• We classify triangular matrices as dense

Two possible representations

• array
• linkedlist

Array Representation of Sparse Matrix

The nonzero entries may be mapped into a 1D array in row-major order

To reconstruct the matrix structure, need to record the row and column each nonzero comes from

코드

template<class T>
class Term{
    private:
        int row, col;
        T value;
}

template <class T>
class sparceMatrix{
    private:
        int rows, cols;
        int terms;
        Term<T> *a;
        int MaxTerms;
    public:
        //...
};

Linked Representation of Sparse Matrix

A shortcoming of the 1-D array of a sparce matrix is that we need to know the number of nozero terms in each of the sparce matrices when the array is created.

A linked repersantation can overcome this shortcoming.