[Insight-developers] Replacing Sparse Matrix Linear Solver : due to Licensing issues

Mon Feb 1 16:08:42 EST 2010

Hi Luis,

Great idea to start a wiki page! I'll edit it!

Do you want to restrict this page to sparse linear solvers? What about 
sparse eigen decomposition?

Sparse direct solver usually starts by reordering the matrix, then 
factorization (decomposition) part follows, and finally if you are 
willing to the linear system is solved.
The reordering part is often performed by using METIS library 
(http://glaros.dtc.umn.edu/gkhome/views/metis).
The license of the latest version 
(http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/metis-5.0pre2.tar.gz) 
states:

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.

---------------------------------------------------

An usual set up for taucs require metis, and link against metis...

So, we should first check with people from TAUCS if metis is really 
required?
(If we could skip the reordering part at the cost of lower performances).

And if it can not be optionally replaced by boost-BGL reordering 
algorithms  
(http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/table_of_contents.html), 
or by another library BSD compliant?

Arnaud

On 02/01/2010 03:29 PM, Luis Ibanez wrote:
> Hi Arnaud,
>
> Thanks a lot , all these suggestions are very useful.
>
> A) I'll give it a shot at using vnl_sparse_lu
>
>      (I must first double check that is not encumbered
>       by the ACM copyright/license absurd restrictions).
>
>
> B)  About the alternative libraries:
>       Thanks for gathering this list.
>
> B.1)  SuiteSparse,
>           since it is a LGPL libraries, is not an option.
>           at least not for being a default ITK component.
>           We could however, support it the way we support FFTW.
>          An pass the licensing nightmare down to the users who
>          enable that option.
>
> B.2)  TAUCS,
>           Looks like a good option.
>           The MIT license is fully compatible with BSD.
>
> B.3)  SuperLU,
>           Reading its license, it turns out to be a standard BSD.
>           So, this is also a good option.
>
> It looks like we should bring this discussion to the Wiki,
>
> I made a page for it at:
> http://www.itk.org/Wiki/Proposals:Sparse_Linear_Solvers
>
>
> That is linked from the 2010 Proposals Table:
> http://www.itk.org/Wiki/ITK_Oversight_Committee#2010
>
>
> Let's gather more factors in the Wiki, so we can make
> an educated decision.
>
>
>       Thanks,
>
>
>           Luis
>
>
> ------------------------------------------------------------------------------
> On Sun, Jan 31, 2010 at 4:28 PM, Arnaud Gelas
> <arnaud_gelas at hms.harvard.edu>  wrote:
>    
>> Hi Luis,
>> A short term solution would be to replace (if that possible) the code for
>> solving sparse linear system with existing sparse direct solution from VNL
>> (vnl_sparse_lu). Note that the mesh parameterization can easily change to
>> use vnl_sparse_lu by default.
>> Is vnl_sparse_lu  ok (in terms of license)?
>> Can Code/Numerics/FEM/itkFEMLinearSystemWrapperVNL.h use vnl_sparse_lu
>> instead?
>> A longer term solution would be to start using specialized sparse libraries
>> (which are more efficient than vnl for these problems). Here, I cite some of
>> them
>>   * SuiteSparse (LGPL): the most complete (and as far as I know the most
>> efficient) solution http://www.cise.ufl.edu/research/sparse/SuiteSparse/
>>   * TAUCS (MIT License): sparse direct solver http://code.google.com/p/taucs/
>>   * SuperLU (License): LU decomposition http://crd.lbl.gov/~xiaoye/SuperLU/
>> Arnaud
>> On Jan 31, 2010, at 2:50 PM, Luis Ibanez wrote:
>>
>> The "toms" incident seems to be behind us now.
>> The code has been removed from the VXL version
>> that is carried by ITK.
>>
>>
>> However, as a secondary effect,
>>
>> Bill found out that the "lsqr" libraries inside VXL are
>> also copyrighted by ACM and therefore subject to
>> their non-commercial license.
>>
>>
>>           Therefore,    they must go.
>>
>>
>> As opposed to "toms", however, this code is actually
>> used in ITK.
>>
>> The lsqr code from the directory:
>>
>>     Utilities/vxl/v3p/netlib/linalg/lsqr.c
>>
>> is used by VXL in
>>
>>     Utilities/vxl/core/vnl/algo/vnl_lsqr.h
>>
>> that in turn is used by ITK in:
>>
>> Code/Numerics/FEM/itkFEMLinearSystemWrapperVNL.h
>> Testing/Code/Review/itkQuadEdgeMeshLinearParameterizationTest.cxx
>>
>> After a (non exhaustive) Google search for
>> open source implementations of sparse matrix
>> linear solvers with licenses compatible with
>> the BSD license.
>>
>> We end up with :
>>
>>      http://sourceforge.net/projects/sparse/files/
>>      http://sparse.sourceforge.net/index.html
>>
>>      "Sparse 1.4"
>>      by  Kenneth Kundert.
>>      that is distributed under BSD license.
>>
>>
>> It turned out that VXL already carries (a version)
>> of this library under:
>>
>>          Utilities/vxl/v3p/netlib/sparse
>>
>> Ironically,...
>> still under the Evil "netlib" label...
>>
>> (we will come back to that later...)
>>
>> ---
>>
>> We are currently experimenting with replacing
>> the vnl_lsqr solver with another one based on
>> the Sparse library.
>>
>> Given that this is an issue of copyright infringement,
>> we will have to do the replacement even if the new
>> library is not technically better than the lsqr one.
>>
>>
>> At this point, the only places where we anticipate
>> to see any effect is the FEM registration algorithm,
>> which is the only code in ITK that uses the FEM
>> solver classes.
>>
>>
>> If you have any experience with using the Sparse
>> library we will appreciate your advice and help.
>>
>>
>> If you are aware of any other options on Open
>> Source sparse matrix linear solvers, with BSD
>> compatible licenses, please let us know.
>>
>>
>>      Thanks
>>
>>
>>             Luis
>> _______________________________________________
>> Powered by www.kitware.com
>>
>> Visit other Kitware open-source projects at
>> http://www.kitware.com/opensource/opensource.html
>>
>> Kitware offers ITK Training Courses, for more information visit:
>> http://kitware.com/products/protraining.html
>>
>> Please keep messages on-topic and check the ITK FAQ at:
>> http://www.itk.org/Wiki/ITK_FAQ
>>
>> Follow this link to subscribe/unsubscribe:
>> http://www.itk.org/mailman/listinfo/insight-developers
>>
>>
>>      