Bug 715314 (metis)

Summary: Review Request: metis - A set of serial programs for partitioning graphs, partitioning finite element meshes, and producing fill reducing orderings for sparse matrices
Product: [Fedora] Fedora Reporter: Ankur Sinha (FranciscoD) <sanjay.ankur>
Component: Package ReviewAssignee: Nobody's working on this, feel free to take it <nobody>
Status: CLOSED CANTFIX QA Contact: Fedora Extras Quality Assurance <extras-qa>
Severity: medium Docs Contact:
Priority: medium    
Version: rawhideCC: fedora-package-review, notting, susi.lehtola, tcallawa
Target Milestone: ---   
Target Release: ---   
Hardware: All   
OS: Linux   
Whiteboard:
Fixed In Version: Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of: Environment:
Last Closed: 2011-07-01 15:48:25 UTC Type: ---
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: --- Target Upstream Version:
Bug Depends On:    
Bug Blocks: 182235    

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