[Dune-devel] BCRSMatrix implicit build mode

[Dominic Kempf]

Hey Markus,

when I was implementing the build mode I had the original idea of keeping
the entries ordered per row to perform binary search exactly as I describe.
This has the obvious pro of fast search, biut it comes at the cost of moving
entries within the row upon insertion.

In the end, we started benchmarking which of the both effects has a stronger
impact on performance and it turned out to be the latter. After all, we are
treating
with sparse matrices and the total number of entries per row is too low to
really
profit from the logarithmic complexity of binary search.

Unfortunately, I do not remember how extensive we benchmarked it and I did
not store any
results, so I cannot tell you where to expect a breakeven point of the two
strategies.

Best,
Dominic

On Mon, Nov 30, 2015 at 11:53 AM, Markus Blatt <markus at dr-blatt.de> wrote:

> Hi,
>
> last week I was thinking: Wow, this build mode together with the
> ImplicitMatrixBuilder is really awesome and can be used to elegantly
> implement various ILU methods.
>
> Unfortunately, and as a bit of a surprise, the complexities of
> entry(row, col) and mat[row][col] are quite different. The first does
> a linear search while the latter does a binary one. If I recall
> correctly, then the original proposal was always keep the columns
> ordered and shift the higher entries by one place in case of
> insertion of a new value.
>
> What is the reason for the deviation from the original proposal? Did
> you do any timings (based on average nonzeros per row) when your or
> the original approach is more efficient?
>
> Cheers,
>
> Markus
> --
> Dr. Markus Blatt - HPC-Simulation-Software & Services
> http://www.dr-blatt.de
> Hans-Bunte-Str. 8-10, 69123 Heidelberg, Germany
> Tel.: +49 (0) 160 97590858
>
> _______________________________________________
> Dune-devel mailing list
> Dune-devel at dune-project.org
> http://lists.dune-project.org/mailman/listinfo/dune-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.dune-project.org/pipermail/dune-devel/attachments/20151130/34ec61cb/attachment.htm>