bugGNU Octave - Bugs: bug #51241, Infinite loop in normest1

 
 

bug #51241: Infinite loop in normest1

Submitted by:  Guillaume <gyom>
Submitted on:  Thu 15 Jun 2017 02:43:23 PM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Guillaume Open/Closed:  Closed
Release:  dev Operating System:  Any

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)

Fri 16 Jun 2017 04:05:14 PM UTC, comment #20: 

I modified the placement of the comments to be clearer and pushed it to the stable branch here (http://hg.savannah.gnu.org/hgweb/octave/rev/4ce622b7b930).  I also pulled it through to the development branch.  Thanks for the very quick fix Marco (< 24 hours from reporting bug to a verified solution).

Rik <rik5>
Project Administrator
Fri 16 Jun 2017 02:49:39 PM UTC, comment #19: 

Thanks Marco, I applied your patch and the issue disappeared.

Guillaume <gyom>
Fri 16 Jun 2017 11:09:45 AM UTC, comment #18: 

Here it is my patch.

(file #40926)

Marco Caliari <caliari>
Project Member
Fri 16 Jun 2017 08:22:18 AM UTC, comment #17: 

Thanks Marco, I can also confirm it works with your suggestion.

Guillaume <gyom>
Thu 15 Jun 2017 08:21:57 PM UTC, comment #16: 

@Marco: Your suggested change works for me.

Also, your suggested test case fails reliably, but I agree with Dmitri that it is likely to be a problem to put a test which may hang Octave in the general test suite. 

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 08:16:15 PM UTC, comment #15: 

rand('seed',1);, condest (a) hangs reliably for me, but I am not
sure this is a good test for unattended build servers.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Thu 15 Jun 2017 08:06:55 PM UTC, comment #14: 

I think that the reason is not the misplaced i++, but the wrong maximum number of unparallel columns 2^(n-1) (in the comment it is written parallel, this is also wrong). I propose to modify

imax = min (t, 2 ^ (n - 1));

to

imax = min (t, 2 ^ (n - 1) - n);

If it works for you, I will make a patch. How is it possible to add a test for this bug? For instance, I can always reproduce it with

rand('seed',1);, condest (a)

Is it true for everybody?

Marco Caliari <caliari>
Project Member
Thu 15 Jun 2017 04:36:30 PM UTC, comment #13: 

@Rik: Thanks. Your fix seems to work for me. I add Marco to this report in case he can comment on it.

Guillaume <gyom>
Thu 15 Jun 2017 04:36:19 PM UTC, comment #12: 

Adding Marco Caliari to the CC list since he provided the patch for the original function.

changeset:   22183:bfb1b089c230
user:        Marco Caliari <marco.caliari@univr.it>
date:        Mon Jul 25 14:50:29 2016 +0100
summary:     New function normest1 as replacement for onenormest (patch #8837)

The patch was applied after 4.0.3 and before 4.2.0 so it fits the timeline for the introduction of the regression in behavior.

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 04:32:39 PM UTC, comment #11: 

Bug seems to have been introduced between 4.0.3 and 4.2.0.

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 04:11:44 PM UTC, comment #10: 

Attached is a diff which moves the increment i++ outside of the else branch so that it always takes place.  That solves the issue for me, and 'test normest1' and 'test condest' still pass.  But since I didn't write this code I don't really know if what I'm proposing is correct.

(file #40921)

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 04:08:38 PM UTC, comment #9: 

I don't understand the algorithm, but here is a dump of the variables.

debug> i
i =  2
debug> imax
imax =  3
debug> p
p = 0
debug> S
S =

   1   1  -1
  -1   1   1
  -1  -1   1

debug> Sold
Sold =

   1   1  -1
   1  -1  -1
   1   1   1

The issue is this expression

any (abs (S(:,i)' * Sold) == n)

which is always true.  I wonder if the code should read

if (expression)
  ## i-th column of S parallel to previous one
  do stuff...
endif
i++;

rather than

if (expression)
  ## i-th column of S parallel to previous one
  do stuff...
else
  i++;
endif

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 04:01:34 PM UTC, comment #8: 

Within normest1, the problem is this section of code

          while (i <= imax)
            ## The maximum number of parallel columns of length n with entries
            ## {-1,1} is 2^(n-1). Therefore, if the number of columns of S is
            ## greater than 2^(n-1), for sure some of them are parallel to some
            ## columns of Sold. Don't even try to change them (i <= 2^(n-1)).
            ## Now, check if S(:,i) is parallel to any previous column of S
            p = (any (abs (S(:,i)' * S(:,1:i-1)) == n));
            if (p || (any (abs (S(:,i)' * Sold) == n)))
              ## i-th column of S parallel to a previous or to a
              ## column of Sold: change it.
              S(:,i) = sign (2*rand (n, 1)-1);
            else
              i++;
            endif
          endwhile

If the first branch of the if statement is taken, then the variable i is never incremented.

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 03:56:58 PM UTC, comment #7: 

I used dbstep to step through the code.  The line that hangs is

[Ainv_norm, v, w] = normest1 (solve, t, [], varargin{4:end});

normest1.m is an m-file and it does have while loops so that is probably where the problem lies.

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 03:38:42 PM UTC, comment #6: 

There are calls to rand(), see the help text:

## Algorithm Note: @code{condest} uses a randomized algorithm to approximate
## the 1-norms.

Guillaume <gyom>
Thu 15 Jun 2017 03:36:54 PM UTC, comment #5: 

There are "lu" and "\" in the code which are iterative and thus can hang. What puzzles me is the randomness of this.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Thu 15 Jun 2017 03:33:03 PM UTC, comment #4: 

I can confirm it on this cset as well:

[dima@i7 gcc_default]$ hg id
b0e9c030f063 tip @
[dima@i7 gcc_default]$ ./run-octave --no-gui
GNU Octave, version 4.3.0+
Copyright (C) 2016 John W. Eaton and others.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  For details, type 'warranty'.

Octave was configured for "x86_64-pc-linux-gnu".

Additional information about Octave is available at http://www.octave.org.

Please contribute if you find this software useful.
For more information, visit http://www.octave.org/get-involved.html

Read http://www.octave.org/bugs.html to learn how to submit bug reports.
For information about changes from previous versions, type 'news'.

octave:1> a = [146.50 3.2070e-61 0;3.2070e-61 147.50 0;0 0 144.00];
octave:2> condest(a)
^C
octave:2> condest(a)
^C
octave:2> condest(a)
^C
octave:2> condest(a)
ans =  1.0243
octave:3> condest(a)
ans =  1.0243
octave:4> condest(a)

Dmitri A. Sergatskov <dasergatskov>
Thu 15 Jun 2017 03:21:22 PM UTC, comment #3: 

For reference, I am using cset 23604:b0e9c030f063.  You might try updating to that version as this bug seems to be present for 4.2.1 but not on the latest development tip.

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 03:19:21 PM UTC, comment #2: 

I can confirm the behaviour with 4.2.1

Dmitri.

Dmitri A. Sergatskov <dasergatskov>
Thu 15 Jun 2017 03:14:28 PM UTC, comment #1: 

This works for me.  I also don't see any for/while/do-until loops in condest.m so I don't see how it could get caught in an infinite loop.

Maybe try stepping through the code using the debugger and seeing what statement causes the hang for you.

Rik <rik5>
Project Administrator
Thu 15 Jun 2017 02:43:23 PM UTC, original submission:  

In a random way, condest seems to get stuck in a loop:

a = [146.50 3.2070e-61 0;3.2070e-61 147.50 0;0 0 144.00];
condest(a)

It returns 1.0243 or never returns.

Guillaume <gyom>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #40926:  normest1_marco.diff added by caliari (2KiB - application/x-tex)
file #40921:  normest1.diff added by rik5 (540B - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    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 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-06-16 rik5 StatusPatch Submitted => Fixed
        Open/ClosedOpen => Closed
    2017-06-16 caliari Attached File- => Added normest1_marco.diff, #40926
        StatusIn Progress => Patch Submitted
    2017-06-16 rik5 StatusPatch Submitted => In Progress
    2017-06-15 rik5 Carbon-Copy- => Added caliari
    2017-06-15 rik5 Attached File- => Added normest1.diff, #40921
        StatusConfirmed => Patch Submitted
    2017-06-15 rik5 SummaryInfinite loop in condest => Infinite loop in normest1
    2017-06-15 rik5 StatusWorks For Me => Confirmed
    2017-06-15 rik5 StatusNone => Works For Me

    Back to the top


    Powered by Savane 3.5