Timo, > As a remedy I created a new class called > CompressedSimpleSparsityPattern, that (in my cases) works better than > both alternatives. It's faster than the two (41s instead of one hour in > the above example)
That's fantastic! > For each line we keep a sorted std:vector<unsigned int> which is > dynamically growing (doubling its size on each allocation). The correct > position for new entries (and if it actually is a new entry) is found by > a binary search on the vector. I'm using no additional cache like > CompressedSparsityPattern. This is basically a CompressedSparsityPattern > with a lot less allocations (and copies) and no linear search over the > elements in a row. That *is* simple :-) Looking at this, it makes me wonder why I implemented the cache. I do remember not having it in the beginning, and implementing it because there were cases where it made the whole operation much (at least an order of magnitude) faster. Basically, my experience with these compressed sparsity patterns has been that there's always a testcase where one of them sucked, and you apparently have one where both of them suck. I would therefore not be opposed to having a third of these classes! > I'm first looking for some feedback and additional tests to check the > performance (in a comment there is a "random insertion test" mentioned). > I tested Q1 up to Q6 scalar and vector valued FEs for different > refinements and also tried a random reordering. I'm always using > doftools:make_sparsity_pattern(), but this is a typical usage "pattern" > i think. :-) Some tests regarding hp, adaptive refinement and > constraints could be useful. You may want to take a look at the page that describes our unit regression tests: http://www.dealii.org/developer/development/testsuite.html If you check out the tests, take a look at the tests in the lac/compressed_sparsity_pattern*cc lac/compressed_set_sparsity_pattern*cc groups. I bet that you can very easily adapt the compressed_sparsity_pattern tests by simply changing the file names. > So, should this go into deal.ii? Can it stay like this or should the > name be replaced? What do I need to change? Should it co-exist with the > two other variants? I think it would be great if you offered your class for deal.II! I would appreciate if you could take a look at updating the documentation of the new class where necessary (as well as doc/doxygen/headers/matrices.h, where it's probably sufficient if you just add the new class where all the other ones are listed). You should also edit doc/authors.html! If you could add unit tests, that would be great, but if it's too much work then I'd be happy to do that myself. > A few other things i noticed: > - SparsityPattern::copy_from() is copying the data twice and sorts the > rows even when they are already sorted (in all cases) You mean because it first copies the elements and then calls compress()? Yes, I believe this could be improved, but keep in mind that in those functions if m()==n() & optimize_diag, we allocate one additional entry so that we can make sure the diagonal entry exists. If it was already in the sparsity pattern we copy from, then we won't need the additional entry and compress() actually has to compress the sparsity pattern. I agree, though, that the function could be made more efficient -- I guess nobody cared so far because it never showed up in a profile of run times. > - a SparsityPattern before compress()'ing behaves somehow like a > CompressedSP with the only difference, that you have to supply a limit > on the number of entries per row. Maybe this could be unified? If you have good bounds on the number of nonzero entries, and if there are only few entries per row, SP uses a lot less memory than CompressedSP. That was the reason why we always retained its current behavior. Does that make sense? > - the names are misleading, "Compressed" should be called "Dynamic"? Yes, but changing names is not backward compatible and so is rather unpopular :-) > - a lot of code regarding CompressedSP and CompressedSetSP (and now also > for CompressedSimpleSP) is duplicated (gnuplot export ...) Right. Basically, all that's different is the Line structure. I've always meant to unify things into a base class and simply pass it a different Line implementation as a template parameter. I've just added a TODO mark to the compressed_sparsity_pattern.h file. > - the clearing of the cache in CompressedSP also does the whole > allocation-copy-swap work when the cache only contained duplicate > entries Aw, true. I've just added a simple fix for this problem. > and uses only up to twice the memory of the > CompressedSparsityPattern class (2.3gb instead of 1.8gb in the above > example). The doubled memory requirements needed while creating the > SparsityPattern is (in my opinion) no problem, because the system matrix > created later should be larger than the CompressedSimpleSparsityPattern, > which is already freed then. As an immaterial point (I don't want to take away from your patch, so I put this at the bottom): If you have a SparseMatrix<float>, then the matrix itself takes less memory than the SparsityPattern, and probably much less than the Compressed*SparsityPattern objects. So the memory consumption of these Compressed*SparsityPatterns do matter. I do agree, however, that your factor of 2 is really not an important point worth discussing. So, as I said, if you could take a look at the documentation and possibly the regression tests, this would make for a great addition to deal.II! Best Wolfgang ------------------------------------------------------------------------- Wolfgang Bangerth email: [EMAIL PROTECTED] www: http://www.math.tamu.edu/~bangerth/ _______________________________________________
