bugGNU Octave - Bugs: bug #53258, test pcg.m fail

 
 

bug #53258: test pcg.m fail

Submitter:  Dmitri A. Sergatskov <dasergatskov>
Submitted:  Fri 02 Mar 2018 03:34:03 AM UTC
   
 
Category:  Test Suite Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
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 10 Mar 2018 10:48:32 PM UTC, comment #23: 
Carlo de Falco <cdf>
Group Member
Sat 10 Mar 2018 05:39:59 PM UTC, comment #22: 

@Carlo: Yes, go ahead and merge these on to the development branch.  I find that it is best to get the code under version control and then iterate, rather than try and make it perfect outside the system and do a single merge.

Rik <rik5>
Group administrator
Sat 10 Mar 2018 01:48:36 AM UTC, comment #21: 

Rik, I agree that it is inefficient to keep working on the old version of the code.

So, is it OK if I merge Cristiano's branch into default now
and we keep working there?

You can see the complete set of changes here:
https://bitbucket.org/cdf1/octave/branch/dorigo#diff

These are all the files touched:

doc/interpreter/linalg.txi
scripts/sparse/bicg.m
scripts/sparse/bicgstab.m
scripts/sparse/cgs.m
scripts/sparse/gmres.m
scripts/sparse/ilu.m
scripts/sparse/module.mk
scripts/sparse/pcg.m
scripts/sparse/private/__alltohandles__.m
scripts/sparse/private/__default__input__.m
scripts/sparse/tfqmr.m

it doesn't really look too invasive, I think
we can review and finalize the changes in a
codesprint next week.


notice that this will override your changes to test
from changeset 96c74e33d17a but I think it's easier
to re-apply them manually also considering that similar
changes may also be needed for the 12 new BIST in pcg
and for the BIST in other solvers.

Carlo de Falco <cdf>
Group Member
Fri 09 Mar 2018 03:59:11 PM UTC, comment #20: 

In the interests of efficiency, I don't think we should continue working to debug the existing code.  Instead, we should merge in the new iterative solver code and then ensure the test suite is working.

Rik <rik5>
Group administrator
Fri 09 Mar 2018 08:42:11 AM UTC, comment #19: 

@Carlo: I'm here with Cristiano. His version fails the test from time to time, both in stable and default branch. We agree that the problem is the test itself, not the algorithm.

Marco Caliari <caliari>
Group Member
Fri 09 Mar 2018 07:37:53 AM UTC, comment #18: 

@Carlo, Rik: the test is very trivial and maye its purpose is really to check that pcg converges within N+1 iterations. As such, I like Carlo's idea to set the tolerance to zero, check that the final error is below something like 1e-14 and check that flag is 1.
I do not know why Cristiano's version never fails. As far as I remember, the only big problem of pcg was detection of non-SPD matrices. We can investigate.

Marco Caliari <caliari>
Group Member
Fri 09 Mar 2018 12:58:02 AM UTC, comment #17: 

Thinking better, even if the problem never occurred with Cristiano's code, I agree with Rik that we can not expect error
to be below 1e-10 if we solve with a tolerance of 1e-6 on the residual.

So, if we really want to check error, either we should set tolerance to 0 to make sure all N+1 iterations are run and then check the error but ignore the convergence flag, or we should more carefully set the pcg tolerance parameter so that it makes sense in comparison with the error bound used in the assertion.

But probably Rik's idea of just checking the residual makes more sense here ...

Still I believe the new version of pcg is working better so it should be checked in ASAP.


Carlo de Falco <cdf>
Group Member
Fri 09 Mar 2018 12:25:10 AM UTC, comment #16: 

I went back to pcg in the default branch to hgid 2d68dc548561 (just before your change) and ran again


for i = 1: 10_000; test pcg; endfor


and got failure 57 times, this means approximately 1/175
of the runs are failing.

Tried again with Cristiano's version and got 0 failures.

My guess is that there might be a bug in the pcg implementation
in the default branch that hinders convergence rate and your changes to the tests are just hiding it.

My suggestion is to either revert this change and let the tests fail to make the bug apparent or to just move over to Cristiano's implementation that seems to have fixed this issue.

Does that make sense?

Carlo de Falco <cdf>
Group Member
Thu 08 Mar 2018 11:24:21 PM UTC, comment #15: 

I don't remember that overriding to N+1 (11) was sufficient.  I believe there were still occasional failures.  I did only occasional checking to verify the iter count and I believe it was sometimes 12 or 13.  There was no need to find the exact number where it worked so I set it to 20.

It may be that new version of pcg converges faster, I don't know.

Rik <rik5>
Group administrator
Thu 08 Mar 2018 11:03:13 PM UTC, comment #14: 

BTW, I tried


for i = 1: 10_000; test pcg; endfor


with Cristiano's version of pcg and never got a failure,
so maybe it could be that it is the algorithm and not the
test that needed fixing?


Carlo de Falco <cdf>
Group Member
Thu 08 Mar 2018 10:57:52 PM UTC, comment #13: 

@Rik, If the correct default value was documented incorrectly I agree the docs should be fixed, but I don't think the default value matters here as it was already overridden to be N+1, right?

As for the number of iterations, if I recall correctly, pcg should produce the exact solution after N iterations (and definitely that should be the case for a diagonal matrix), N+1 was probably used to allow the algorithm to detect convergence (as the test is performed at the beginning of the iteration) and to set the flag accordingly.

Cristiano and/or Marco can you comment on why 2*N iterations seem to be needed to robustly guarantee convergence?

Carlo de Falco <cdf>
Group Member
Thu 08 Mar 2018 10:38:46 PM UTC, comment #12: 

Because the behavior wasn't documented correctly.  It used to say that the default value for maximum iters was 20.  In fact, it is more complicated and it is


min (rows (b), 20)


In this case, b has 10 rows but 10+1 (11) iterations is not always enough to guarantee convergence.  I bumped it to 2*10 (20) iterations and I didn't see any failures after 40,000 test iterations.

Rik <rik5>
Group administrator
Thu 08 Mar 2018 10:27:39 PM UTC, comment #11: 

Why are you also changing


[x, flag] = pcg (A, b, [], N+1);


to


[x, flag] = pcg (A, b, [], 2*N);



?

Carlo de Falco <cdf>
Group Member
Thu 08 Mar 2018 12:53:42 PM UTC, comment #10: 

I like Carlo's and Cristiano's idea to take this up at OctConf 2018.

I did make a lot of changes, but the big one that was necessary to resolve this report was to change what the BIST tests were looking for.  See the small diff below


 %! ## solve small diagonal system
 %!
 %! N = 10;
-%! A = diag ([1:N]); b = rand (N, 1);
-%! X = A \ b;  # X is the true solution
-%! [x, flag] = pcg (A, b, [], N+1);
-%! assert (norm (x - X) / norm (X), 0, 1e-10);
+%! A = diag ([1:N]);
+%! b = rand (N, 1);
+%! [x, flag] = pcg (A, b, [], 2*N);
+%! assert (norm (A*x - b) / norm (b), 0, 1e-6);


In the original, the relative error in the solution X is checked.  But the pcg algorithm doesn't guarantee any such results so there were occasional failures in the BIST tests.

In the modified version, I look at the residuals (Ax - b) normalized by the magnitude of b [/ norm (b)].  This is the stopping criteria used by pcg itself so as long as flag==0 the tolerance of 1e-6 will have been met.


Rik <rik5>
Group administrator
Thu 08 Mar 2018 09:53:29 AM UTC, comment #9: 

Dear all, I will be at the OctConf on Monday afternoon and Tuesday morning. Then if there are problems with the changeset, I can help Carlo.

Cheers,
Cristiano

Cristiano Dorigo <cristianodorigo>
Thu 08 Mar 2018 07:36:10 AM UTC, comment #8: 

sorry, missing attachment.



(file #43486)

Carlo de Falco <cdf>
Group Member
Thu 08 Mar 2018 07:15:25 AM UTC, comment #7: 

@Rik,

I am maintaining a branch to integrate new versions of iterative
solvers developed by Cristiano Dorigo in bitbucket here:

https://bitbucket.org/cdf1/octave/branch/dorigo

I am having trouble merging this changeset.
I attach a diff between my version of pcg.m and the one in default, could you help me choose what changes I need to incorporate?

I am particularly not sure about the changes in the docstring.
also the feature branch contains more tests so probably they should be also fixed?

thanks,
c.

P.S. I never had time to push the merge since last OctConf, maybe that is a task for a codesprint next week?

Carlo de Falco <cdf>
Group Member
Thu 08 Mar 2018 06:27:18 AM UTC, comment #6: 

I fixed the BIST tests for pcg here (http://hg.savannah.gnu.org/hgweb/octave/rev/96c74e33d17a).  The trouble was that the pcg algorithm was using a different test for stopping criteria then the BIST tests.

Marking as fixed and closing report.

Rik <rik5>
Group administrator
Wed 07 Mar 2018 11:53:02 PM UTC, comment #5: 

Probably next most frequent is pinv e.g.:


http://buildbot.octave.org:8010/builders/gcc-5-debian/builds/1436/steps/test/logs/stdio

***** assert (y*x*y, y, -hitol)
!!!!! test failed
ASSERT errors for:  assert (y * x * y,y,-hitol)

  Location  |  Observed  |  Expected  |  Reason
   (2,4)       33.9874      33.9874      Rel err 8.1657e-07 exceeds tol 5.9605e-07 by 2e-07


Dmitri A. Sergatskov <dasergatskov>
Wed 07 Mar 2018 11:24:03 PM UTC, comment #4: 

Actually if you look at buildbots -- they are now regularly failing at some random tests. In most of those cases the
error exceeds tolerance by some small amount (usually less than a factor of 2). pcg looks much more gross in that regard, that is why I reported it -- I was wondering if there is something more serious here.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 07 Mar 2018 10:28:50 PM UTC, comment #3: 

Tedious, but I used grep to find other m-files that mentioned iteration in their documentation and then ran the BIST tests for each of those 1000 times.  The good news is that pcg is the only one that fails.

Rik <rik5>
Group administrator
Wed 07 Mar 2018 12:02:45 AM UTC, comment #2: 

Confirmed.

I bet this is because we don't fix a random seed and pcg is an iterative method which depends on the initial starting point.

For testing I used


N = 1e3;

bm = zeros (N,1);
for i = 1:N
  bm(i) = test ("pcg", "verbose", "pcg.res");
endfor

sum (bm)


The number of tests that pass is >=996, but there are a few failures for each 1000 iterations.

This probably means the BIST tests for all iterative solvers should be checked to see if they fail occasionally.

Rik <rik5>
Group administrator
Fri 02 Mar 2018 04:51:34 PM UTC, comment #1: 

I usually get few failures if I repeat test 1000 times.
This is one of the failed cases:


b = [
   0.12278472
   0.10887554
   0.37156328
   0.05834160
   0.52981297
   0.68811238
   0.00012278
   0.05733196
   0.78572195
   0.06894106
];


N = 10;
A = diag ([1:N]);
X = A \ b;  # X is the true solution
[x, flag] = pcg (A, b, [], N+1);
norm (x - X) / norm (X)

# ans =  0.00000057028


This is with OpenBLAS.

Dmitri.
--



Dmitri A. Sergatskov <dasergatskov>
Fri 02 Mar 2018 03:34:03 AM UTC, original submission:  

Now with updated rand seed testing:


http://buildbot.octave.org:8010/builders/gcc-fedora/builds/1353/steps/test/logs/stdio

>>>>> processing /home/buildbotu/fc25-x86_64/gcc-fedora/src/scripts/sparse/pcg.m
***** test
 ## solve small diagonal system

 N = 10;
 A = diag ([1:N]); b = rand (N, 1);
 X = A \ b;  # X is the true solution
 [x, flag] = pcg (A, b, [], N+1);
 assert (norm (x - X) / norm (X), 0, 1e-10);
 assert (flag, 0);
!!!!! test failed
ASSERT errors for:  assert (norm (x - X) / norm (X),0,1e-10)

  Location  |  Observed  |  Expected  |  Reason
     ()       3.9945e-07       0         Abs err 3.9945e-07 exceeds tol 1e-10 by 4e-07


The error looks pretty gross... (4000 X def tolerance)

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #43486:  open_vvOdMnml.txt added by cdf (35KiB - text/plain)

 

Depends on the following items: None found

Digest:
   bug dependencies.

 

Carbon-Copy List
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by cristianodorigo (Posted a comment)
  • -email is unavailable- added by cdf (Posted a comment)
  • -email is unavailable- added by cdf
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by dasergatskov (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 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-03-11 cdf Dependencies- bugs #53319 is dependent
    2018-03-08 cdf Attached File- Added open_vvOdMnml.txt, #43486
    2018-03-08 cdf Carbon-Copy- Added -email is unavailable-
    2018-03-08 rik5 StatusIn Progress Fixed
        Open/ClosedOpen Closed
    2018-03-07 rik5 StatusNone In Progress

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code