<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Aug 12, 2010, at 4:17 PM, Matthew Knepley wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">On Thu, Aug 12, 2010 at 4:10 PM, Barry Smith <span dir="ltr"><<a href="mailto:bsmith@mcs.anl.gov">bsmith@mcs.anl.gov</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div style="word-wrap:break-word"><div><br></div> It claims "permute the matrix such that sparse matrix-vector multiplication</div></blockquote><div><br></div><div>Does anyone understand what this means? I understand cache-oblivious divide&conquer</div> <div>where you just keep splitting until you are in cache (the original paper by Harald), but</div><div>what is meant here?</div><div><br></div></div></blockquote><div><br></div><div>I'm sure that your interpretation is correct Matt. I don't recall the people that coined this phrase but as I recall you keep splitting forever, in theory, to be truly cache oblivious. In practice you generally have some idea of how far down you want to block and stop before you get to individual equations.</div><div><br></div><div>Mark</div><div><br></div><br><blockquote type="cite"><div class="gmail_quote"><div> Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div style="word-wrap:break-word"><blockquote type="cite"><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex"> <div style="word-wrap:break-word"><div> is cache-oblivious," this would be a great feature to have it worked.</div></div></blockquote></div></div></blockquote><div><br></div><font color="#888888"> Barry</font><div> <div></div><div class="h5"><div><br><br><div><div>On Aug 12, 2010, at 3:07 PM, Matthew Knepley wrote:</div><br><blockquote type="cite">Prob will not help that much over Metis for MatMult, but fill-reducing orderings<div>might be a big win for LU.</div> <div><br></div><div> Matt<br><br><div class="gmail_quote">On Thu, Aug 12, 2010 at 1:38 PM, Barry Smith <span dir="ltr"><<a href="mailto:bsmith@mcs.anl.gov" target="_blank">bsmith@mcs.anl.gov</a>></span> wrote:<br> <blockquote class="gmail_quote" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word"> <div><br></div><div>From: Bas Fagginger Auer <<a href="mailto:B.O.FaggingerAuer@uu.nl" target="_blank">B.O.FaggingerAuer@uu.nl</a>><br> Date: Wed, 4 Aug 2010 15:02:44 +0200<br>Subject: Mondriaan 3.0 : Sparse Matrix Partitioning Package<br><br>Mondriaan 3.0: Sparse matrix partitioning package<br><br>We would like to announce the availability of version 3.0 of the<br> Mondriaan package. Mondriaan can be used as a preprocessing tool<br>for large sparse matrix-vector multiplications. It subdivides the<br>nonzeros of the matrix into a desired number of parts and generates<br>a permutation of the matrix based on this subdivision.<br> This subdivision and permutation can be used to<br>* minimise communication for sparse matrix-vector multiplication<br> when the matrix is distributed among nodes of a large parallel<br> system,<br>* permute the matrix such that sparse matrix-vector multiplication<br> is cache-oblivious,<br>* permute the matrix to reduce fill-in during LU decomposition.<br><br>Features of version 3.0:<br>* algorithms to permute the matrix to Separated Block Diagonal<br> or Bordered Block Diagonal form,<br> * improved finegrain quality,<br>* inclusion of the cut-net metric,<br>* Matlab and PaToH interfaces,<br>* visualisation of the partitioning process,<br>* Mondriaan is built as a separate library,<br> facilitating inclusion in existing programs,<br> * extensive documentation with examples and unit tests.<br><br>The package and related documentation can be obtained from:<br><a href="http://www.staff.science.uu.nl/~bisse101/Mondriaan/" target="_blank">http://www.staff.science.uu.nl/~bisse101/Mondriaan/</a><br> <br>Mondriaan is written in C and distributed under the GNU LGPL license.<br><br>Rob Bisseling, Bas Fagginger Auer, Albert-Jan Yzelman<br>Dept. Mathematics<br>Utrecht University<br><a href="http://www.staff.science.uu.nl/~bisse101/" target="_blank">http://www.staff.science.uu.nl/~bisse101/</a><br> </div><div><br></div></div></blockquote></div><br><br clear="all"><br>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br> -- Norbert Wiener<br> </div> </blockquote></div><br></div></div></div></div></blockquote></div><br><br clear="all"><br>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br> -- Norbert Wiener<br></blockquote></div><br></body></html>