Unexpected behaviour of BCRSMatrix implict buildmode

The behaviour of the implicit build mode is in several ways unexpected and does not fit its documentation:

• (a) In contrast to the documentation, the allocated overflow area is not used while filling the matrix in favour of a separate std::map.
• (b) The allocated overflow area does always contain 4*avg more entries than expected.
• (c) The given avg value is not really related to average row sizes. If you give the exact average, compres() may fail if the overflow size is zero.
• (d) The allocated overflow area is in fact used to balance the mismatch between the given avg value and rows having more entries than this.
• (e) compress() may fail depending on the row order: The following will fail for row=0 but succeed for row=5

  using M = Dune::BCRSMatrix<Dune::FieldMatrix<double,1,1>>;
  M m(6, 6, 1, 0.0, M::implicit);
  for(std::size_t i=0; i<6; ++i)
    m.entry(row,i) = i;
  m.compress();

Explanation for this behaviour: When allocating storage, this is partitioned into the overflow area followed by avg reserved entries per row. When more than avg entries are used in a row, they are stored in an additional std::map. On compress() all entries are shifted forward towards the first free position, inserting intermediate entries from the overflow map when necessary. This explains, why early rows cannot have more than avg+overflow entries, while later ones may consume remaining space left by preceding less populated rows.

Due to (a) there is a possible fix for several of those problems. Before compressing forward with insertion of overflow entries, one can compress backwards without this insertion. This would solve (c)-(e) at the price of an additional shifting operation. Even more, this would allow to compute the number of non-zeros in the first sweep and than allocate new storage if the overflow was to small instead of throwing an exception and letting the user assemble all entries again with a hopefully better guess.