Re: [eigen] Complexity of setFromTriplets

[coryaden@xxxxxxxxxx]

But in the function 'set_from_triplets' in 'SparseCore\SparseMatrix.h' 
there is a call to function sumupDuplicates(). This initializes a vector 
of length innerSize() with the value -1 and iterates over j from 0 to 
outerSize()-1.
From a theoretical perspective, we need to set all k values of 'Index* 
m_outerIndex' at some point, while k is either number of rows or number 
of columns and independent on number of triplets we set. Thus, when 
storing the matrix in CRS format, it should be impossible to beat 
O(n+k).

This is a problem when setting only a constant number of triplets in a 
big SparseMatrix. Increasing the number of rows by a factor of c results 
in a higher execution time of setFromTriplets (by roughly the same 
factor c).

Am 2015-10-08 22:20, schrieb Nathan Yonkee:
> Cory,
>
> Simply setting the values is independent of the matrix size. If I set
> only the first element, that's only one set of operations, nothing is
> done on the rows or columns. Additionally, a matrix is sparse when n =
> O(r) with r being the longer dimension, so O(n) + O(r) + O(c) is still
> O(n). So for an algorithm like multigrid applied to a sparse matrix,
> the complexity is based on size (I think), but is still O(n) because
> every dimension is no greater than O(n).
>
> On Thu, 08 Oct 2015 12:39:56 +0200
> coryaden@xxxxxxxxxx wrote:
>
> > Hello,
> >
> > in the documentation of the class Eigen::SparseMatrix< _Scalar,
> > _Options, _Index > it is claimed that the function setFromTriplets was 
> > a
> > "O(n) operation, with n the number of triplet elements".
> > O(n) suggests that the matrix dimensions do not effect execution time,
> > which is wrong. It should be O(n+r+c), with n number of triplets and 
> > r,c
> > the number of rows and columns of the SparseMatrix<>.
> >
> > Cory Aden