<div dir="ltr"><div><div><div>Hey Markus,<br><br></div>when I was implementing the build mode I had the original idea of keeping<br></div>the entries ordered per row to perform binary search exactly as I describe.<br></div><div>This has the obvious pro of fast search, biut it comes at the cost of moving<br></div><div>entries within the row upon insertion.<br><br></div><div>In the end, we started benchmarking which of the both effects has a stronger<br></div><div>impact on performance and it turned out to be the latter. After all, we are treating<br></div><div>with sparse matrices and the total number of entries per row is too low to really<br></div><div>profit from the logarithmic complexity of binary search.<br><br></div><div>Unfortunately, I do not remember how extensive we benchmarked it and I did not store any<br></div><div>results, so I cannot tell you where to expect a breakeven point of the two strategies.<br><br></div><div>Best,<br></div><div>Dominic<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Nov 30, 2015 at 11:53 AM, Markus Blatt <span dir="ltr"><<a href="mailto:markus@dr-blatt.de" target="_blank">markus@dr-blatt.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
last week I was thinking: Wow, this build mode together with the<br>
ImplicitMatrixBuilder is really awesome and can be used to elegantly<br>
implement various ILU methods.<br>
<br>
Unfortunately, and as a bit of a surprise, the complexities of<br>
entry(row, col) and mat[row][col] are quite different. The first does<br>
a linear search while the latter does a binary one. If I recall<br>
correctly, then the original proposal was always keep the columns<br>
ordered and shift the higher entries by one place in case of<br>
insertion of a new value.<br>
<br>
What is the reason for the deviation from the original proposal? Did<br>
you do any timings (based on average nonzeros per row) when your or<br>
the original approach is more efficient?<br>
<br>
Cheers,<br>
<br>
Markus<br>
<span class="HOEnZb"><font color="#888888">--<br>
Dr. Markus Blatt - HPC-Simulation-Software & Services <a href="http://www.dr-blatt.de" rel="noreferrer" target="_blank">http://www.dr-blatt.de</a><br>
Hans-Bunte-Str. 8-10, 69123 Heidelberg, Germany<br>
Tel.: <a href="tel:%2B49%20%280%29%20160%2097590858" value="+4916097590858">+49 (0) 160 97590858</a><br>
</font></span><br>_______________________________________________<br>
Dune-devel mailing list<br>
<a href="mailto:Dune-devel@dune-project.org">Dune-devel@dune-project.org</a><br>
<a href="http://lists.dune-project.org/mailman/listinfo/dune-devel" rel="noreferrer" target="_blank">http://lists.dune-project.org/mailman/listinfo/dune-devel</a><br>
<br></blockquote></div><br></div>