Bug 715314 (metis) - Review Request: metis - A set of serial programs for partitioning graphs, partitioning finite element meshes, and producing fill reducing orderings for sparse matrices
Summary: Review Request: metis - A set of serial programs for partitioning graphs, par...
Keywords:
Status: CLOSED CANTFIX
Alias: metis
Product: Fedora
Classification: Fedora
Component: Package Review
Version: rawhide
Hardware: All
OS: Linux
medium
medium
Target Milestone: ---
Assignee: Nobody's working on this, feel free to take it
QA Contact: Fedora Extras Quality Assurance
URL:
Whiteboard:
Depends On:
Blocks: FE-Legal
TreeView+ depends on / blocked
 
Reported: 2011-06-22 14:24 UTC by Ankur Sinha (FranciscoD)
Modified: 2011-07-02 10:52 UTC (History)
4 users (show)

Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed: 2011-07-01 15:48:25 UTC
Type: ---
Embargoed:


Attachments (Terms of Use)

Description Ankur Sinha (FranciscoD) 2011-06-22 14:24:20 UTC
Spec URL: http://ankursinha.fedorapeople.org/metis/metis.spec
SRPM URL: http://ankursinha.fedorapeople.org/metis/metis-4.0.3-1.fc15.src.rpm
Description: 
METIS's key features are the following:

Provides high quality partitions!
Experiments on a large number of graphs arising in various domains 
including finite element methods, linear programming, VLSI, and 
transportation show that METIS produces partitions that are 
consistently better than those produced by other widely used 
algorithms. The partitions produced by METIS are consistently 
10% to 50% better than those produced by spectral partitioning 
algorithms.

It is extremely fast!
Experiments on a wide range of graphs has shown that METIS is one 
to two orders of magnitude faster than other widely used 
partitioning algorithms. Graphs with over 1,000,000 vertices can be 
partitioned in 256 parts in a few seconds on current generation 
workstations and PCs.

Produces low fill orderings!
The fill-reducing orderings produced by METIS are significantly 
better than those produced by other widely used algorithms 
including multiple minimum degree. For many classes of problems 
arising in scientific computations and linear programming, METIS 
is able to reduce the storage and computational requirements of 
sparse matrix factorization, by up to an order of magnitude. 
Moreover, unlike multiple minimum degree, the elimination trees 
produced by METIS are suitable for parallel direct factorization. 
Furthermore, METIS is able to compute these orderings very fast. 
Matrices with over 200,000 rows can be reordered in just a few 
seconds on current generation workstations and PCs.

Comment 1 Susi Lehtola 2011-06-27 13:56:42 UTC
LICENSE reads:

The METIS package is copyrighted by the Regents of the University of
Minnesota. It can be freely used for educational and research purposes 
by non-profit institutions and US government agencies only. Other 
organizations are allowed to use METIS only for evaluation purposes,
and any further uses will require prior approval. The software 
may not be sold or redistributed without prior approval. One may 
make copies of the software for their use provided that the copies, 
are not sold or distributed, are used under the same terms and 
conditions. 

This is clearly nonfree and unappropriate for Fedora.

Comment 2 Ankur Sinha (FranciscoD) 2011-06-30 18:25:13 UTC
I found this in the elmerfem metis package:

"Metis license:
--------------

* Copyright 1997, Regents of the University of Minnesota

Our policy regarding the distribution of METIS with third-party applications is as follows:

    *  Non-commercial applications
      METIS can be freely distributed provided that:
          o Proper references are included.
          o The original documentation and copyright notice is included.
    * Commercial applications
      METIS can be freely distributed provided that:
          o Proper references are included.
          o The original documentation and copyright notice is included.
          o METIS is a relatively small portion of the overall application.

"

I'll email upstream and request clarification before we proceed. 

Thanks,
Regards,
Ankur

Comment 3 Tom "spot" Callaway 2011-07-01 14:49:01 UTC
It still doesn't look like the licensing is Free here, but I'll wait to see what clarification comes from upstream.

Comment 4 Ankur Sinha (FranciscoD) 2011-07-01 15:48:25 UTC
(In reply to comment #3)
> It still doesn't look like the licensing is Free here, but I'll wait to see
> what clarification comes from upstream.

Here's the clarification(quoting):

"
Hi Ankur

Metis is used as the main strategy for mesh partitioning i.e. its relevant only for parallel computations. We have a historical OK from Metis developers to distribute it with Elmer. However, I understand that this does not make Metis free software. There is an alternative package, Scotch [1], which to my understanding provides similar functionality. It is used in the Debian build of Elmer. We should try to invest some time to test these packages and use perhaps it instead of Metis. As a quick solution I think that building ElmerGrid without Metis is OK. Just change the #define PARTMETIS in femelmer.h to zero and there is some alternative text printed in case Metis is called. 

Best regards,
Peter

[1] http://www.labri.fr/perso/pelegrin/scotch/
"

I'm going to go look at scotch. This one's a CANTFIX :/

Thanks all for the inputs :)

Regards,
Ankur

Comment 5 Ankur Sinha (FranciscoD) 2011-07-01 15:49:53 UTC
Oh! And I'm going to build elmergrid without elmer as upstream suggests for the time being. When scotch is ready, I'll rebuild elmergrid with it. 

Thanks,
Ankur


Note You need to log in before you can comment on or make changes to this bug.