add sparse matrices to GenSVM and reorganize update functionality

5 files changed, 146 insertions, 20 deletions

diff --git a/include/gensvm_base.h b/include/gensvm_base.h
index 03b7ffa..986e2a5 100644
--- a/include/gensvm_base.h
+++ b/include/gensvm_base.h
@@ -14,7 +14,7 @@
 #define GENSVM_BASE_H
 
 // includes
-#include "gensvm_globals.h"
+#include "gensvm_sparse.h"
 
 // type declarations
 
@@ -26,6 +26,7 @@
  * @param m 		number of predictors
  * @param *y 		pointer to vector of class labels
  * @param *Z 		pointer to augmented data matrix
+ * @param *spZ 		pointer to the sparse augmented data matrix
  * @param *RAW 		pointer to augmented raw data matrix
  * @param *J 		pointer to regularization vector
  * @param kerneltype 	kerneltype used in GenData::Z
@@ -46,6 +47,8 @@ struct GenData {
 	double *Z;
 	///< augmented data matrix (either equal to RAW or to the eigenvectors
 	///< of the kernel matrix)
+	struct GenSparse *spZ;
+	///< sparse representation of the augmented data matrix
 	double *RAW;
 	///< augmented raw data matrix
 	double *Sigma;
diff --git a/include/gensvm_io.h b/include/gensvm_io.h
index 9b0d973..3f34c1a 100644
--- a/include/gensvm_io.h
+++ b/include/gensvm_io.h
@@ -14,6 +14,7 @@
 
 // includes
 #include "gensvm_base.h"
+#include "gensvm_print.h"
 #include "gensvm_strutil.h"
 
 // function declarations
diff --git a/include/gensvm_optimize.h b/include/gensvm_optimize.h
index b342d6b..93f6676 100644
--- a/include/gensvm_optimize.h
+++ b/include/gensvm_optimize.h
@@ -2,7 +2,7 @@
  * @file gensvm_optimize.h
  * @author Gertjan van den Burg
  * @date August, 2013
- * @brief Header file for gensvm_train.c
+ * @brief Header file for gensvm_optimize.c
  *
  * @details
  * Contains function declarations for functions used to train a single
@@ -14,33 +14,20 @@
 #define GENSVM_OPTIMIZE_H
 
 #include "gensvm_sv.h"
-#include "gensvm_print.h"
 #include "gensvm_simplex.h"
+#include "gensvm_update.h"
 
 // function declarations
 void gensvm_optimize(struct GenModel *model, struct GenData *data);
 double gensvm_get_loss(struct GenModel *model, struct GenData *data, 
 		struct GenWork *work);
-
-double gensvm_calculate_omega(struct GenModel *model, struct GenData *data,
-		long i);
-bool gensvm_majorize_is_simple(struct GenModel *model, struct GenData *data, 
-		long i);
-void gensvm_calculate_ab_non_simple(struct GenModel *model, long i, long j,
-		double *a, double *b_aq);
-void gensvm_calculate_ab_simple(struct GenModel *model, long i, long j,
-		double *a, double *b_aq);
-double gensvm_get_alpha_beta(struct GenModel *model, struct GenData *data,
-		long i, double *beta);
-
-void gensvm_get_update(struct GenModel *model, struct GenData *data, 
-		struct GenWork *work);
 void gensvm_calculate_errors(struct GenModel *model, struct GenData *data,
 		double *ZV);
+void gensvm_calculate_ZV_dense(struct GenModel *model, struct GenData *data,
+		double *ZV);
+void gensvm_calculate_ZV_sparse(struct GenModel *model, struct GenData *data,
+		double *ZV);
 void gensvm_calculate_huber(struct GenModel *model);
 void gensvm_step_doubling(struct GenModel *model);
-int dposv(char UPLO, int N, int NRHS, double *A, int LDA, double *B, int LDB);
-int dsysv(char UPLO, int N, int NRHS, double *A, int LDA, int *IPIV, double *B,
-	       	int LDB, double *WORK, int LWORK);
 
 #endif
diff --git a/include/gensvm_sparse.h b/include/gensvm_sparse.h
new file mode 100644
index 0000000..bac576a
--- /dev/null
+++ b/include/gensvm_sparse.h
@@ -0,0 +1,80 @@
+/**
+ * @file gensvm_sparse.h
+ * @author Gertjan van den Burg
+ * @date 2016-10-11
+ * @brief Header file for gensvm_sparse.c
+ *
+ * @details
+ * Contains declarations of the GenSparse structure and related functions.
+ *
+ * @copyright
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License
+ as published by the Free Software Foundation; either version 2
+ of the License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+
+ */
+
+#ifndef GENSVM_SPARSE_H
+#define GENSVM_SPARSE_H
+
+// includes
+#include "gensvm_globals.h"
+
+// type declarations
+
+/**
+ * @brief A structure to represent a sparse matrix in CSR format
+ *
+ * @details
+ * This structure holds a sparse matrix in the classic CSR format. Refer to
+ * <a href="https://en.wikipedia.org/wiki/Sparse_matrix">Wikipedia</a> for 
+ * more details. The total storage requirement for this format is 
+ * 2*nnz+n_row+1, so it only makes sense to use this format if the number of 
+ * nonzeros is smaller than @f$(n(m - 1) - 1)/2@f$.
+ *
+ * @note
+ * We use @f$n@f$ for rows, and @f$m@f$ for columns, to conform to GenSVM 
+ * notation. This is in exact contrast with the Wikipedia page.
+ *
+ * @param nnz 		number of nonzero elements
+ * @param n_row 	rows of the matrix
+ * @param n_col 	columns of the matrix
+ * @param values 	nonzero values (length nnz)
+ * @param ia 		row indices (length n+1)
+ * @param ja 		column indices (length nnz)
+ */
+struct GenSparse {
+	long nnz;
+	///< number of nonzero elements
+	long n_row;
+	///< number of rows of the original matrix
+	long n_col;
+	///< number of columns of the original matrix
+
+	double *values;
+	///< actual nonzero values, should be of length nnz
+	int *ia;
+	///< cumulative row lengths, should be of length n+1
+	int *ja;
+	///< column indices, should be of length nnz
+};
+
+struct GenSparse *gensvm_init_sparse();
+void gensvm_free_sparse(struct GenSparse *sp);
+long gensvm_count_nnz(double *A, long rows, long cols);
+bool gensvm_could_sparse(double *A, long rows, long cols);
+struct GenSparse *gensvm_dense_to_sparse(double *A, long rows, long cols);
+double *gensvm_sparse_to_dense(struct GenSparse *A);
+
+#endif
diff --git a/include/gensvm_update.h b/include/gensvm_update.h
new file mode 100644
index 0000000..9242d86
--- /dev/null
+++ b/include/gensvm_update.h
@@ -0,0 +1,55 @@
+/**
+ * @file gensvm_update.h
+ * @author Gertjan van den Burg
+ * @date 2016-10-14
+ * @brief Header file for gensvm_update.c
+
+ * Copyright (C)
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License
+ as published by the Free Software Foundation; either version 2
+ of the License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+
+ */
+
+#ifndef GENSVM_UPDATE_H
+#define GENSVM_UPDATE_H
+
+#include "gensvm_base.h"
+#include "gensvm_print.h"
+
+// function declarations
+double gensvm_calculate_omega(struct GenModel *model, struct GenData *data,
+		long i);
+bool gensvm_majorize_is_simple(struct GenModel *model, struct GenData *data,
+		long i);
+void gensvm_calculate_ab_non_simple(struct GenModel *model, long i, long j,
+		double *a, double *b_aq);
+void gensvm_calculate_ab_simple(struct GenModel *model, long i, long j,
+		double *a, double *b_aq);
+double gensvm_get_alpha_beta(struct GenModel *model, struct GenData *data,
+		long i, double *beta);
+void gensvm_get_update(struct GenModel *model, struct GenData *data, 
+		struct GenWork *work);
+void gensvm_get_ZAZ_ZB_dense(struct GenModel *model, struct GenData *data,
+		struct GenWork *work);
+void gensvm_get_ZAZ_ZB_sparse(struct GenModel *model, struct GenData *data,
+		struct GenWork *work);
+void gensvm_get_ZAZ_ZB(struct GenModel *model, struct GenData *data, 
+		struct GenWork *work);
+int dposv(char UPLO, int N, int NRHS, double *A, int LDA, double *B,
+		int LDB);
+int dsysv(char UPLO, int N, int NRHS, double *A, int LDA, int *IPIV,
+		double *B, int LDB, double *WORK, int LWORK);
+
+#endif