[petsc-dev] something to consider adding to PETSc

[Mark F. Adams]

On Aug 12, 2010, at 4:17 PM, Matthew Knepley wrote:

> On Thu, Aug 12, 2010 at 4:10 PM, Barry Smith <bsmith at mcs.anl.gov>  
> wrote:
>
>   It claims "permute the matrix such that sparse matrix-vector  
> multiplication
>
> Does anyone understand what this means? I understand cache-oblivious  
> divide&conquer
> where you just keep splitting until you are in cache (the original  
> paper by Harald), but
> what is meant here?
>

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.

Mark


>    Matt
>
>>   is cache-oblivious," this would be a great feature to have it  
>> worked.
>
>    Barry
>
>
> On Aug 12, 2010, at 3:07 PM, Matthew Knepley wrote:
>
>> Prob will not help that much over Metis for MatMult, but fill- 
>> reducing orderings
>> might be a big win for LU.
>>
>>    Matt
>>
>> On Thu, Aug 12, 2010 at 1:38 PM, Barry Smith <bsmith at mcs.anl.gov>  
>> wrote:
>>
>> From: Bas Fagginger Auer <B.O.FaggingerAuer at uu.nl>
>> Date: Wed, 4 Aug 2010 15:02:44 +0200
>> Subject: Mondriaan 3.0 : Sparse Matrix Partitioning Package
>>
>> Mondriaan 3.0: Sparse matrix partitioning package
>>
>> We would like to announce the availability of version 3.0 of the
>> Mondriaan package. Mondriaan can be used as a preprocessing tool
>> for large sparse matrix-vector multiplications. It subdivides the
>> nonzeros of the matrix into a desired number of parts and generates
>> a permutation of the matrix based on this subdivision.
>> This subdivision and permutation can be used to
>> * minimise communication for sparse matrix-vector multiplication
>>   when the matrix is distributed among nodes of a large parallel
>>   system,
>> * permute the matrix such that sparse matrix-vector multiplication
>>   is cache-oblivious,
>> * permute the matrix to reduce fill-in during LU decomposition.
>>
>> Features of version 3.0:
>> * algorithms to permute the matrix to Separated Block Diagonal
>>   or Bordered Block Diagonal form,
>> * improved finegrain quality,
>> * inclusion of the cut-net metric,
>> * Matlab and PaToH interfaces,
>> * visualisation of the partitioning process,
>> * Mondriaan is built as a separate library,
>>   facilitating inclusion in existing programs,
>> * extensive documentation with examples and unit tests.
>>
>> The package and related documentation can be obtained from:
>> http://www.staff.science.uu.nl/~bisse101/Mondriaan/
>>
>> Mondriaan is written in C and distributed under the GNU LGPL license.
>>
>> Rob Bisseling, Bas Fagginger Auer, Albert-Jan Yzelman
>> Dept. Mathematics
>> Utrecht University
>> http://www.staff.science.uu.nl/~bisse101/
>>
>>
>>
>>
>> -- 
>> What most experimenters take for granted before they begin their  
>> experiments is infinitely more interesting than any results to  
>> which their experiments lead.
>> -- Norbert Wiener
>
>
>
>
> -- 
> What most experimenters take for granted before they begin their  
> experiments is infinitely more interesting than any results to which  
> their experiments lead.
> -- Norbert Wiener

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20100813/655d8872/attachment.html>