bugGNU Octave - Bugs: bug #46683, Need better configure test for bad...

 
 

bug #46683: Need better configure test for bad ARPACK library

Submitter:  Avinoam Kalma <avinoam>
Submitted:  Mon 14 Dec 2015 07:44:56 PM UTC
   
 
Category:  Libraries Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Works For Me Assigned to:  caliari
Originator Name:  Avinoam Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Wed 05 Apr 2017 05:45:39 PM UTC, comment #25: 

Closing report.

Rik <rik5>
Group administrator
Wed 05 Apr 2017 02:34:31 PM UTC, comment #24: 

I cannot reproduce the bad behavior in comment #20 with 4.0.2 ore 4.3.0+. So, I would close this bug report.

Marco Caliari <caliari>
Group Member
Thu 04 Feb 2016 10:01:35 AM UTC, comment #23: 

My dndrv1.f has the same input values. So, the difference is after the call to dsaupd.

Marco Caliari <caliari>
Group Member
Tue 02 Feb 2016 10:15:23 PM UTC, comment #22: 

Marco, your interpretation in comment #20 seems correct.  I haven't checked what the Fortran code does, but the C++ code calls dsaupd with

ido 0
bmat I
n 12
typ LM
k 1
tol 2.22045e-16
p 11
ip 1 0 300 1 0 0 1 0 0 0 0

Lachlan Andrew <lachlan>
Wed 20 Jan 2016 09:34:13 AM UTC, comment #21: 

@Rik,

I have seen your message on the mailing list. I think that a proper, safe, not interfering with existing codes fix of the failed test is that suggested in comment #3. What is in comment #8 is for sure valid, but probably useless whenever (if ever) all the problems in eigs will be fixed. So, I'd propose to go with #3 in stable and #8 in default.

Marco Caliari <caliari>
Group Member
Tue 12 Jan 2016 09:26:02 AM UTC, comment #20: 

Here my first example that I cannot reproduce in plain fortran. The matrix is AA (taken from #31479), the initial vector opts.v0


A = [1,0,0,-1;0,1,0,0;0,0,1,0;0,0,2,1];
AA = sparse([A,zeros(4),zeros(4);zeros(4),A,zeros(4);zeros(4),zeros(4),A]);
opts.v0 = [0.239;0.420472;0.358959;0.6824;0.483916;0.312213;0.845595;0.298945;0.38219;0.595434;0.01263;0.66212];


and I use eigs(AA,1,'lm',opts). I get  1.0000e+00 - 2.8107e-06i (Octave 4.0.0, arpack 3.3.0). From line 296 in _eigs_.cc I understand have_sigma = false and then EigsRealNonSymmetricMatrix should be used (see line 584). In eigs_base.cc, line 1696, mode=1 (regular mode) and in line 1731, p=n-1=11. So, it should correspond to dndrv1.f (attached). But here the result has imaginary part exactly zero (as in Matlab, by the way).

(file #35998)

Marco Caliari <caliari>
Group Member
Sat 09 Jan 2016 03:43:51 PM UTC, comment #19: 

@Rik

Thanks Rik for joining the group ;-)

After my fisrt comment, I found that ARPACK > 3.1.5 already contains a test file for checking the bug. It is called bug-1315 (double and single version). I slightly modified it in order to use a fixed initial vector (resid). The bug is triggered by computing eigenvalues and eigenvectors of a diagonal matrix forcing ARPACK to treat it as nonsymmetric. Therefore, I presume Octave succeeds here. I checked ARPACK 3.1.5, 3.2.0, 3.3.0 with reference lapack, ATLAS and openblas. ARPACK 3.1.5 always fails, the other always pass (more details in the attached files). Now, the file has to be converted into an Octave installation test (here I cannot help).

Later I will submit the test which gives me different results in Octave and plain fortran.

(file #35954, file #35955)

Marco Caliari <caliari>
Group Member
Fri 08 Jan 2016 08:31:09 PM UTC, comment #18: 

@Marco: The configure test runs straight Fortran so if you have code that fails on the bad libraries that is good enough.  We don't need to have it fail in exactly the same way as in Octave proper.

But, does Octave succeed on a matrix that fails in straight Fortran?  If it does then there may be no need to blacklist old versions of ARPACK.

For reference, eigs is probably the most complicated function in Octave.

The code begins in scripts/sparse/eigs.m where some input validation is done and we handle the corner case of a small matrix which ARPACK does not do well.  The m-file also formats the output returned from C++.

If it is an ordinary case it is forwarded to libinterp/dldfcn/__eigs__.cc.  This also does input checking and then works to call the correct internal function based on characteristics of the inputs (complex? function or matrix? etc.).

The code then shifts to liboctave/numeric/eigs-base.cc.  Here you will find yet more input validation and a lot of code to prepare the inputs for forwarding on to Fortran code.  Eventually a particular Fortran routine is called and the results are passed back up the stack to the m-file.

Rik <rik5>
Group administrator
Fri 08 Jan 2016 10:08:13 AM UTC, comment #17: 

Hi all,

I started with the job by searching all previous bugs related to eigs in order to understand whether they were caused by ARPACK. To be clear, I refer to the problem described here

https://forge.scilab.org/index.php/p/arpack-ng/issues/1315/

fixed in ARPACK 3.2.0 using dlahqr from LAPACK 2.0

https://github.com/opencollab/arpack-ng/pull/2

changed in ARPACK 3.3.0 using my hint on the previous web page. Right now, I have a rough fortran code which fails with ARPACK 3.1.5 and succeeds with both ARPACK 3.2.0 and 3.3.0. Good. But while searching the previous eigs bugs, I found some incompatible behaviours with ml. This can due to different arpack libraries behind or different eigs implementations or, probably, both. Moreover, I have to say that I cannot reproduce Octave's eigs behaviour with simple fortran files and ARPACK library. The main problem here is that I do not fully understand how eigs uses ARPACK. My proposal is to make a group that wants to understand and writes a document, like David's Sparse matrix implementation in Octave. I think this is a nice project for students in mathematics or computer science, too.

Marco Caliari <caliari>
Group Member
Tue 05 Jan 2016 05:02:10 PM UTC, comment #16: 

Re-titling report to reflect remaining open issue.

Rik <rik5>
Group administrator
Mon 28 Dec 2015 05:39:37 PM UTC, comment #15: 

hg id
85dfb551e4cd tip @default
this is after today's merge.

 PASS     13678
  FAIL         0
  XFAIL       26
  SKIPPED     46

So it passes now!!

Thanks

Doug Stewart <dastew>
Mon 28 Dec 2015 05:03:38 PM UTC, comment #14: 

I checked in Marco's change under his name on the default branch (http://hg.savannah.gnu.org/hgweb/octave/rev/73f62b4bb533).

@Doug: Could you try building and testing with a development version later than or equal to 20999:73f62b4bb533?

@Marco,@Mike: Does this fix need to be backported to stable?

Rik <rik5>
Group administrator
Mon 28 Dec 2015 04:25:35 PM UTC, comment #13: 

this is still failing with today's dev. branch

*** testif HAVE_ARPACK, HAVE_UMFPACK
 [u2,s2,v2,flag] = svds (A,k,0,opts);
 s2 = diag (s2);
 assert (flag, ! 1);
 tol = 10 eps() norm(s2, 1);
 assert (s2, s(k:-1:1), tol);

!!!!! test failed
ASSERT errors for:  assert (s2,s (k:-1:1),tol)

  Location  |  Observed  |  Expected  |  Reason
     .          O(6x1)       E(7x1)      Dimensions don't match

Doug Stewart <dastew>
Sat 19 Dec 2015 08:49:30 AM UTC, comment #12: 

@Rik: the best I can do in a fast way is a diff wrt svds.m 4.0.0, which I include here as svds.patch. Hope this helps.

Marco

(file #35797)

Marco Caliari <caliari>
Group Member
Sat 19 Dec 2015 12:24:47 AM UTC, comment #11: 

@Marco: I removed the save/restore of the randn seed in the BIST tests for svds in this cset http://hg.savannah.gnu.org/hgweb/octave/rev/7832c351a6f5.

I think the flipud () patch should be applied to stable before the 4.0.1 bug fix release if possible, but that is if you have time.

Rik <rik5>
Group administrator
Wed 16 Dec 2015 03:03:00 PM UTC, comment #10: 

For point #3, it might be that I can write a fortran test to check the wrong behavior of ARPACK<=3.1.5. My idea is something like


i = 0;
while 1
  fix the random seed to i;
  generate the initial random vector x0
  run arpack to compute eigenvalues and eigenvectors for a possibly small case
  if the dneupd bug is triggered, print x0, break
  else i++
end


In principle, now I have an initial vector x0, which can be hard-coded, which triggers the bug.

Marco Caliari <caliari>
Group Member
Tue 15 Dec 2015 08:20:41 PM UTC, comment #9: 

@Marco: I like suggestion #1 to use flipud(-s).

For point #2, normest used to use randn but switched to rand in 2010.  Apparently, nobody got around to updating the svds tests.

For point #3, Octave already does one check at configure time on the ARPACK library.  See the file m4/acinclude.m4 and the macro OCTAVE_CHECK_LIB_ARPACK_OK.  Other tests could be added here, although we prefer to check behavior rather than version numbers.


dnl
dnl Check whether ARPACK works (does not crash).
dnl
dnl Using a pure Fortran program doesn't seem to crash when linked
dnl with the buggy ARPACK library but the C++ program does.  Maybe it
dnl is the memory allocation that exposes the bug and using statically
dnl allocated arrays in Fortran does not?
dnl
dnl FIXME: it would be nice to avoid the duplication of F77 macros
dnl and typedefs here and in the f77-fcn.h header file.
dnl
AC_DEFUN([OCTAVE_CHECK_LIB_ARPACK_OK], [



Rik <rik5>
Group administrator
Tue 15 Dec 2015 07:47:03 PM UTC, comment #8: 

1)
For this particular case (I mean, failure of a test in svds), I think it is possible to do something. In fact, when b_sigma == 0, the eigenvalues are symmetric about 0. Moreover, if sigma is an eigenvalue of [0,A;A'0], then -sigma is an eigenvalue as well. Since svds requires 2*k eigenvalues, the expected result is k positive eigenvalues and k negative. But, it may happen (due to random initializations in ARPACK) that the number of positive eigenvalues is less than k. But it means that the number of negative ones is larger than k. So, take flipud(-s) instead of s.
So, before


tol = norma * opts.tol;


I addedd


   if (b_sigma == 0)
     if (sum (s > 0) < k)
       s = flipud (-s);
     endif
   endif


and now test svds always succeeds.

2)
I do not understand


%! randn ("state", 42);      % Initialize to make normest function reproducible


In fact, normest.m uses rand, not randn.

3)
Arpack <= 3.1.5 has a serious bug when requesting both eigenvalues and eigenvectors (see #44004). Is it possible to detect Arpack version when installing Octave?

Marco

Marco Caliari <caliari>
Group Member
Tue 15 Dec 2015 05:36:54 PM UTC, comment #7: 

I'm sure that one of the libraries has changed.

With the failing combination, can you check if there is an initial seed that works?

Edit svds.m and change the constant 42 to another value (try a few different integers in the range 35-50)


%! randn ("state", 42);      % Initialize to make normest function reproducible
%! rand ("state", 42);


Then run the attached tst_svds.m to see if there are any failures.

I had other people help with this earlier for cygwin and mingw and there are not that many values which work across all platforms.




(file #35752)

Rik <rik5>
Group administrator
Tue 15 Dec 2015 05:07:54 PM UTC, comment #6: 

Ok, but this is an upgrade that is causing this error to arise now. I'm willing to put some more energy into this to prove it if necessary, but I suspect it's a new version of OpenBLAS causing this error to appear. I haven't yet, but I am willing to try comparing older and newer versions of OpenBLAS to see if the error follows.

Mike Miller <mtmiller>
Group Member
Tue 15 Dec 2015 05:01:11 PM UTC, comment #5: 

The testing of svds has always been problematic.  The method used in ARPACK depends on the initial seed and so there have been problems over the years with initializing everything, including the random number generators, to get reproducible behavior.

For a while, we seemed to have had that.  My question is whether we shouldn't treat the test as correct?  It is identifying that the particular library combination installed is not as good as other combinations.  The fault is not with Octave, but wouldn't it still be better to alert users so that they could upgrade rather than suppressing that information?

The test 'svds (A,k,0)' is a stress test which is why it is more prone to failure.  But that does make it a useful probe.

Rik <rik5>
Group administrator
Tue 15 Dec 2015 02:34:51 PM UTC, comment #4: 

On my system at least, it's an interaction between OpenBLAS and ARPACK. Yes, ARPACK is the library being called, but if netlib BLAS is used, I get the expected results.

Regardless, yes on certain systems it seems that this test is no longer as reproducible as it was meant to be.

How about the attached, based on Marco's suggestion. I don't need to increase the tol on my end, but I added an assertion to ensure that the number of singular values is no more than one less than what we requested.

(file #35751)

Mike Miller <mtmiller>
Group Member
Tue 15 Dec 2015 10:46:35 AM UTC, comment #3: 

I tried with ARPACK 3.3.0, same result. I think Rik gave the correct interpretation in #42658. I propose to modify the test


%! tol = 100 * eps() * norm(s2, 1);
%! assert (s2, s(length(s2):-1:1), tol);


Marco

Marco Caliari <caliari>
Group Member
Mon 14 Dec 2015 08:08:25 PM UTC, comment #2: 

Way back on ubuntu 12.04 and everything works fine.


ii  libblas-dev                                1.2.20110419-2ubuntu1                               Basic Linear Algebra Subroutines 3, static library
ii  libopenblas-base                           0.1alpha2.2-3                                       Optimized BLAS (linear algebra) library based on GotoBLAS2
ii  libopenblas-dev                            0.1alpha2.2-3                                       Optimized BLAS (linear algebra) library based on GotoBLAS2


The arpack library may also be relevant for svds.

ies


ii  libarpack2                                 3.0.2-3                                             Fortran77 subroutines to solve large scale eigenvalue problems
ii  libarpack2-dev                             3.0.2-3                                             Fortran77 subroutines to solve large scale eigenvalue problems (development)


Rik <rik5>
Group administrator
Mon 14 Dec 2015 07:56:35 PM UTC, comment #1: 

This test fails also with Debian with the current version of OpenBLAS, but does not require loading Java to trigger the test failure. Maybe more than one interaction leading to this happening?


$ LD_LIBRARY_PATH=/usr/lib/libblas:/usr/lib/lapack octave-cli --eval "test svds"
PASSES 6 out of 6 tests


$ octave-cli --eval "test svds"
warning: svds: returning fewer singular values than requested
warning: svds: try increasing the value of sigma
***** testif HAVE_ARPACK, HAVE_UMFPACK
 [u2,s2,v2,flag] = svds (A,k,0,opts);
 s2 = diag (s2);
 assert (flag, !1);
 tol = 10 * eps() * norm(s2, 1);
 assert (s2, s(k:-1:1), tol);

!!!!! test failed
ASSERT errors for:  assert (s2,s (k:-1:1),tol)

  Location  |  Observed  |  Expected  |  Reason
     .          O(6x1)       E(7x1)      Dimensions don't match


Originally posted here: http://lists.gnu.org/archive/html/octave-maintainers/2015-12/msg00111.html

Mike Miller <mtmiller>
Group Member
Mon 14 Dec 2015 07:44:56 PM UTC, original submission:  



>> test svds
PASSES 6 out of 6 tests
>> jobj = javaObject ("java.lang.StringBuffer");
>> test svds
warning: returning fewer singular values than requested
warning: try increasing the value of sigma
***** testif HAVE_ARPACK, HAVE_UMFPACK
 [u2,s2,v2,flag] = svds (A,k,0,opts);
 s2 = diag (s2);
 assert (flag, !1);
 tol = 10 * eps() * norm(s2, 1);
 assert (s2, s(k:-1:1), tol);

!!!!! test failed
ASSERT errors for:  assert (s2,s (k:-1:1),tol)

  Location  |  Observed  |  Expected  |  Reason
     .          O(6x1)       E(7x1)      Dimensions don't match
>>


similar problem appears in bug #43505

Avinoam Kalma <avinoam>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #35998:  dndrv1.f added by caliari (15KiB - text/x-fortran)
file #35954:  bug_1315_double.c added by caliari (2KiB - text/x-csrc)
file #35955:  bug_1315.txt added by caliari (2KiB - text/plain)
file #35797:  svds.patch added by caliari (632B - text/x-patch)
file #35752:  tst_svds.m added by rik5 (94B - d2l/unknowntype)
file #35751:  svds.diff added by mtmiller (488B - text/x-diff)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by lachlan (Posted a comment)
  • -email is unavailable- added by dastew (Posted a comment)
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by avinoam (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 15 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-04-05 rik5 Open/ClosedOpen Closed
    2017-04-05 caliari StatusIn Progress Works For Me
    2016-01-12 caliari Attached File- Added dndrv1.f, #35998
    2016-01-09 caliari Attached File- Added bug_1315_double.c, #35954
        Attached File- Added bug_1315.txt, #35955
    2016-01-05 rik5 Assigned toNone caliari
    2016-01-05 rik5 Summarytest svds fails Need better configure test for bad ARPACK library
    2015-12-28 rik5 StatusConfirmed In Progress
    2015-12-19 caliari Attached File- Added svds.patch, #35797
    2015-12-15 rik5 Attached File- Added tst_svds.m, #35752
    2015-12-15 mtmiller Attached File- Added svds.diff, #35751
    2015-12-14 mtmiller CategoryOctave Function Libraries
        StatusNone Confirmed
        Release4.0.1-rc1 dev
        Operating SystemMicrosoft Windows Any

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code