[petsc-dev] something to consider adding to PETSc
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 divideconquer 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
[petsc-dev] something to consider adding to PETSc
From: Bas Fagginger Auer b.o.faggingera...@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/ -- next part -- An HTML attachment was scrubbed... URL: http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20100812/f6034825/attachment.html
[petsc-dev] something to consider adding to PETSc
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 -- next part -- An HTML attachment was scrubbed... URL: http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20100812/e7835e21/attachment.html
[petsc-dev] something to consider adding to PETSc
It claims permute the matrix such that sparse matrix-vector multiplication 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 -- next part -- An HTML attachment was scrubbed... URL: http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20100812/d3d1d7a4/attachment.html
[petsc-dev] something to consider adding to PETSc
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 divideconquer where you just keep splitting until you are in cache (the original paper by Harald), but what is meant here? 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/20100812/000486da/attachment.html