#132 computational complexity of BCRSMatrix::coldim()

Metadata

Property	Value
Reported by	unknown (unknown)
Reported at	May 22, 2006 12:06
Type	Bug Report
Version	Git (pre2.4) [autotools]
Operating System	Unspecified / All
Last edited by	Markus Blatt (markus@dr-blatt.de)
Last edited at	May 22, 2006 14:37
Closed by	Oliver Sander (oliver.sander@tu-dresden.de)
Closed at	May 23, 2006 10:04
Closed in version	Unknown
Resolution	Implemented
Comment	Implemented in a patch by Martin Weiser in revision 608

Description

The computational complexity of BCRSMatrix::coldim() is O(N()*nnz). This can be improved a lot to O(nnz) with a relatively small constant by the following alternative implementation of coldim():

size_type coldim () const
  {
    // The following original code has a complexity of
    // rowdim()*nnz, which is horribly slow for at least medium
    // sized FE matrixes...
    // 
    // size_type mm=0;
    // for (size_type i=0; i`<`m; i++)
    //       mm += coldim(i);	  
    // return mm;
    //
    // The following new code has a complexity of nnz, but
    // typically a very small constant.
    //
    std::vector<size_type> coldims(M(),-1);
    for (ConstRowIterator row=begin(); row!=end(); ++row) 
      for (ConstColIterator col=row->begin(), ; col!=row->end();++col)
        // only compute blocksizes we don't already have
        if (coldims[col.index()]==-1) 
          coldims[col.index()] = col->coldim();   
   assert(std::find(coldims.begin(),coldims.end(),-1)==coldims.end());
    return std::accumulate(coldims.begin(),coldims.end(),0);
  }

It is necessary to include and .

Martin Weiser