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

 
 

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

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

Add a New Comment Rich Markup
   

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>
Group 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>
Group 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>
Group 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>
Group Member
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>
Group 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
  •  

    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 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.13-d3ae.
    Corresponding source code