[feature][SeqILU] faster implementation of ILU preconditioner

This MR implements a faster ILU version by simply using Compressed Row Storage for the lower and upper triangular matrices. This way the access for the upper triangular can be done forwards in memory.

Also, the new class SeqILU unifies both, SeqILU0 and SeqILUn.

assigned to @markus.blatt

I forgot to mention that the new ILU implementation is between 10% and 20% faster then the existing ones.

Any objections of merging this?

The patch does not change any of the existing preconditioners.

Cool, thanks for improving this part of ISTL.

Would you mind extending the documentation to mention the CRS there as well? And maybe the name could contain a Crs, too. Dune::SeqILU is not distingable from Dune::SeqILU0 when reading foreign code.

I do not want this to be merged as is because it doubles the memory consumption of the ILU preconditioner. This might come as quite a surprise to some users.

We should do this improvement properly, that is without setting up an additional matrix and copying the decomposition to it.

@markus.blatt This is not true. It uses the same memory plus some overhead that can be adjusted.

The matrix is only temporary, and in addition, it does not change the exiting implementations. So where is the surprise?

@markus.blatt The memory consumption is only temporarily higher. The overall consumption during application of the preconditioner should be similar. That could also be included as a dynamic switch to allow for both versions. An implementation using less memory during the transition (i.e. reused some memory of the matrix ILU) would be quite an effort and might be hacky, e.g. reusing the storage of ILU in a different way. So I'm not so convinced that this is worthwile.

Does this change your argument?

added 1 commit

• 2a82fa64 - [cleanup] Allow SeqILU to use old and new storage format, old being the

Compare with previous version

@markus.blatt: I have now implemented the SeqILU such that both implementations can be used, the current one being the default option. From my point of view this could be merged now.

Does the new version also maintain the old order when solving Ux=y? Will give it a spin.

added 26 commits

• 2a82fa64...b3e7fc90 - 24 commits from branch master
• be38b8de - [feature][SeqILU] faster implementation of ILU preconditioners using a
• cdfebf9c - [cleanup] Allow SeqILU to use old and new storage format, old being the

Compare with previous version

added 3 commits

• ede82b79 - [cleanup] remove warnings of uninitialized variables.
• 828b7ac1 - Merge branch 'feature/remove-warnings' into feature/faster-ilu-implementation
• d1e67754 - [cleanup] Use nonzeroes for estimation of memory consumption.

Compare with previous version

@markus.blatt: I have addressed your concerns. The setup now uses the reverse iterators to keep the exact order of the matrices. Also, for memory estimation the non zeros are used, which should work here since the bug with non zeros being 0 even for a matrix setup correctly is fixed I guess.

added 1 commit

• 8d53d312 - [cleanup] adjust SeqILU to recent updates for SimdScalar.

Compare with previous version

added 1 commit

• 7e9942d4 - [cleanup] nonzeros --> nonzeroes (arrrgggghhh).

Compare with previous version

changed milestone to %DUNE 2.6.0

resolved all discussions

mentioned in commit 09cecfde

merged

Merged, thanks. Concerning the backport tag. I tried to cherry-pick manually but it seems a bit too involved for me and I soon gave up. There have been a lot of changes to the category stuff in master which seem to bite us here. Maybe it would have been easier if the unification would have been skipped. But this is a pure guess.

Thanks. Then backport to 2.5 would be good, for example, for the use in OPM. I can make a branch that takes care of this.

Great.