[IPOL discuss] the problem with Eigen (and other embedded libraries)

Mon Nov 7 19:55:55 CET 2011

Maybe I am missing something: what is it about SVD computation that
has to do with the operating system?  It seems to me that a correct,
portable, and safe SVD implementation should be entirely possible.  On
top of that, the implementation should be reasonably efficient.
Easier said than done, of course, but an SVD implementation that
succeeded in all of this would be extremely valuable.

According to ALGLIB's page about SVD [1], most modern SVD algorithms
and particularly LAPACK's SVD are based on QR iteration, and there are
tricks to speed up the basic approach.  I guess that Eigen and CCMath
do something like this.

I can't really think of anything that would affect an SVD
implementation's portability.  If testing for NaNs matters, the code
should not assume that "isnan" is available, since this function is
guaranteed by C99 but not C++ [2].

Infinite loops can be avoided by setting a maximum iteration limit on
every loop, e.g., MATLAB sets a limit of 75 QR iterations in its "svd"
command [3]:

> If the limit of 75 QR step iterations is exhausted while seeking a singular
> value, this message appears:
>
> Solution will not converge.

[1] http://www.alglib.net/matrixops/general/svd.php
[2] http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.15
[3] http://www.mathworks.com/help/techdoc/ref/svd-singular-value-decomposition.html

Best,
Pascal

On Mon, Nov 7, 2011 at 03:44, Pierre Moulon <pmoulon at gmail.com> wrote:
> Hi,
>
> By default using or writing code let the possibility to have bug or
> instability.
> All library are subject to amelioration and bug fix.
> By looking to the last CCMath release we could see:
> "2.2.1
>  09 Nov 2001 18:15 Minor bugfixes
> Release Notes: A fix for a rare numerical instability in the singular value
> decomposition (SVD) code."
> So it's look like recent log from Eigen. All math library are subject to
> instability and rare bugs.
> I see that ccmath by default is not said compatible with windows.
> http://freecode.com/projects/ccmath => Operating Systems    POSIX Linux
> Using code is often a compromise between "portability and reliablility".
> So I think there is not easy solution.
> Lapack (not easy to use on windows for new programmer)
> Eigen (portable)
> CCmath (linux only)
> GSL (linux, not easy to use on windows)
> Like you said a possibility is to use the system version of Eigen and
> provide a default implementation for windows.
> I think IPOL code must be easy to compile and so provide a self contained
> tested solution is the best (in my opinion).
> Regards,
> Pierre
> PS:  And SVD on very small number often is discarded because a degenerate
> configuration have been found before by the programmer.
> And often the code provided for a submission have been tested on large
> dataset and so critical case could be detected and under control.
> When you look to all the project that use Eigen as main computational
> library we could consider it as stable.
> ROS, Google,  VcgLib, PointCloudLibrary ...
> And personally I never encounter instability.
> It could be a long debate, but it's important that anyone could provide it's
> point of view.
>
> 2011/11/5 Nicolas Limare <nicolas.limare at cmla.ens-cachan.fr>
>>
>> Hi all,
>>
>> I already wrote about the problems that can happen from embedded
>> libraries, with the libtiff example[1].
>>
>> [1] http://tools.ipol.im/wiki/author/code/embedding_vs_security/
>>
>> I had a look tonight at the Changelog for Eigen. Since version 3.0,
>> released March 19, 2011, there has been 3 minor updates. The changelog[2]
>> mentions the correction of various bugs.
>>
>> syntax and memory bugs
>> * Standard compliance: fix aligned_allocator and remove uses of long long.
>> * Fix memory leak issue for scalar types throwing exceptions.
>>
>> bugs related to some compilers
>> * Fix compilation on gcc 4.6
>> * Fix compilation with MSVC 2005
>> * Fix compilation issues with MinGW
>>
>> numerical bugs
>> * Fix bug in trapezoidal matrix time matrix product.
>> * Fix asin.
>> * Fix solve using LDLT for singular matrices if solution exists.
>> * Fix infinite loop when computing SVD of some matrices with very small
>> numbers
>>
>> [2] http://eigen.tuxfamily.org/index.php?title=ChangeLog
>>
>> This means that every software published in IPOL swith all the Eigen
>> library will have these bugs, forever. When you consider that Eigen
>> was used by some IPOL software for the SVD, and this SVD was buggy with
>> a chance of infinite loops, I think this clearly shows why including
>> the full code of an external library is a bad decision.
>>
>> If we accept Eigen in the list of external libraries allowed for IPOL
>> software (someone will have to explain why we must consider Eigen
>> portable, widely used and stable), then every IPOL software can
>> use Eigen ftom the system, and just #include <Eigen>. The version
>> installed on the system will be updated when new versions are
>> released, and will correct bugs.
>>
>> If we don't accept Eigen in the list of external libraries, and you
>> still don't want to use lapack, then I think simple stand-alone
>> implementations like ccmath/svdval[3] for the SVD are less likely to
>> need updates and corrections for specific compilers.
>>
>>
>> [3]http://dev.ipol.im/git/?p=coco/ccmath.git;a=blob;f=manual/C01-matrix#l708
>>
>> --
>> Nicolas LIMARE - CMLA - ENS Cachan
>>  http://www.cmla.ens-cachan.fr/~limare/
>> IPOL - image processing on line
>>  http://www.ipol.im/
>>
>> -----BEGIN PGP SIGNATURE-----
>> Version: GnuPG v1.4.10 (GNU/Linux)
>>
>> iEYEARECAAYFAk61qqYACgkQvviFAPpCP091JgCeO6q9kzD2rO5kJ/cIqkvgQgZ3
>> 5gAAoKrRx2+N4qjsxv4B3VX5L10YbMcu
>> =+ev9
>> -----END PGP SIGNATURE-----
>>
>> _______________________________________________
>> discuss mailing list
>> discuss at list.ipol.im
>> http://tools.ipol.im/mailman/listinfo/discuss
>
>
> _______________________________________________
> discuss mailing list
> discuss at list.ipol.im
> http://tools.ipol.im/mailman/listinfo/discuss
>