Chapter 1

Experimental Results
In this chapter, we will present computation results for the algorithm proposed in this thesis.
Section 1.1 provides the environment in which we test our algorithm. In section 1.2 we
will give details of test data set that we have used in our experiment. Lower bound results
using different data sets for our algorithm and comparison with other results are discussed
in section 1.3. In section 1.4 we will provide our heuristic results and make a comparison
with other results. Section 1.5 describe about the results of our iterative algorithm. Finally
in section 1.5 we will conclude the chapter.

1.1

Test Environment

We have tested our experiment in the following environment:

Machine :
Operating System :
Desktop :
Physical Memory (RAM) :
Virtual Memory(Swap):

1.2

Data Results

In this section, we will discuss about the details of our data sets. The data sets consist
of number of rows, columns, non-zero , maximum and minimum number of non-zero in
a row and a column of a matrix. The first data set is for large size of matrices which are
1

1.2. DATA RESULTS

collected from University of Florida sparse matrix collection[]. These matrices are used to
compare result with unidirectional partition results. The other data sets are obtained from
Harwell-Boeing test matrices[] and University of Florida Matrix Collection.Part of these
data sets are used to compare lower bound with lower bound result of Judes and Jones[].
Full of this data set is compared with ridawnss [] unidirectional partition, mini goyals[]
bidirectional result. The data is also used to compare lower bound calculated by DSM.
Table 1.1: Matrix Statistics for Set 1
Matrix
af23560
cage11
cage12
e30r2000
e40r0100
lhr10
lhr14
lhr34
lhr71c
lpcrea
lpcreb
lpcred
lpfit2d
lpdfl001
lpken11
lpken13
lpken18
lpmarosr7
lppds10
lppds20
lpstocfor3

n
23560
39082
130228
9661
17281
10672
14270
35152
70304
3516
9648
8926
25
6071
14694
28632
105127
3136
16558
33874
16675

m
23560
39082
130228
9661
17281
10672
14270
35152
70304
7248
77137
73948
10524
12230
21349
42659
154699
9408
49932
108175
23541

nnz
484256
559722
2032536
306356
553956
232633
307858
764014
1528092
18168
260785
246614
129042
35632
49058
97246
358171
144848
107605
232647
76473

max
min max
21
11
21
31
3
31
33
5
33
62
8
62
62
8
62
63
1
36
63
1
36
63
1
36
63
1
36
360
1
14
844
1
14
808
1
13
10500 1427 17
228
2
14
122
1
3
170
1
3
325
1
3
48
5
46
96
1
3
96
1
3
15
1
18

min
10
3
5
8
8
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

In the table 1.4 and 1.5 Matrix is used for Matrix name. n , m and nnz are used to
represent number of rows , columns and total number of non-zeroes in the matrix. max ,
min describes maximum and minimum number of non-zeroes in any row of the matrix and
max and min is used to tell maximum and minimum number of non-zeroes in any column
2

1.2. DATA RESULTS

Table 1.2: Matrix Statistics for Set 2

Matrix
abb313
adlittle
agg
agg2
agg3
arc130
ash219
ash292
ash331
ash608
ash958
blend
bore3d
bp0
bp1000
bp1200
bp1400
bp1600
bp200
bp400
bp600
bp800
can1054
can1072
can256
can268
can292
can634
can715
curtis54
dwt1007
dwt1242
dwt2680
dwt419
dwt59
eris1176

n
313
56
488
516
516
130
219
292
331
608
958
74
233
822
822
822
822
822
822
822
822
822
1054
1072
256
268
292
634
715
54
1007
1242
2680
419
59
1176

m
176
138
615
758
758
130
85
292
104
188
292
114
334
822
822
822
822
822
822
822
822
822
1054
1072
256
268
292
634
715
54
1007
1242
2680
419
59
1176

nnz
1557
424
2862
4740
4756
1282
438
2208
662
1216
1916
522
1448
3276
4661
4726
4790
4841
3802
4028
4172
4534
12196
12444
2916
3082
2540
7228
6665
291
8575
10426
25026
3563
267
18552

max
6
27
19
49
49
124
2
14
2
2
2
29
73
266
308
311
311
304
283
295
302
304
35
35
83
37
35
28
105
12
10
12
19
13
6
99

min
1
1
2
2
2
1
2
4
2
2
2
2
1
1
1
1
1
1
1
1
1
1
6
6
4
4
4
2
2
3
3
2
4
13
2
2

max
26
11
43
43
43
124
9
14
12
12
13
16
28
20
21
21
21
21
21
21
21
21
35
35
83
37
35
28
105
16
10
12
19
6
6
99

min
2
1
1
1
1
1
2
4
3
2
3
1
1
1
1
1
1
1
1
1
1
1
6
6
4
4
4
2
2
3
3
2
4
6
2
2

1.2. DATA RESULTS

Matrix
fs5411
fs5412
gent113
ibm32
impcola
impcolb
impcolc
impcold
impcole
israel
lunda
lundb
scagr25
scagr7
shl0
shl200
shl400
stair
standata
str0
str200
str400
tuff
vtpbase
watt2
west0067
west0381
west0497
will199
will57

n
541
541
113
32
207
59
137
425
225
174
147
147
471
129
663
663
663
356
359
363
363
363
333
198
1856
67
381
497
199
57

m
541
541
113
32
207
59
137
425
225
316
147
147
671
185
663
663
663
614
1274
363
363
363
628
346
1856
67
381
497
199
57

nnz
4285
4285
655
126
572
312
411
1339
1308
2443
2449
2441
1725
465
1687
1726
1712
4003
3230
2454
3068
3157
4561
1051
11550
294
2157
1727
701
281

max
11
11
20
8
8
7
8
10
12
119
21
21
10
10
422
440
426
36
745
34
30
33
113
38
128
6
25
28
6
11

min
1
1
1
2
1
2
1
1
1
2
5
5
1
1
1
1
1
2
2
1
1
1
0
1
1
1
1
1
1
2

max
541
541
27
7
5
12
8
10
23
136
21
21
9
9
4
4
4
34
10
34
26
34
25
12
65
10
50
55
9
11

min
5
5
1
2
1
1
1
1
1
1
5
5
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
2
2

1.2. DATA RESULTS

of the matrix.
Table 1.3: Matrix Statistics for Set 2
Matrix
abb313
adlittle
agg
agg2
agg3
arc130
ash219
ash292
ash331
ash608
ash958
blend
bore3d
bp0
bp1000
bp1200
bp1400
bp1600
bp200
bp400
bp600
bp800
can1054
can1072
can256
can268
can292
can634
can715
curtis54
dwt1007
dwt1242
dwt2680
dwt419
dwt59

lbDSM
10
27
19
19
49
124
3
14
6
5
6
29
73
266
308
311
311
304
283
295
302
304
35
35
83
37
35
28
105
12
10
12
19
14
6

lbLexicographical
6
4
6
9
9
16
2
8
2
2
2
6
6
5
6
6
7
7
5
6
6
6
12
12
12
12
9
12
10
6
9
9
10
9
5

lbDegree
6
7
9
14
14
16
2
8
2
2
2
8
13
7
8
8
8
8
7
7
7
8
12
12
12
12
9
12
10
6
9
9
10
9
5

Color

1.2. DATA RESULTS

Matrix
lbDSM
eris1176 99
fs5411
11
fs5412
11
gent113
20
ibm32
8
impcola
8
impcolb
10
impcolc
8
impcold
10
impcole
20
israel
119
lunda
21
lundb
21
scagr25
10
scagr7
10
shl0
422
shl200
440
shl400
426
stair
36
standata
745
str0
34
str200
30
str400
33
tuff
113
vtpbase
38
watt2
128
west0067 7
west0381 27
west0497 28
will199
7
will57
11

lbDegree
20
8
8
6
4
3
6
3
4
8
19
17
17
3
3
3
3
3
15
3
14
11
11
9
4
7
5
6
4
4
5

lbLexicographical
39
8
8
9
4
3
6
4
4
11
29
18
18
4
4
3
3
3
18
4
17
17
18
12
5
7
5
6
6
4
6

Color

1.2. DATA RESULTS

Table 1.4: Matrix Statistics for Set 1

Matrix
af23560
cage11
cage12
e30r2000
e40r0100
lhr10
lhr14
lhr34
lhr71c
lpcrea
lpcreb
lpcred
lpfit2d
lpdfl001
lpken11
lpken13
lpken18
lpmarosr7
lppds10
lppds20
lpstocfor3

row color

column color

ridwan row

0
0

67
66

66
66

35

64

1.2. DATA RESULTS

Table 1.5: Matrix Statistics for Set 2

Matrix
abb313
adlittle
agg
agg2
agg3
arc130
ash219
ash292
ash331
ash608
ash958
blend
bore3d
bp0
bp1000
bp1200
bp1400
bp1600
bp200
bp400
bp600
bp800
can1054
can1072
can256
can268
can292
can634
can715
curtis54
dwt1007
dwt1242
dwt2680
dwt419
dwt59
eris1176

row color
0
12
0
2
2
9
0
0
0
0
0
6
22
14
22
21
21
21
15
16
17
22
0
0
25
10
3
5
3
1
0
0
2
0
0
1

column color
10
0
26
25
26
17
4
14
6
6
6
10
3
3
0
0
0
0
4
4
2
0
32
32
3
22
14
21
16
10
10
13
17
15
6
79

ridwan row
26
12
43
43
43
124
9
14
12
12
13
16
28
20
21
21
21
21
21
21
21
21
35
35
83
37
35
28
105
16
10
13
19
15
6
99

ridwan column

1.2. DATA RESULTS

Matrix
fs5411
fs5412
gent113
ibm32
impcola
impcolb
impcolc
impcold
impcole
israel
lunda
lundb
scagr25
scagr7
shl0
shl200
shl400
stair
standata
str0
str200
str400
tuff
vtpbase
watt2
west0067
west0381
west0497
will199
will57

row color
0
0
6
1
5
0
0
0
0
41
0
0
9
9
4
4
4
36
10
5
31
17
11
2
1
0
6
3
2
0

column color
13
13
12
6
0
10
8
10
21
7
23
23
0
0
0
0
0
0
0
22
0
19
8
11
11
8
4
14
7
7

ridwan row
541
541
27
7
5
16
8
11
31
136
23
23
9
9
4
4
4
36
10
35
31
36
25
13
65
12
50
55
9
11

ridwan column