SparseMatrix2D Class Reference

#include <sparse_matrix2d.h>

Collaboration diagram for SparseMatrix2D:

Public Member Functions
int	nrows () const
	Y size of the matrix. More...
int	ncols () const
	X size of the matrix. More...
	SparseMatrix2D (std::vector< SparseElement > &_elements, int _Nelements)
void	sparseMatrix2DFromVector (std::vector< SparseElement > &_elements)
	Fill the sparse matrix A with the elements of the vector. More...
void	multMv (double *x, double *y)
void	multMM (const SparseMatrix2D &X, SparseMatrix2D &Y)
	Computes Y=this*X. More...
void	multMMDiagonal (const MultidimArray< double > &D, SparseMatrix2D &Y)
	Computes y=SparseMatrixThis*SparseMatrix. More...
double	getElemIJ (int row, int col) const
void	loadMatrix (const FileName &fn)

Public Attributes
int	N =0
	The matrix is of size NxN. More...
MultidimArray< int >	iIdx
	List of i positions. More...
MultidimArray< int >	jIdx
	List of j positions. More...
MultidimArray< double >	values
	List of values. More...

Friends
std::ostream &	operator<< (std::ostream &out, const SparseMatrix2D &X)
	Shows the dense Matrix associated. More...

Detailed Description

Square, sparse matrices.

To create a Sparse Matrix we need a vector with SparseElements that contains a value, its row position and its column position.

We store that information with a Compressed Row Storage (CRS). This method stores a vector with the non-zero values (values), their column position (jIdx) and another vector with the position on values's vector of the element which is the first non-zero elements of each row (iIdx). The value 0 on iIdx vector means that there aren't nonzero values in that row. iIdx and jIdx have the first element in position 1. Value 0 is for no elements on a row.

i.e.:

Vector values 4, 3, 1, 2, 1, 4, 3

Vector jIdX 1, 2, 1, 2, 2, 4, 4

Vector iIdx 1, 3, 5, 7

Matriz A: 4 3 0 0 1 2 0 0 0 1 0 4 0 0 0 3

Definition at line 80 of file sparse_matrix2d.h.

Constructor & Destructor Documentation

SparseMatrix2D()

SparseMatrix2D::SparseMatrix2D	(	std::vector< SparseElement > &	_elements,
		int	_Nelements
	)

Constructor from a set of i,j indexes and their corresponding values. N is the total dimension of the square, sparse matrix.

Definition at line 32 of file sparse_matrix2d.cpp.

{
    //First of all, we sort the elements by rows and then by columns
    std::sort(_elements.begin(),_elements.end());

    size_t ln = _elements.size();
    N      = _Nelements;

    values.resizeNoCopy(ln);
    jIdx.resizeNoCopy(ln);
    iIdx.resizeNoCopy(N);

    int actualRow = -1;
    int i         =  0; // Iterator for the vectors "values" and "jIdx"

    for (size_t k=0 ; k< ln ; ++k )// Iterator for vector of SparseElemets
    {
        if(_elements.at(k).value != 0.0) // Searching that there isn't any zero value
        {
            DIRECT_MULTIDIM_ELEM(values,i) = _elements.at(k).value;
            DIRECT_MULTIDIM_ELEM(jIdx,i)   = _elements.at(k).j +1;

            int rse = _elements.at(k).i;
            while( rse > actualRow )
            {
                actualRow++;
                if( rse == actualRow )
                    // The first element in row number "x" is in position iIdx(x-1)
                    DIRECT_MULTIDIM_ELEM(iIdx,actualRow) = i+1;

                else
                    // If there isn't any nonzero value on this row, the value in this vector is 0
                    DIRECT_MULTIDIM_ELEM(iIdx,actualRow) = 0;
            }
            ++i;
        }
    }
}

Member Function Documentation

getElemIJ()

double SparseMatrix2D::getElemIJ	(	int	row,
		int	col
	)		const

Returns the value on position (row,col). The matrix goes from 0 to N-1

Get element

Definition at line 157 of file sparse_matrix2d.cpp.

{
    int rowBeg = DIRECT_MULTIDIM_ELEM(iIdx,row) -1;
    int rowEnd;

    if( row != N-1 )
        rowEnd = DIRECT_MULTIDIM_ELEM(iIdx,row+1) -1;
    else
        rowEnd = XSIZE(values);

    // If there is a non-zero element, the column is in jIdx
    for(int i = rowBeg; i < rowEnd ; i++)
        if( DIRECT_MULTIDIM_ELEM(jIdx,i)-1 == col )
            return DIRECT_MULTIDIM_ELEM(values,i);
    return 0.0;
}

loadMatrix()

void SparseMatrix2D::loadMatrix

(

const FileName &

fn

)

Loads a sparse matrix from a file. Loads a SparseMatrix2D from a file which has the following format:

sizeOfMatrix 1 1 value 2 1 value . . . i j value . . . last_i last_j last_value

Definition at line 258 of file sparse_matrix2d.cpp.

{
    std::ifstream fhIn;
    fhIn.open(fn.c_str());
    if (!fhIn)
       REPORT_ERROR(ERR_IO_NOTEXIST,fn);

    double dobVecSize, auxDob;
    int vectorSize = 0;
    fhIn >> dobVecSize;
    vectorSize = (int)dobVecSize ;

    std::vector<SparseElement> elems(vectorSize);
    for(int i =0; i< vectorSize; ++i){
        fhIn >> auxDob;
        elems.at(i).i = (int) auxDob -1;

        fhIn >> auxDob;
        elems.at(i).j = (int) auxDob -1;

        fhIn >> elems.at(i).value;
    }
    sparseMatrix2DFromVector(elems);
}

multMM()

void SparseMatrix2D::multMM	(	const SparseMatrix2D &	X,
		SparseMatrix2D &	Y
	)

Computes Y=this*X.

Computes y=SparseMatrixThis*SparseMatrixX.

Definition at line 175 of file sparse_matrix2d.cpp.

{
    size_t nnz=XSIZE(X.values);

    Y.N = X.N;
    Y.values.initZeros(nnz);
    Y.jIdx.initZeros(nnz);
    Y.iIdx.initZeros(N);

    size_t nnzY = 0;
    int Nelems  = X.N;
    for(int row = 0; row < Nelems ; ++row){
        int firstElemRow = 0;
        for(int col = 0; col < Nelems ; ++col){
            double aij = 0.0;
            for(int k = 0; k < Nelems ; ++k ){
                double val=getElemIJ(row, k);
                if(val != 0.0){ // If GetElemIJ(row, k) is 0, the product is 0.
                    double val2=X.getElemIJ(k,col);
                    aij += val * val2;
                }
            }

            if(aij != 0.0){ // If there is a nonzero element in (row,col) position, we include that in the matrix
                if(firstElemRow == 0)
                    firstElemRow = nnzY +1;
                DIRECT_MULTIDIM_ELEM(Y.values,nnzY) = aij;
                DIRECT_MULTIDIM_ELEM(Y.jIdx,nnzY)   = col+1;
                ++nnzY;
            }
        }
        // Indicates where is the first element of the row
        DIRECT_MULTIDIM_ELEM(Y.iIdx,row) = firstElemRow;
    }
    Y.values.resize(nnzY);
    Y.jIdx.resize(nnzY);
}

multMMDiagonal()

void SparseMatrix2D::multMMDiagonal	(	const MultidimArray< double > &	D,
		SparseMatrix2D &	Y
	)

Computes y=SparseMatrixThis*SparseMatrix.

Computes Y=this*D where D is a diagonal matrix. It is assumed that the size of this sparse matrix is NxN and that the length of y is N.

Definition at line 227 of file sparse_matrix2d.cpp.

{
    int actualRow = N-1;

    Y=*this;

    // We see where is the first element in the next row
    int until = DIRECT_MULTIDIM_ELEM(iIdx,actualRow) -1;

    // Obtain the value that we have to multiply by the first row.
    double dx = DIRECT_MULTIDIM_ELEM(D,actualRow);
    size_t nnz=XSIZE(values);
    for(int i = nnz-1; i >= 0 ; --i)
    {
        // Yij = Aij * Dii / Y = A => Yij = Yij * Dii
        DIRECT_MULTIDIM_ELEM(Y.values,i) *= dx;

        if(until == i && i > 0){
            --actualRow;
            // Search for a row with nonzero elements
            while( DIRECT_MULTIDIM_ELEM(iIdx,actualRow) == 0 )
                --actualRow;

            until = DIRECT_MULTIDIM_ELEM(iIdx,actualRow) -1;
            dx    = DIRECT_MULTIDIM_ELEM(D,actualRow);
        }
    }
}

multMv()

void SparseMatrix2D::multMv	(	double *	x,
		double *	y
	)

Computes y=this*x y and x are vectors of size Nx1

It computes y <- this*x

Definition at line 113 of file sparse_matrix2d.cpp.

{
    int col, rowEnd, rowBeg;
    double val;
    memset(y,0,N*sizeof(double));

    size_t nnz=XSIZE(values);
    for(int i = 0; i< N; i++)
    {
        // We get the gap where are the elements of the row i in value's vector
        rowBeg = DIRECT_MULTIDIM_ELEM(iIdx,i) -1;
        if( i != N-1 )
            rowEnd = DIRECT_MULTIDIM_ELEM(iIdx,i+1) -1;
        else
            rowEnd = nnz;

        val = 0.0;
        for(int j = rowBeg; j < rowEnd ; j++)
        {
            col = DIRECT_MULTIDIM_ELEM(jIdx,j) -1;// Column with a nonzero element in this row of the matrix
            val += DIRECT_MULTIDIM_ELEM(values,j) * x[col];
        }
        y[i] = val;
    }
}

ncols()

int SparseMatrix2D::ncols ( ) const

inline

X size of the matrix.

Definition at line 100 of file sparse_matrix2d.h.

    {
        return N;
    }

nrows()

int SparseMatrix2D::nrows ( ) const

inline

Y size of the matrix.

Definition at line 94 of file sparse_matrix2d.h.

    {
        return N;
    }

sparseMatrix2DFromVector()

void SparseMatrix2D::sparseMatrix2DFromVector

(

std::vector< SparseElement > &

_elements

)

Fill the sparse matrix A with the elements of the vector.

Definition at line 74 of file sparse_matrix2d.cpp.

{
    std::sort(_elements.begin(),_elements.end());

    size_t ln = _elements.size();
    N = _elements.at(ln-1).j;
    values.resizeNoCopy(ln);
    jIdx.resizeNoCopy(ln);
    iIdx.resizeNoCopy(N);

    int actualRow = -1;
    int i         =  0;

    for (size_t k=0 ; k< ln ; ++k )
    {
        if(_elements.at(k).value != 0.0) // Seaching that there isn't any zero value
        {
            DIRECT_MULTIDIM_ELEM(values,i) = _elements.at(k).value;
            DIRECT_MULTIDIM_ELEM(jIdx,i)   = _elements.at(k).j +1;

            int rse = _elements.at(k).i;
            while( rse > actualRow )
            {
                actualRow++;
                if( rse == actualRow )
                    DIRECT_MULTIDIM_ELEM(iIdx,actualRow) = i+1;

                else
                    DIRECT_MULTIDIM_ELEM(iIdx,actualRow) = 0;
            }
            ++i;
        }
    }
    N = actualRow+1;
}

Friends And Related Function Documentation

operator<<

std::ostream& operator<< ( std::ostream &  out, const SparseMatrix2D &  X  )

friend

Shows the dense Matrix associated.

Definition at line 142 of file sparse_matrix2d.cpp.

{
    int N=X.nrows();
    for(int i =0 ; i< N ; i++)
    {
        for(int j =0; j<N ; j++)
            out << X.getElemIJ(i, j) << "\t";
        out << std::endl;
    }
    return out;
}

Member Data Documentation

iIdx

MultidimArray<int> SparseMatrix2D::iIdx

List of i positions.

Definition at line 87 of file sparse_matrix2d.h.

jIdx

MultidimArray<int> SparseMatrix2D::jIdx

List of j positions.

Definition at line 89 of file sparse_matrix2d.h.

N

int SparseMatrix2D::N =0

The matrix is of size NxN.

Definition at line 84 of file sparse_matrix2d.h.

values

MultidimArray<double> SparseMatrix2D::values

List of values.

Definition at line 91 of file sparse_matrix2d.h.

---

The documentation for this class was generated from the following files:

• xmipp/libraries/data/sparse_matrix2d.h
• xmipp/libraries/data/sparse_matrix2d.cpp