1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
\documentclass[12pt]{article}
\usepackage{url}
\urlstyle{sf}
\usepackage[svgnames]{xcolor}
\usepackage[colorlinks,linkcolor=Blue,citecolor=Blue,urlcolor=Blue]{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{framed}
\usepackage{mdframed}
% \usepackage{geometry}
% \usepackage{pdflscape}
\newmdenv[backgroundcolor=white]{spec}
\newmdenv[backgroundcolor=yellow]{specbeta}
\hyphenation{Suite-Sparse}
\hyphenation{Graph-BLAS}
\hyphenation{Suite-Sparse-Graph-BLAS}
\newenvironment{packed_itemize}{
\begin{itemize}
\setlength{\itemsep}{1pt}
\setlength{\parskip}{0pt}
\setlength{\parsep}{0pt}
}{\end{itemize}}
\title{MATLAB test suite for SuiteSparse:GraphBLAS}
\author{Timothy A. Davis \\
\small
davis@tamu.edu, Texas A\&M University. \\
\small
http://suitesparse.com and http://aldenmath.com
}
%-------------------------------------------------------------------------------
\begin{document}
%-------------------------------------------------------------------------------
\maketitle
SuiteSparse:GraphBLAS includes a MATLAB implementation of nearly the entire
GraphBLAS specification, including all built-in types and operators. The
typecasting rules and integer operator rules from GraphBLAS are implemented in
MATLAB via \verb'mexFunctions' that call the GraphBLAS routines in C. All
other functions are written purely in MATLAB \verb'M'-files, and are given
names of the form \verb'GB_spec_*'. All of these MATLAB interfaces and
\verb'M'-file functions they are provided in the software distribution of
SuiteSparse:GraphBLAS. The purpose of this is two-fold:
\begin{itemize}
\item {\bf Illustration and documentation:} MATLAB is so expressive, and so
beautiful to read and write, that the \verb'GB_spec_*' functions read
almost like the exact specifications from the GraphBLAS API.
Excerpts and condensed versions of these functions appear in the
User Guide. The reader can benefit from studying the \verb'GB_spec_*'
functions to understand what a GraphBLAS operation is computing. For
example, in the User Guide, \verb'GrB_mxm' includes a condensed and
simplified version of \verb'GB_spec_mxm'.
\item {\bf Testing:} Testing the C interface to SuiteSparse:GraphBLAS is a
significant challenge since it supports so many different kinds of
operations on a vast range of semirings. It is difficult to tell from
looking at the result from a C function in GraphBLAS if the result is
correct. Thus, each function has been written twice: once in a
highly-optimized function in C, and again in a simple and elegant MATLAB
function. The latter is almost a direct translation of all the mathematics
behind the GraphBLAS API, so it is much easier to visually
inspect the \verb'GB_spec_*' version in MATLAB to ensure the correct
mathematics are being computed.
\end{itemize}
The following functions are included in the SuiteSparse:GraphBLAS software
distribution. Each has a name of the form \verb'GB_spec_*', and each of them
is a ``mimic'' of a corresponding C function in GraphBLAS. Not all functions
in the C API have a corresponding mimic; in particular, many of the vector
functions can be computed directly with the corresponding matrix version in the
MATLAB implementations. A list of these files is shown below:
\vspace{0.2in}
{\footnotesize
\begin{tabular}{ll}
MATLAB \verb'GB_spec' function & corresponding GraphBLAS \\
& function or method \\
\hline
\verb'GB_spec_accum.m' & ${\bf Z = C \odot T}$ \\
\verb'GB_spec_mask.m' & ${\bf C \langle M \rangle = Z}$ \\
\verb'GB_spec_accum_mask.m' & ${\bf C \langle M \rangle = C \odot T}$ \\
\hline
\verb'GB_spec_Vector_extractElement.m' & \verb'GrB_Vector_extractElement' \\
\hline
\verb'GB_spec_build.m' & \verb'GrB_Matrix_build' \\
\verb'GB_spec_Matrix_extractElement.m' & \verb'GrB_Matrix_extractElement' \\
\verb'GB_spec_extractTuples.m' & \verb'GrB_Matrix_extractTuples' \\
\hline
\verb'GB_spec_mxm.m' & \verb'GrB_mxm' \\
\verb'GB_spec_vxm.m' & \verb'GrB_vxm' \\
\verb'GB_spec_mxv.m' & \verb'GrB_mxv' \\
\hline
\verb'GB_spec_Vector_eWiseMult.m' & \verb'GrB_Vector_eWiseMult' \\
\verb'GB_spec_Matrix_eWiseMult.m' & \verb'GrB_Matrix_eWiseMult' \\
\verb'GB_spec_Vector_eWiseAdd.m' & \verb'GrB_Vector_eWiseAdd' \\
\verb'GB_spec_Matrix_eWiseAdd.m' & \verb'GrB_Matrix_eWiseAdd' \\
\hline
\verb'GB_spec_Vector_extract.m' & \verb'GrB_Vector_extract' \\
\verb'GB_spec_Matrix_extract.m' & \verb'GrB_Matrix_extract' \\
\verb'GB_spec_Col_extract.m' & \verb'GrB_Col_extract' \\
\hline
\verb'GB_spec_subassign.m' & \verb'GxB_subassign' \\
\verb'GB_spec_assign.m' & \verb'GrB_assign' \\
\hline
\verb'GB_spec_apply.m' & \verb'GrB_apply' \\
\hline
\verb'GB_spec_select.m' & \verb'GxB_select' \\
\hline
\verb'GB_spec_reduce_to_vector.m' & \verb'GrB_reduce' (to vector) \\
\verb'GB_spec_reduce_to_scalar.m' & \verb'GrB_reduce' (to scalar) \\
\hline
\verb'GB_spec_transpose.m' & \verb'GrB_transpose' \\
\hline
\verb'GB_spec_kron.m' & \verb'GrB_kronecker' \\
\hline
\end{tabular}
}
\vspace{0.2in}
Additional files are included for creating test problems and providing
inputs to the above files, or supporting functions:
\vspace{0.1in}
{\footnotesize
\begin{tabular}{ll}
MATLAB \verb'GB_spec' function & purpose \\
\hline
\verb'GB_spec_compare.m' & Compares output of C and MATLAB functions \\
\verb'GB_spec_random.m' & Generates a random matrix \\
\verb'GB_spec_op.m' & MATLAB mimic of built-in operators \\
\verb'GB_spec_operator.m' & Like \verb'GrB_*Op_new' \\
\verb'GB_spec_opsall.m' & List operators, types, and semirings \\
\verb'GB_spec_semiring.m' & Like \verb'GrB_Semiring_new' \\
\verb'GB_spec_descriptor.m' & mimics a GraphBLAS descriptor \\
\verb'GB_spec_identity.m' & returns the identity of a monoid \\
\verb'GB_spec_matrix.m' & conforms a MATLAB sparse matrix to GraphBLAS \\
\verb'GB_define.m' & creates draft of \verb'GraphBLAS.h' \\
\hline
\end{tabular}
}
An intensive test suite has been written that generates test graphs in MATLAB,
then computes the result in both the C version of the SuiteSparse:GraphBLAS and
in the MATLAB \verb'GB_spec_*' functions. Each C function in GraphBLAS has
a direct \verb'mexFunction' interface that allow the test suite in MATLAB
to call both functions.
This approach has its limitations:
\begin{itemize}
\item {\bf matrix classes:} MATLAB only supports sparse double, sparse double
complex, and sparse logical matrices. MATLAB can represent dense matrices
in all 13 built-in GraphBLAS data types, so in all these specification
\verb'M'-files, the matrices are either in dense format in the
corresponding MATLAB class, or they are held as sparse double or sparse
logical, and the actual GraphBLAS type is held with it as a string member
of a MATLAB \verb'struct'. To ensure the correct typecasting is computed,
most of the MATLAB scripts work on dense matrices, not sparse ones. As a
result, the MATLAB \verb'GB_spec_*' function are not meant for production
use, but just for testing and illustration.
\item {\bf integer operations:} MATLAB and GraphBLAS handle integer operations
differently. In MATLAB, an integer result outside the range of the integer
is set to maximum or minimum integer. For example, \verb'int8(127)+1' is
\verb'127'. This is useful for many computations such as image processing,
but GraphBLAS follows the C rules instead, where integer values wrap,
modulo style. For example, in GraphBLAS and in C, incrementing
\verb'(int8_t) 127' by one results in \verb'-128'. Of course, an
alternative would be for a MATLAB interface to create its own integer
operators, each of which would follow the MATLAB integer rules of
arithmetic. However, this would obscure the purpose of these
\verb'GB_spec_*' and \verb'GB_mex_*' test functions, which is to test the C
API of GraphBLAS. When the \verb'GB_spec_*' functions need to perform
integer computations and typecasting, they call GraphBLAS to do the work,
instead doing the work in MATLAB. This ensures that the \verb'GB_spec_*'
functions obtain the same results as their GraphBLAS counterparts.
\item {\bf elegance:} to simplify testing, each MATLAB \verb'mexFunction'
interface a GraphBLAS function is a direct translation of the C API. For
example, \verb'GB_mex_mxm' is a direct interface to the GraphBLAS
\verb'GrB_mxm', even down the order of parameters. This approach
abandons some of the potential features of MATLAB for creating elegant
\verb'M'-file interfaces in a highly usable form, such as the ability to
provide fewer parameters when optional parameters are not in use. These
\verb'mexFunctions', as written, are not meant to be usable in a user
application. They are not highly documented. They are meant to be fast,
and direct, to accomplish the goal of testing SuiteSparse:GraphBLAS in
MATLAB and comparing their results with the corresponding \verb'GB_spec_*'
function. They are not recommended for use in general applications in
MATLAB.
\item {\bf generality:} the MATLAB \verb'mexFunction' interface needs to
test the C API directly, so it must access content of SuiteSparse:GraphBLAS
objects that are normally opaque to an end user application. As a result,
these \verb'mexFunctions' do not serve as a general interface to any
conforming GraphBLAS implementation, but only to SuiteSparse:GraphBLAS.
\end{itemize}
In the MATLAB mimic functions, \verb'GB_spec_*', a GraphBLAS matrix \verb'A' is
represented as a MATLAB \verb'struct' with the following components:
\begin{itemize}
\item \verb'A.matrix': the values of the matrix. If \verb'A.matrix' is a
sparse double matrix, it holds a typecasted copy of the values of a
GraphBLAS matrix, unless the GraphBLAS matrix is also double
(\verb'GrB_FP64').
\item \verb'A.pattern': a logical matrix holding the pattern;
\verb'A.pattern(i,j)=true' if \verb'(i,j)' is in the pattern of \verb'A',
and \verb'false' otherwise.
\item \verb'A.class': the MATLAB class of the matrix corresponding to one of
the 13 built-in types. Normally this is simply \verb'class(A.matrix)'.
\item \verb'A.values': most of the GraphBLAS test \verb'mexFunctions' return
their result as a MATLAB sparse matrix, in the \verb'double' class. This
works well for all types except for the 64-bit integer types, since a
double has about 54 bits of mantissa which is less than the 64 bits
available in a long integer. To ensure no bits are lots, these values are
also returned as a vector. This enables \verb'GB_spec_compare' to ensure
the test results are identical down to the very last bit, and not just to
within roundoff error. Nearly all tests, even in double precision, check
for perfect equality, not just for results accurate to within round-off
error.
\end{itemize}
\end{document}
|
