Line data Source code
1 : /**
2 : * @file gensvm_sparse.c
3 : * @author G.J.J. van den Burg
4 : * @date 2016-10-11
5 : * @brief Functions for dealing with sparse data matrices
6 : *
7 : * @copyright
8 : Copyright 2016, G.J.J. van den Burg.
9 :
10 : This file is part of GenSVM.
11 :
12 : GenSVM is free software: you can redistribute it and/or modify
13 : it under the terms of the GNU General Public License as published by
14 : the Free Software Foundation, either version 3 of the License, or
15 : (at your option) any later version.
16 :
17 : GenSVM is distributed in the hope that it will be useful,
18 : but WITHOUT ANY WARRANTY; without even the implied warranty of
19 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 : GNU General Public License for more details.
21 :
22 : You should have received a copy of the GNU General Public License
23 : along with GenSVM. If not, see <http://www.gnu.org/licenses/>.
24 :
25 : */
26 :
27 : #include "gensvm_sparse.h"
28 :
29 : /**
30 : * @brief Initialize a GenSparse structure
31 : *
32 : * @details
33 : * A GenSparse structure is used to hold a sparse data matrix. We work with
34 : * Compressed Row Storage (CSR) storage, also known as old Yale format.
35 : *
36 : * @return initialized GenSparse instance
37 : */
38 14 : struct GenSparse *gensvm_init_sparse(void)
39 : {
40 14 : struct GenSparse *sp = Malloc(struct GenSparse, 1);
41 14 : sp->nnz = 0;
42 14 : sp->n_row = 0;
43 14 : sp->n_col = 0;
44 :
45 14 : sp->values = NULL;
46 14 : sp->ia = NULL;
47 14 : sp->ja = NULL;
48 :
49 14 : return sp;
50 : }
51 :
52 : /**
53 : * @brief Free an allocated GenSparse structure
54 : *
55 : * @details
56 : * Simply free a previously allocated GenSparse structure by freeing all of
57 : * its components. Finally, the structure itself is freed, and the pointer is
58 : * set to NULL for safety.
59 : *
60 : * @param[in] sp GenSparse structure to free
61 : */
62 14 : void gensvm_free_sparse(struct GenSparse *sp)
63 : {
64 14 : free(sp->values);
65 14 : free(sp->ia);
66 14 : free(sp->ja);
67 14 : free(sp);
68 14 : sp = NULL;
69 14 : }
70 :
71 : /**
72 : * @brief Count the number of nonzeros in a matrix
73 : *
74 : * @details
75 : * This is a utility function to count the number of nonzeros in a dense
76 : * matrix. This is simply done by comparing with 0.0.
77 : *
78 : * @param[in] A a dense matrix (RowMajor order)
79 : * @param[in] rows the number of rows of A
80 : * @param[in] cols the number of columns of A
81 : *
82 : * @return the number of nonzeros in A
83 : */
84 17 : long gensvm_count_nnz(double *A, long rows, long cols)
85 : {
86 17 : long i, nnz = 0;
87 :
88 374 : for (i=0; i<rows*cols; i++)
89 357 : nnz += (A[i] != 0.0) ? 1 : 0;
90 17 : return nnz;
91 : }
92 :
93 : /**
94 : * @brief Compare the number of nonzeros is such that sparsity if worth it
95 : *
96 : * @details
97 : * This is a utility function, see gensvm_could_sparse() for more info.
98 : *
99 : * @param[in] nnz number of nonzero elements
100 : * @param[in] rows number of rows
101 : * @param[in] cols number of columns
102 : *
103 : * @return whether or not sparsity is worth it
104 : */
105 9 : bool gensvm_nnz_comparison(long nnz, long rows, long cols)
106 : {
107 9 : return (nnz < (rows*(cols-1.0)-1.0)/2.0);
108 : }
109 :
110 : /**
111 : * @brief Check if it is worthwile to convert to a sparse matrix
112 : *
113 : * @details
114 : * It is only worth to convert to a sparse matrix if the amount of sparsity is
115 : * sufficient. For this to be the case, the number of nonzeros must be
116 : * smaller than @f$(n_{row}(n_{col} - 1) - 1)/2@f$. This is tested here. If
117 : * the amount of nonzero entries is small enough, the function returns the
118 : * number of nonzeros. If it is too big, it returns -1.
119 : *
120 : * @sa
121 : * gensvm_nnz_comparison()
122 : *
123 : * @param[in] A matrix in dense format (RowMajor order)
124 : * @param[in] rows number of rows of A
125 : * @param[in] cols number of columns of A
126 : *
127 : * @return whether or not sparsity is worth it
128 : */
129 5 : bool gensvm_could_sparse(double *A, long rows, long cols)
130 : {
131 5 : long nnz = gensvm_count_nnz(A, rows, cols);
132 5 : return gensvm_nnz_comparison(nnz, rows, cols);
133 : }
134 :
135 : /**
136 : * @brief Convert a dense matrix to a GenSparse structure if advantageous
137 : *
138 : * @details
139 : * This utility function can be used to convert a dense matrix to a sparse
140 : * matrix in the form of a GenSparse struture. Note that the allocated memory
141 : * must be freed by the caller. The user should first check whether using a
142 : * sparse matrix is worth it by calling gensvm_could_sparse().
143 : *
144 : * @param[in] A a dense matrix in RowMajor order
145 : * @param[in] rows number of rows of the matrix A
146 : * @param[in] cols number of columns of the matrix A
147 : *
148 : * @return a GenSparse struct
149 : */
150 10 : struct GenSparse *gensvm_dense_to_sparse(double *A, long rows, long cols)
151 : {
152 : double value;
153 : long row_cnt;
154 10 : long i, j, cnt, nnz = 0;
155 10 : struct GenSparse *spA = NULL;
156 :
157 10 : nnz = gensvm_count_nnz(A, rows, cols);
158 :
159 10 : spA = gensvm_init_sparse();
160 :
161 10 : spA->nnz = nnz;
162 10 : spA->n_row = rows;
163 10 : spA->n_col = cols;
164 10 : spA->values = Calloc(double, nnz);
165 10 : spA->ia = Calloc(long, rows+1);
166 10 : spA->ja = Calloc(long, nnz);
167 :
168 10 : cnt = 0;
169 10 : spA->ia[0] = 0;
170 78 : for (i=0; i<rows; i++) {
171 68 : row_cnt = 0;
172 313 : for (j=0; j<cols; j++) {
173 245 : value = matrix_get(A, cols, i, j);
174 245 : if (value != 0) {
175 171 : row_cnt++;
176 171 : spA->values[cnt] = value;
177 171 : spA->ja[cnt] = j;
178 171 : cnt++;
179 : }
180 : }
181 68 : spA->ia[i+1] = spA->ia[i] + row_cnt;
182 : }
183 :
184 10 : return spA;
185 : }
186 :
187 : /**
188 : * @brief Convert a GenSparse structure to a dense matrix
189 : *
190 : * @details
191 : * This function converts a GenSparse structure back to a normal dense matrix
192 : * in RowMajor order. Note that the allocated memory must be freed by the
193 : * caller.
194 : *
195 : * @param[in] A a GenSparse structure
196 : *
197 : * @return a dense matrix
198 : */
199 1 : double *gensvm_sparse_to_dense(struct GenSparse *A)
200 : {
201 : double value;
202 : long i, j, jj;
203 1 : double *B = Calloc(double, (A->n_row)*(A->n_col));
204 5 : for (i=0; i<A->n_row; i++) {
205 8 : for (jj=A->ia[i]; jj<A->ia[i+1]; jj++) {
206 4 : j = A->ja[jj];
207 4 : value = A->values[jj];
208 4 : matrix_set(B, A->n_col, i, j, value);
209 : }
210 : }
211 :
212 1 : return B;
213 : }
|
