CODEWITHSUNDEEP
c++eigen
Abolfazl
Abolfazl

Reputation: 1227

Efficient way to find maximum value of Sparse matrix (Eigen)

I was wondering whether it is possible to find the max/min coefficients in a sparse matrix in an efficient way.

It seems that the minCoeff()/maxCoeff() functions are not implemented for sparse matrices, which is a bit weird.

I found this answer here, but I could not figure it out.

 using Tmp = typename remove_cv_ref<decltype(matrix)>::type;
 if constexpr(std::is_base_of<Eigen::SparseMatrixBase<Tmp>, Tmp>::value)
 max = Eigen::Map<const Vector>(matrix.valuePtr(), matrix.size()).maxCoeff();
 else
    max = matrix.maxCoeff();

Edit: This is my try, I am not sure about the efficiency.

typedef Eigen::SparseMatrix<int, Eigen::RowMajor> SRI;
int maxCoeff(const SparseMatrix<int, RowMajor> &A)
{
    size_t row = A.rows();
    size_t col = A.cols();
    int max_value = -10000000;
    for (size_t k = 0; k < row; k++)
    {
        for (SRI::InnerIterator it(A, k); it; ++it)
        {
            if (it.value() > max_value)
                max_value = it.value();
        }
    }
    return max_value;
}

Upvotes: 5

Views: 3629

Answers (2)

RHertel
RHertel

Reputation: 23788

Try this templated function to obtain the maximum non-zero value of an Eigen::SparseMatrix:

template <class T>
T sparseMax (SparseMatrix<T>& mat) { 
  return Map<Matrix<T, Dynamic, 1> >(mat.valuePtr(), mat.nonZeros()).maxCoeff();
}

The principle here consists in mapping the non-zero elements of the sparse matrix onto a vector (a one-dimensional Eigen::Matrix) from which the maximum is then extracted with .maxCoeff(). This should be a very efficient means to determine the maximum value in the matrix. Note that the matrix needs to be compressed for this method to work.

In the code, the function sparseMax() could be called like this:

if (!mat.isCompressed()) mat.makeCompressed();
auto max = sparseMax(mat);

where mat is an Eigen::SparseMatrix.

The answer in the link is thus almost correct, but.size() should be replaced with .nonZeros() and it failed to ensure that the matrix is compressed. If you know that you are dealing with a SparseMatrix the if/else construction mentioned in the linked answer is not needed.

Edit

The above solution works for a SparseMatrix with the default column major storage order. In the case of RowMajor storage one could change the template to

template <class T>
 T sparseMax_RM (SparseMatrix<T,RowMajor>& mat) { 
 return Map<Matrix<T, Dynamic, 1> >(mat.valuePtr(), mat.nonZeros()).maxCoeff();
}

A more robust way is to use the member function .coeffs() instead, as pointed out by @ggael. The .coeffs() function works for compressed SparseMatrix classes of both types, RowMajor and ColMajor storage order.

Upvotes: 3

ggael
ggael

Reputation: 29205

Those functions are not readily available because it might be ambiguous whether the implicit zeros should be taken into account or not. For instance, if all non-zeros are negative, shall maxCoeff returns 0?

If you want to consider explicitly stored elements only and that your sparse matrix in is compressed mode, then you can write:

auto max = matrix.coeffs().maxCoeff();

The coeff method is equivalent to RHertel's answer.

Upvotes: 9

Related Questions