[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [38873] branches/soc-2011-avocado/blender/ intern/autoseam: Sparse matrix routines are implemented and integrated with the current code to make it more efficient .
shuvro sarker
shuvro05 at gmail.com
Sun Jul 31 08:38:24 CEST 2011
Revision: 38873
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=38873
Author: shuvro
Date: 2011-07-31 06:38:23 +0000 (Sun, 31 Jul 2011)
Log Message:
-----------
Sparse matrix routines are implemented and integrated with the current code to make it more efficient.
Modified Paths:
--------------
branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.cpp
branches/soc-2011-avocado/blender/intern/autoseam/CMakeLists.txt
branches/soc-2011-avocado/blender/intern/autoseam/EigenSolver.cpp
branches/soc-2011-avocado/blender/intern/autoseam/EigenSolver.h
branches/soc-2011-avocado/blender/intern/autoseam/EigenSolverArpack.cpp
branches/soc-2011-avocado/blender/intern/autoseam/EigenSolverArpack.h
Added Paths:
-----------
branches/soc-2011-avocado/blender/intern/autoseam/SparseMatrix.h
Modified: branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.cpp
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.cpp 2011-07-31 06:26:03 UTC (rev 38872)
+++ branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.cpp 2011-07-31 06:38:23 UTC (rev 38873)
@@ -35,6 +35,7 @@
#define THRESHOLD_ZERO 0.0005
#define EXTRA_MEMORY_SIZE 10
+#define VALUE_ZERO 0.0000001
AutoseamAdjacency::AutoseamAdjacency(int dimension)
@@ -132,7 +133,18 @@
// Need to modify the errors of the commented code.
EigenSolverArpack solver(matrix_dimension);
- solver.matrix = a;
+ //solver.matrix = a;
+ // We need to set up our matrix here.
+
+ //logic: if any member of a is non-zero then push it into the matrix
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < n; j++) {
+ if(fabs(a(i,j)) > VALUE_ZERO){
+ solver.sparse_matrix(i,j) = a(i,j);
+ }
+ }
+ }
+
eigen_vectors = solver.calculate_eigen_space();
if(a.rows() && a.cols() && eigen_vectors != NULL){
@@ -154,7 +166,7 @@
//if(fabs(eigen_values[f]) > 0.0005){
printf("eigen values: %f\n", fabs(solver.eigen_values[f]));
- if(fabs(solver.eigen_values[f]) > 0.0005){
+ if(fabs(solver.eigen_values[f]) > THRESHOLD_ZERO){
int loop;
//now construct a vector with the values
Modified: branches/soc-2011-avocado/blender/intern/autoseam/CMakeLists.txt
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/CMakeLists.txt 2011-07-31 06:26:03 UTC (rev 38872)
+++ branches/soc-2011-avocado/blender/intern/autoseam/CMakeLists.txt 2011-07-31 06:38:23 UTC (rev 38873)
@@ -56,6 +56,7 @@
AutoseamAdjacency.cpp
EigenSolver.h
EigenSolver.cpp
+ SparseMatrix.h
)
set (SRC_AUTOSEAM_ARPACK
Modified: branches/soc-2011-avocado/blender/intern/autoseam/EigenSolver.cpp
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/EigenSolver.cpp 2011-07-31 06:26:03 UTC (rev 38872)
+++ branches/soc-2011-avocado/blender/intern/autoseam/EigenSolver.cpp 2011-07-31 06:38:23 UTC (rev 38873)
@@ -33,25 +33,10 @@
EigenSolver::EigenSolver(int dimension)
{
matrix_dimension = dimension;
- //num_eigen_vectors = eigen_vectors;
+ sparse_matrix = SparseMatrix<double> (dimension);
- // Allocate memories for eigenspace
-
}
-int EigenSolver::multiply_matrix_vector(int dimension, double *result, double *input)
-{
- for (int i = 0; i < A.n ; i++) {
- *(result + i) = 0.0;
- }
-
- for (int k = 0; k < A.nnz; k++) {
- *(result + A.i[k]) += A.v[k] * (*(input + A.j[k]));
- }
-
- return 0;
-}
-
EigenSolver::~EigenSolver()
{
}
Modified: branches/soc-2011-avocado/blender/intern/autoseam/EigenSolver.h
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/EigenSolver.h 2011-07-31 06:26:03 UTC (rev 38872)
+++ branches/soc-2011-avocado/blender/intern/autoseam/EigenSolver.h 2011-07-31 06:38:23 UTC (rev 38873)
@@ -29,31 +29,21 @@
#ifndef EIGEN_SOLVER_H
#define EIGEN_SOLVER_H
-struct SparseMatrix{
- int n; // matrix dimension
- int nnz; // number of non-zero coefficients
- int *i; // row indices, array of size nnz;
- int *j; // column indices, array of size nnz;
- double *v; // non-zero coefficients, array of size nnz;
-};
+#include "SparseMatrix.h"
+
+
class EigenSolver{
protected:
- SparseMatrix A;
- bool is_allocated;
int matrix_dimension;
- // int num_eigen_vectors;
- double *eigen_vectors; // This is of size matrix_dimension * num_eigen_vectors
- double *eigen_values; // This is of size matrix_dimension
+
public:
- int num_eigen_vectors;
+ int num_eigen_vectors;
+ SparseMatrix<double> sparse_matrix;
EigenSolver(int dimension);
- int allocate_matrix(int dimension, int non_zero); // allocates memory for matrix
- int set_matrix(int row, int column, double value); // sets a specific element of Sparse Matrix A
- virtual double * calculate_eigen_space() = 0; // Declared it as pure virtual, so that subclasses must have to implement this.
- int multiply_matrix_vector(int dimension, double *result, double *input);
+ virtual double * calculate_eigen_space() = 0; // Declared it as pure virtual, so that subclasses must have to implement this.
~EigenSolver();
Modified: branches/soc-2011-avocado/blender/intern/autoseam/EigenSolverArpack.cpp
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/EigenSolverArpack.cpp 2011-07-31 06:26:03 UTC (rev 38872)
+++ branches/soc-2011-avocado/blender/intern/autoseam/EigenSolverArpack.cpp 2011-07-31 06:38:23 UTC (rev 38873)
@@ -30,7 +30,7 @@
#include "MEM_guardedalloc.h"
#include <stdio.h>
-
+//#define EIGEN_DEBUG_ARPACK 1
#define NUM_EIGEN_VAL 100
#define minimum(a,b) (a <= b) ? a : b;
@@ -40,11 +40,6 @@
}
-//EigenSolverArpack:: EigenSolverArpack(int dimension)
-//{
-// matrix_dimension = dimension;
-// //num_eigen_vectors = eigen_vectors;
-//}
EigenSolverArpack::~EigenSolverArpack()
{
printf("Destructor is being called.");
@@ -58,7 +53,7 @@
}
-int EigenSolverArpack:: mul_matrix_vector(int dimension, double *vec, double * result)
+/*int EigenSolverArpack:: mul_matrix_vector(int dimension, double *vec, double * result)
{
int i;
Eigen::VectorXd output(dimension);
@@ -81,7 +76,7 @@
return 0;
-}
+}*/
double * EigenSolverArpack:: calculate_eigen_space()
@@ -204,7 +199,8 @@
if (ido == -1 || ido == 1) {
//perform matrix-vector multiplication
//av_(&nx, &workd[ipntr[0] - 1], &workd[ipntr[1] - 1]);
- mul_matrix_vector(n, &workd[ipntr[0] - 1], &workd[ipntr[1] - 1]);
+ //mul_matrix_vector(n, &workd[ipntr[0] - 1], &workd[ipntr[1] - 1]);
+ sparse_matrix.mul_matrix_vector(n, &workd[ipntr[0] - 1], &workd[ipntr[1] - 1]);
//goto L10;
}
else{
Modified: branches/soc-2011-avocado/blender/intern/autoseam/EigenSolverArpack.h
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/EigenSolverArpack.h 2011-07-31 06:26:03 UTC (rev 38872)
+++ branches/soc-2011-avocado/blender/intern/autoseam/EigenSolverArpack.h 2011-07-31 06:38:23 UTC (rev 38873)
@@ -47,12 +47,12 @@
//int num_eigen_values;
Eigen::VectorXd eigen_values;
- Eigen::MatrixXd matrix;
+ //Eigen::MatrixXd matrix;
EigenSolverArpack(int dimension);
//EigenSolverArpack(int dimension);
//initialize_arpack(); // allocate memory and sets variables
double * calculate_eigen_space();
- int mul_matrix_vector(int dimension, double *vec, double * result);
+ //int mul_matrix_vector(int dimension, double *vec, double * result);
~EigenSolverArpack();
};
Added: branches/soc-2011-avocado/blender/intern/autoseam/SparseMatrix.h
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/SparseMatrix.h (rev 0)
+++ branches/soc-2011-avocado/blender/intern/autoseam/SparseMatrix.h 2011-07-31 06:38:23 UTC (rev 38873)
@@ -0,0 +1,112 @@
+#ifndef _SPARSE_MATRIX_H
+#define _SPARSE_MATRIX_H
+
+#include <cstdlib>
+#include <map>
+#include <vector>
+#include <iostream>
+
+/**
+ * This class is based on compressed row storage(CRS) format.
+ * More info can be found at http://web.eecs.utk.edu/~dongarra/etemplates/node373.html
+ */
+
+template <class T>
+class SparseMatrix
+{
+public:
+ typedef std::map<size_t, std::map<size_t , T> > mat_t;
+ typedef typename mat_t::iterator row_iter;
+ typedef std::map<size_t, T> col_t;
+ typedef typename col_t::iterator col_iter;
+
+ SparseMatrix(){};
+ SparseMatrix(size_t i){ m=i; n=i; }
+ SparseMatrix(size_t i, size_t j){ m=i; n=j; }
+
+ inline
+ T& operator()(size_t i, size_t j)
+ {
+ if(i>=m || j>=n) throw;
+ return mat[i][j];
+ }
+ inline
+ T operator()(size_t i, size_t j) const
+ {
+ if(i>=m || j>=n) throw;
+ return mat[i][j];
+ }
+
+ /**
+ * Multiplies vector x with matrix m and returns
+ * the result as a vector.
+ */
+ std::vector<T> operator*(const std::vector<T>& x)
+ {
+ if(this->m != x.size()) throw;
+
+ std::vector<T> y(this->m);
+ T sum;
+
+ row_iter ii;
+ col_iter jj;
+
+ for(ii=this->mat.begin(); ii!=this->mat.end(); ii++){
+ sum=0;
+ for(jj=(*ii).second.begin(); jj!=(*ii).second.end(); jj++){
+ sum += (*jj).second * x[(*jj).first];
+ }
+ y[(*ii).first]=sum;
+ }
+
+ return y;
+ }
+
+ /**
+ * Multiplies input_vector of length dimension with matrix m and stores
+ * it in result. Both the input_vector and the result need to be a valid
+ * pointer of type T
+ */
+ void mul_matrix_vector(int dimension, T *input_vector, T * result)
+ {
+ if(this->m != dimension) throw;
+
+ T sum;
+
+ row_iter ii;
+ col_iter jj;
+
+ for(ii=this->mat.begin(); ii!=this->mat.end(); ii++){
+ sum=0;
+ for(jj=(*ii).second.begin(); jj!=(*ii).second.end(); jj++){
+ sum += (*jj).second * input_vector[(*jj).first];
+ }
+ result[(*ii).first]=sum;
+ }
+
+ }
+
+ /**
+ * Displays the sparse matrix.
+ */
+ void print_sparse_matrix()
+ {
+ row_iter ii;
+ col_iter jj;
+ for(ii=this->mat.begin(); ii!=this->mat.end(); ii++){
+ for( jj=(*ii).second.begin(); jj!=(*ii).second.end(); jj++){
+ std::cout << (*ii).first << ' ';
+ std::cout << (*jj).first << ' ';
+ std::cout << (*jj).second << std::endl;
+ }
+ } std::cout << std::endl;
+ }
+
+
+private:
+ mat_t mat;
+ size_t m;
+ size_t n;
+};
+
+#endif /* _MATRIX_H */
\ No newline at end of file
More information about the Bf-blender-cvs
mailing list