bugGNU Octave - Bugs: bug #53560, tests: pinv.cc-tst BIST test...

 
 

bug #53560: tests: pinv.cc-tst BIST test failing occasionally

Submitted by:  Rik <rik5>
Submitted on:  Wed 04 Apr 2018 07:01:46 PM UTC  
 
Category:  Test Suite Severity:  3 - Normal
Priority:  1 - Later Item Group:  Unexpected Error
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  Closed
Release:  dev Operating System:  GNU/Linux

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Sat 07 Apr 2018 05:07:37 PM UTC, comment #7: 

The issue about the test suite failing has been fixed by using a specific random seed during tests.

According to Marco, the pseudoinverse as calculated in both Matlab and Octave is more accurate as a "right inverse" rather than a "left inverse".  This just seems to be what we have to live with.

Closing report.

Rik <rik5>
Project Administrator
Fri 06 Apr 2018 02:14:42 PM UTC, comment #6: 

I modified the script and run in MatlabR2017b. I see a warning rate of about 1%. In octave it seems slightly smaller. So, the BIST test should be fixed, but I think there is no problem with pinv.

(file #43823)

Marco Caliari <caliari>
Project Member
Wed 04 Apr 2018 09:44:19 PM UTC, comment #5: 

THis is super annoying.  I don't know what the issue is, but it goes pretty deep.

I tried excluding high condition number matrices (cond # > 25), but there are still occasional failures.

The algorithm for pinv is actually implemented in liboctave/array/dMatrix.cc (for double matrices).  It uses the singular value decomposition.  I played around with changing the LAPACK driver that we use for calculating the SVD from gesdd to gesvd using the svd_driver() function.  This also didn't help.

It may just be round-off errors during intermediate computations during matrix multiplication.  The BIST test is attempting to verify the Penrose conditions on the pseudoinverse.  It should be the case that

A*B*A - A = 0
B*A*B - B = 0

However, only the first condition is accurate (<8 eps).  This may have something to do with the order of multiplication.

I think we should ask someone on the Maintainer's list to run the code in Matlab and see if it fails there as well.  But that can come later.  For now, I just fixed the random seed to a known value (http://hg.savannah.gnu.org/hgweb/octave/rev/435645a627dd).

Rik <rik5>
Project Administrator
Wed 04 Apr 2018 07:56:16 PM UTC, comment #4: 

OK, I verified that I get occasional failures (~1.5%)
with any other blas library I have available.

E.g.:

 LD_PRELOAD=/usr/lib64/atlas/libtatlas.so ./run-octave  -q -f
octave:1> for jj=1:1e3 ; bm(jj) = test ("libinterp/corefcn/pinv.cc-tst");  endfor ; sum(bm)
ans =  988

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 04 Apr 2018 07:48:18 PM UTC, comment #3: 

OK, may be not. The original bug was a hanged octave running at 1
100% load, now it is a precision failure.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 04 Apr 2018 07:34:47 PM UTC, comment #2: 

Dmitri - are you sure this test failure is due to a Fedora packaging bug? The test may fail more often or always because of this on your system, but it's not the only cause.

When I run 'test pinv.cc' in a loop on Debian, I get from 2 to 10 random failures out of 500, either with OpenBLAS or with reference BLAS. I agree with Rik we should probably just test with a fixed random state, and maybe come back to it later.

Mike Miller <mtmiller>
Project Administrator
Wed 04 Apr 2018 07:12:13 PM UTC, comment #1: 

Fedora ships broken Openblas which they refuse to fix (*).
I replaced it on buildbot with selfcompiled,
but a recent update overwritten it. I replaced it again.

(*) https://bugzilla.redhat.com/show_bug.cgi?id=1507744

Dmitri.

Dmitri A. Sergatskov <dasergatskov>
Wed 04 Apr 2018 07:01:46 PM UTC, original submission:  

The BIST test in pinv.cc is failing occasionally.  I noticed this first with the buildbots (http://buildbot.octave.org:8010/builders/gcc-fedora/builds/1448/steps/test/logs/stdio), but I can reproduce it with the following code:

for i = 1:1e3
> bm(i) = test ('pinv.cc');
> endfor
sum (bm)
ans =  989

The BIST test is

%!shared a, b, tol, hitol, d, u, x, y
%! a = reshape (rand*[1:16], 4, 4);  # Rank 2 matrix
%! b = pinv (a);
%! tol = 4e-14;
%! hitol = 40*sqrt (eps);
%! d = diag ([rand, rand, hitol, hitol]);
%! u = rand (4);                     # Could be singular by freak accident
%! x = inv (u)*d*u;
%! y = pinv (x, sqrt (eps));
%!
%!assert (a*b*a, a, tol)
%!assert (b*a*b, b, tol)
%!assert ((b*a)', b*a, tol)
%!assert ((a*b)', a*b, tol)
%!assert (x*y*x, x, -hitol)
%!assert (y*x*y, y, -hitol)
%!assert ((x*y)', x*y, hitol)
%!assert ((y*x)', y*x, hitol)

Just for fun, I fixed the random seed at the top of the test and then I can get 1000 successful tests.

Should we just fix the random seed?

I used the following code in a script tst_pinv.m

N = 1e3;

tol = 4e-14;
for i = 1:N
  a = reshape (rand*[1:16], 4, 4);  # Rank 2 matrix
  b = pinv (a);
  assert (a*b*a, a, tol);
  assert (b*a*b, b, tol);
  assert ((b*a)', b*a, tol);
  assert ((a*b)', a*b, tol);
endfor

When it errors out I can look at the results.  For the failing case the condition number of a is greater than 2e17.  Should we really be using such a difficult matrix for testing?  Even without the randomization, the condition number is quite high.

cond (reshape(1:16, 4, 4))
ans =    9.3757e+16

This is because the columns are not linearly independent.  You can add the value 4 to a column to turn it in to the adjacent column.

As a reference, the condition number of a random 4x4 matrix is much smaller.

cond (rand (4))
ans =  42.840
cond (rand (4))
ans =  11.335

Maybe we should be doing something like this instead?

a = rand (4, 4);
while (cond (a) > 100)
  a = rand (4,4);
endwhile

Hmmphh.  Just tried that and it didn't work either.

Rik <rik5>
Project Administrator

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #43823:  test_pinv.m added by caliari (430B - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-04-07 rik5 StatusPostponed => Fixed
        Open/ClosedOpen => Closed
    2018-04-06 mtmiller Priority5 - Normal => 1 - Later
        Summarypinv BIST test failing occasionally => tests: pinv.cc-tst BIST test failing occasionally
    2018-04-06 caliari Attached File- => Added test_pinv.m, #43823
    2018-04-04 rik5 StatusNone => Postponed
    2018-04-04 rik5 Carbon-Copy- => Added mtmiller

    Back to the top


    Powered by Savane 3.5